How to Check That the Passed Iterator Is a Random Access Iterator

How to check that the passed Iterator is a random access iterator?

If Iterator is a random access iterator, then

std::iterator_traits<Iterator>::iterator_category

will be std::random_access_iterator_tag. The cleanest way to implement this is probably to create a second function template and have Foo call it:

template <typename Iterator>
void FooImpl(Iterator first, Iterator last, std::random_access_iterator_tag) { 
    // ...
}

template <typename Iterator>
void Foo(Iterator first, Iterator last) {
    typedef typename std::iterator_traits<Iterator>::iterator_category category;
    return FooImpl(first, last, category());
}

This has the advantage that you can overload FooImpl for different categories of iterators if you'd like.

Scott Meyers discusses this technique in one of the Effective C++ books (I don't remember which one).

Checking if a template parameter have Random Access Iterator or not

Your HaveRandomAccessIterator template is overly complicated, there are simpler ways of achieving the same result.

One standard way to change an algorithm on the basis of the iterator type is tag-dispatch:

//First, a helper type alias
template<typename Container>
using IteratorCategoryOf =
    typename std::iterator_traits<typename Container::iterator>::iterator_category;

template<typename Container>
void algorithm(Container &c, std::forward_iterator_tag) {
    //do generic version of algorithm
}

template<typename Container>
void algorithm(Container &c, std::random_access_iterator_tag) {
    //do random-access version of algorithm
}

template<typename Container>
void algorithm(Container &c) {
    algorithm(
        c,
        IteratorCategoryOf<Container>());
}

Alternatively, you can use SFINAE through std::enable_if. I suspect this is what you were aiming to do, but HaveRandomAccessIterator can be written in terms of std::is_base_of, which is far simpler:

template<typename Container>
using HaveRandomAccessIterator =
    std::is_base_of<
        std::random_access_iterator_tag,
        IteratorCategoryOf<Container>>;

template<
    typename Container,
    typename std::enable_if<!HaveRandomAccessIterator<Container>::value>::type * = nullptr>
void algorithm(Container &c) {
    //do generic version of algorithm
}

template<
    typename Container,
    typename std::enable_if<HaveRandomAccessIterator<Container>::value>::type * = nullptr>
void algorithm(Container &c) {
    //do random-access version of algorithm
}

If C++03 compatibility is required, you can use inheritance rather than type-aliasing, and the boost counterparts to std::enable_if and std::is_base_of.

Represent sum of random access iterators as a random access iterator

You are asking to allow (left + right) / 2 as a shorter notation for left + (right - left) / 2 because these expressions are equivalent for numbers in mathematics. However, to do that, you would need to define the addition of 2 iterators and division of iterator by a number. Neither of these operations seems to make sense on their own.

pointer from random access iterator

If you can use C++20, there is std::to_address. Example:

std::vector<int> v{1, 2, 3};

int *ptr = std::to_address(v.begin());

How to compare two non-random access iterator in C++

Iterating over a linked list is of relatively high cost because of the potential accesses to memory that must be made. You'll want to minimize those accesses. There are a couple things you could do to that end:

1. Use find_if to search for either 18 or 25
2. Then search from that point with find_if again for either 7 or the other bound
3. If the other bound was found 1^st there is no intervening 7 if the 7 was found first ensure the other bound exists

So your code could look like this:

const auto start = find_if(cbegin(vec), cend(vec), [](const auto& i){ return i == 18 || i == 25; });
const auto target = find_if(start, cend(vec), [finish = *start == 18 ? 25 : 18](const auto& i){ return i == 7 || i == finish; });
const auto finish = *target == 7 ? find(target, cend(vec), *start == 18 ? 25 : 18) : cend(vec);

After this if finish doesn't point to cend(vec) then target is a valid pointer to the 1^st 7 in the range.

Live Example

---

Vlad from Moscow's solution cleverly avoided the need for lambdas by using find_first_of, but it iterated over the contents of vec more than once, making it more expensive than my algorithm. The marriage of these 2 algorithms results in an algorithm that is faster than my original while preserving the benefit of only accessing each element once:

const int a[] = { 18, 25 };
const auto start = find_first_of(cbegin(vec), cend(vec), cbegin(a), cend(a));
const int b[] = { *start == *cbegin(a) ? *crbegin(a) : *cbegin(a), 7 };
const auto target = find_first_of(start, cend(vec), cbegin(b), cend(b));
const auto finish = *target == *crbegin(b) ? find(target, cend(vec), *cbegin(b)) : cend(vec);

Again if finish doesn't point to cend(vec) then target is a valid pointer to the 1^st 7 in the range.

Live Example

C++ reverse iterator based on existing random access iterator?

You need to define the reverse_iterator type alias and the rbegin and rend methods. The reverse iterator should be implemented with std::reverse_iterator (defined in header <iterator>)

using       reverse_iterator = std::reverse_iterator<      iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

      reverse_iterator rbegin()       { return end  (); }
const_reverse_iterator rbegin() const { return end  (); }
      reverse_iterator rend  ()       { return begin(); }
const_reverse_iterator rend  () const { return begin(); }

const_reverse_iterator crbegin() const { return rbegin(); }
const_reverse_iterator crend  () const { return rend  (); }

And that's everything. No magic.

C++; Pass a std::array Random Access Iterator as a Function Parameter

You need to use typename to hint to the compiler that iterator is a type

template<size_t SIZE>
void QuickSort(typename array<int, SIZE>::iterator low,
               typename array<int, SIZE>::iterator high);

But that won't work either since SIZE is in a nondeduced context. It would be better to just make an iterator as a template

template<typename RandomIt>
void QuickSort(RandomIt low, RandomIt high);

---

Related Topics