Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c++

iterator

stl

I have the following code, which does some iterator arithmetic:

template<class Iterator> void Foo(Iterator first, Iterator last) {   typedef typename Iterator::value_type Value;   std::vector<Value> vec;   vec.resize(last - first);   // ... } 

The (last - first) expression works (AFAIK) only for random access iterators (like the ones from vector and deque). How can I check in the code that the passed iterator meets this requirement?

like image 871
Frank Avatar asked Nov 29 '10 19:11

Frank


People also ask

Is iterator random access?

Random-access iterators are iterators that can be used to access elements at an arbitrary offset position relative to the element they point to, offering the same functionality as pointers. Random-access iterators are the most complete iterators in terms of functionality.

How do I find my iterator type?

Iterator type can be checked by using typeid.

What is the difference between a bidirectional iterator and a random access iterator?

The distinction is simply that the Bidirectional Iterator implementations are linear time, while Random Access Iterators are required to support random access to elements in amortized constant time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.

Do linked lists have random access iterators?

Linked lists are not random access containers. You cannot meaningfully implement random access iteration, nor a conventional operator[](size_t) for regular single or double linked lists. People who use your list class will not expect random access iteration, and will be confused by it.


1 Answers

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).

like image 190
James McNellis Avatar answered Oct 10 '22 15:10

James McNellis