What Are Scary Iterators

What are SCARY iterators?

If you're using them, there's no need to get SCAREd... just ignore their SCARY-ness.

If you're making them, that means you have to make your iterators independent of the container's allocator type, and of other generic parameters to the container that don't affect the iterators.

Why don't iterators depend on allocators? (i.e. does't making iterators SCARY violate the allocator's typedef abstractions?)

Allocators were initially designed to provide an interface into the memory model of the platform for which the program was compiling. Most current architectures (if not all) provide a flat memory model, and a single pointer type can be used to address memory in any program (no need for near and far pointers anymore).

That is reflected in C++11 in allocator_traits. Now it is not mandatory for an allocator to provide many of the typedefs that were previously required, including pointer_type or reference_type, difference_type and so on as there is a known good default value. This really maps to current practice, in most STL implementations those types are the same in all allocators.

Whenever the allocator does not provide the typedefs or the types are the same as the default value provided in allocator_traits there is no point in differentiating the iterators based on what allocator was used to construct the container. Where that assumption does not hold, the implementation could determine to use a different iterator type only for those allocators that provide a different set of typedefs than the default.

Note that I have not looked at their implementation, so take this at face value: that would support the intended purpose (minimize the generated code without breaking standard compliance).

Also note that this is not the only approach. The current allocator model in C++11 supports the use of polymorphic allocators, even if the standard does not yet provide an implementation. With polymorphic allocators a single allocator template argument (a polymorphic adaptor) provides the typedefs and the interface with the container, internally managing a pointer to a real allocator used to provide the memory.

The purpose of polymorphic allocators is the same as the paper referred by in the linked article: allow the creation of vocabulary types. Where the SCARY allocators focus on providing a vocabulary type for the iteration over a particular container type, polymorphic allocators go one step further and enable the use of the container itself as a vocabulary type, regardless of what the actual mechanism to acquire memory is.

You can find a reference implementation of polymorphic allocators (using different names) in Bloomberg's BSL

What is the correct way of declaring an iterator?

std::set<int>::iterator itr; is wrong.

It happens to work on both GCC, Clang, and MSVC by default.
But e.g. if I enable GCC's iterator debugging (-D_GLIBCXX_DEBUG), it stops compiling.

Normally you don't need to manually spell the iterator type. You can do for (auto itr = s1.begin(); ...). Or, if the iterator needs to be created uninitialized, decltype(s1)::iterator itr;.

Are all end() iterators equivalent for a collection type?

No, because of the STL container and iterator requirements:

23.2.1 General container requirements [container.requirements.general]

6 begin() returns an iterator referring to the first element in the
container. end() returns an iterator which is the past-the-end value
for the container. If the container is empty, then begin() == end();

24.2.1 In general [iterator.requirements.general]

6 An iterator j is called reachable from an iterator i if and only if
there is a finite sequence of applications of the expression ++i that
makes i == j. If j is reachable from i, they refer to elements of the
same sequence.

The equality of begin() and end() for empty containers means that begin() and end() need to be part of the same container objects, and hence end() cannot be a static member of a container class. Note also that -except for forward iterators- applying operator-- on end() would be impossible to resolve with a static end() iterator.

How to implement an STL-style iterator and avoid common pitfalls?

https://cplusplus.com/reference/iterator/ has a handy chart that details the specs of § 24.2.2 of the C++11 standard. Basically, the iterators have tags that describe the valid operations, and the tags have a hierarchy. Below is purely symbolic, these classes don't actually exist as such.

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};

input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.

output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an output iterator has been dereferenced, it is 
//undefined to dereference one before that.

forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed

bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix decrement
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

contiguous_iterator : random_access_iterator { //C++17
}; //elements are stored contiguously in memory.

You can either specialize std::iterator_traits<youriterator>, or put the same typedefs in the iterator itself, or inherit from std::iterator (which has these typedefs). I prefer the second option, to avoid changing things in the std namespace, and for readability, but most people inherit from std::iterator.

struct std::iterator_traits<youriterator> {        
    typedef ???? difference_type; //almost always ptrdiff_t
    typedef ???? value_type; //almost always T
    typedef ???? reference; //almost always T& or const T&
    typedef ???? pointer; //almost always T* or const T*
    typedef ???? iterator_category;  //usually std::forward_iterator_tag or similar
};

Note the iterator_category should be one of std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, or std::random_access_iterator_tag, depending on which requirements your iterator satisfies. Depending on your iterator, you may choose to specialize std::next, std::prev, std::advance, and std::distance as well, but this is rarely needed. In extremely rare cases you may wish to specialize std::begin and std::end.

Your container should probably also have a const_iterator, which is a (possibly mutable) iterator to constant data that is similar to your iterator except it should be implicitly constructable from a iterator and users should be unable to modify the data. It is common for its internal pointer to be a pointer to non-constant data, and have iterator inherit from const_iterator so as to minimize code duplication.

My post at Writing your own STL Container has a more complete container/iterator prototype.

Iterator of associative container is not dependent on Comparator template argument

The standard library implementations are well within their rights to do this, and it was nearly made mandatory. The effect you're seeing is known as SCARY iterators and it's a good thing.

You would have to wrap the iterator in a custom struct- effectively tag them with your own custom type to use OR in this way.

Is it safe to hold pointers to iterators in C++?

Iterators are generally handled by value. For instance, begin() and end() will return an instance of type iterator (for the given iterator type), not iterator& so they return copies of a value every time.

You can of course take an address to this copy but you cannot expect that a new call to begin() or end() will return an object with the same address, and the address is only valid as long as you hold on to the iterator object yourself.

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

// This is fine:
auto it = x.begin();
auto* pi = ⁢

// This is not (dangling pointer):
auto* pi2 = &x.begin();

It rarely makes sense to maintain pointers to iterators: iterators are already lightweight handles to data. A further indirection is usually a sign of poor design. In your example in particular the pointers make no sense. Just pass a normal iterator.

---

Related Topics