Are Const_Iterators Faster

Are const_iterators faster?

If nothing else, a const_iterator reads better, since it tells anyone reading the code "I'm just iterating over this container, not messing with the objects contained".

That's a great big win, never mind any performance differences.

Should I prefer iterators over const_iterators?

I totally agree with you.
I think the answer is simple:
Use const_iterators where const values are the right thing to use, and vice versa.
Seems to me that those who are against const_iterators must be against const in general...

Different efficiency of iterator and const_iterator (STL)

The documentation says that these const_iterators should be used whenever possible since they are faster.

It sure does. From http://qt-project.org/doc/qt-4.8/containers.html#stl-style-iterators:

For each container class, there are two STL-style iterator types: one that provides read-only access and one that provides read-write access. Read-only iterators should be used wherever possible because they are faster than read-write iterators.

What a stupid thing to say.

Safer? Yes. Faster? Even if this were the case (it apparently isn't with gcc and clang), it is rarely a reason to prefer const iterators over non-const ones. This is premature optimization. The reason to prefer const iterators over non-const ones is safety. If you don't need the pointed-to contents to be modified, use a const iterator. Think of what some maintenance programmer will do to your code.

As far as begin versus cbegin is concerned, that's a C++11 addition. This allows the auto keyword to use a const iterator, even in a non-const setting.

How does using const_iterator result in the compilation of a more efficient program?

const_iterator doesn't exist to make programs faster, it exists for type-safety. If you want to allow code to iterate over your container but you want to be sure it won't modify the contents, you can give that code const_iterators.

Why would you need separate data structures for iterating through a container that is constant throughout a program, as opposed to iterating through a container that is non-constant?

You don't necessarily need const_iterator to just iterate over a container, but having separate iterators types allows you to express your intentions better. If you want to iterate without changing anything, using a const_iterator makes that intention explicit.

If I have an array of int I could pass int* to functions that want to access it, but if I want to ensure the functions don't modify the array elements I would pass const int* instead. And if I have an array of const int then I must pass const int* because I can't get a non-const int* to the array without using a questionable (and possibly dangerous) cast.

You can use a const_iterator (or its equivalent) to perform non-modifying traversals of const or non-const objects. You can only use a mutable iterator to traverse non-const objects, to prevent you attempting to modify elements of a const container.

Related question: When creating classes in C++, is it possible to define what happens when an instance of the class is declared const?

No, the same constructor is called whether the object is declared const or not, and the type of *this is always non-const during the constructor.

What is the difference between const_iterator and non-const iterator in the C++ STL?

const_iterators don't allow you to change the values that they point to, regular iterators do.

As with all things in C++, always prefer const, unless there's a good reason to use regular iterators (i.e. you want to use the fact that they're not const to change the pointed-to value).

Why does Scott Meyers recommend to prefer `iterator` to `const_iterator`

The short answer is that Meyers does consider const_iterators preferable when using an up-to-date implementation of the STL due to improvements made in the C++11 standard.

Before discussing his reasons for giving the anti-const_iterator advice in the first place and explaining what changed, though, I need to clear up a misconception. You write:

isn't that the whole point of a const_iterator, that it does not allow modifying the container?

This is a sensible assumption, but in fact this is not quite the purpose of const_iterator. As Meyers explains in the third edition of Effective C++ (written, notably, before C++11):

Declaring an iterator const is like declaring a pointer const (i.e., declaring a T* const pointer): the iterator isn't allowed to point to something different, but the thing it points to may be modified. If you want an iterator that points to something that can't be modified (i.e., the STL analogue of a const T* pointer), you want a const_iterator[.]

In short, const_iterator doesn't protect against modifying the container, it protects against modifying the contained values. This is why Meyers expects insertto be compatible with const_iterator: it doesn't modify any of the elements already present in the container.

erase is a bit stranger, because it causes a contained element to be destroyed, which is a non-const operation. But note that the element's destructor is not called via the iterator itself; the iterator is merely the means the API provides to specify the item to be erased. Semantically, a const_iterator should be able to serve this purpose as well as an an iterator.

---

Now, as for the advice in Effective STL and its subsequent retraction, I'll paraphrase and quote some of Effective Modern C++ on the matter. In Item 13, "Prefer const_iterators to iterators", Meyers writes:

...in C++98, const_iterators had only halfhearted support. It wasn't that easy to create them, and once you had one, the ways you could use it were limited....

...there was no simple way to get a const_iterator from a non-const container...

Once you had the const_iterators...locations for insertions (and erasures) could be specified only by iterators. const_iterators weren't acceptable.

He gives an example making extensive use of static_cast to get around these limitations, but points out,

...the code I've shown might not compile, either, because there's no portable conversion from a const_iterator to an iterator, not even with a static_cast. Even the semantic sledgehammer known as reinterpret_cast can't do the job.

He summarizes:

...const_iterators were so much trouble in C++98, they were rarely worth the bother.

These issues were addressed by the C++11 standard. As alluded to in a comment on your question, this standard introduced cbegin and cend, which return const_iterator regardless of whether the container itself is const. Also, insert and erase were given overloads taking const_iterator. This makes const_iterator much easier to use.

Speed accessing a std::vector by iterator vs by operator[]/index?

The performance difference is likely negligable or none (the compiler might optimise them to be identical); you should worry about other things, like whether your program is correct (a slow but correct program is better than a fast and incorrect program). There are other advantages to using iterators though, such as being able to change the underlying container to one with no operator[] without modifying your loops. See this question for more.

const_iterators will most likely have none, or negligable, performance difference compared to ordinary iterators. They are designed to improve the correctness of your program by preventing modifying things that shouldn't be modified, not for performance. The same goes for the const keyword in general.

In short, optimisation should not be a concern of yours until two things have happened: 1) you have noticed it runs too slowly and 2) you have profiled the bottlenecks. For 1), if it ran ten times slower than it could, but is only ever run once and takes 0.1ms, who cares? For 2), make sure it's definitely the bottleneck, otherwise optimising it will have nearly no measurable effect on performance!

How to remove constness of const_iterator?

There is a solution with constant time complexity in C++11: for any sequence, associative, or unordered associative container (including all of the Standard Library containers), you can call the range-erase member function with an empty range:

template <typename Container, typename ConstIterator>
typename Container::iterator remove_constness(Container& c, ConstIterator it)
{
    return c.erase(it, it);
}

The range-erase member functions have a pair of const_iterator parameters, but they return an iterator. Because an empty range is provided, the call to erase does not change the contents of the container.

Hat tip to Howard Hinnant and Jon Kalb for this trick.

How const_iterators are implemented?

How the const_iterators are implemented for example in the STL containers?

You can probably look in your implementation's header files to see how they chose to do it. It will depend on the container type and its internal data structure. But the common pattern I've seen is that there's some private template that can take either non-const T or const T, and that will be used as a base or member of the actual distinct iterator types. One catch is that a specific type from the data structure needs to be used, independently of the type the iterator classes expose. In your example, Node<T> and Node<const T> are not interoperable, so SomeComonFunctionsBetweenIterators could work, but should probably have the node type as a template argument independent of the value type T.

But for an easy way to define iterator types, I always turn to Boost.Iterator's iterator_facade or iterator_adaptor. They take care of a lot of the technical requirements about iterators, letting the author just fill in the behavioral bits. iterator_facade is for implementing something "from scratch", and iterator_adaptor is for the common case of an iterator that contains and wraps another iterator.

The Boost documentation for iterator_facade discusses a way to define related iterator and const_iterator types. (Though their decision to make the iterators interoperable as long as the pointers can convert probably wouldn't be appropriate for iterators from containers.)

Using iterator_facade will also give a bunch of things algorithms may expect of iterators but missing from your code shown, like making std::iterator_traits work, equality and inequality, and other fiddly details.

#include <boost/iterator/iterator_facade.hpp>
#include <type_traits>

template <typename T>
struct Node
{
    T value;
    Node* next;
};

template <typename NodeType, typename ValueType, typename ContainerType>
class TLinkedListIterator :
    public boost::iterator_facade<
        TLinkedListIterator<NodeType, ValueType, ContainerType>, // CRTP Derived type
        ValueType,                  // Iterator's value_type
        std::forward_iterator_tag   // Category
    >
{
public:
    TLinkedListIterator() : m_node(nullptr) {}

protected:
    explicit TLinkedListIterator(NodeType* node) : m_node(node) {}

private:
    friend boost::iterator_core_access;
    friend ContainerType;
    template <typename N, typename V, typename C> friend class TLinkedListIterator;

    ValueType& dereference() const { return m_node->value; }
    void increment() { m_node = m_node->next; }

    // Templating allows comparison between iterator and const_iterator
    // in any combination.
    template <typename OtherValueType>
    bool equal(const TLinkedListIterator<NodeType, OtherValueType, ContainerType>& iter)
    { return m_node == iter.m_node; }

    NodeType m_node;
};

template <typename T>
class LinkedList
{
public:
    using iterator = TLinkedListIterator<Node<T>, T, LinkedList>;

    class const_iterator
        : public TLinkedListIterator<Node<T>, const T, LinkedList>
    {
    private:
        using BaseType = TLinkedListIterator<Node<T>, const T, LinkedList>;
    public:
        const_iterator() = default;

        // Converting constructor for implicit conversion from iterator
        // to const_iterator:
        const_iterator(const iterator& iter)
            : BaseType(iter.m_node) {}

    protected:
        explicit const_iterator(Node<T>* node)
            : BaseType(node) {}

        friend LinkedList<T>;
    };

    iterator begin() { return iterator(get_head()); }
    iterator end() { return iterator(); }
    const_iterator begin() const { return const_iterator(get_head()); }
    const_iterator end() const { return const_iterator(); }
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }

    // ...
};

---

Related Topics