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

Question

I understand that using const and & and all the other fancy C++ stuff is to, as I heard Bjarne Stroustrup say in a video, "help the compiler." I understand how using & (references) whenever possible can help make the program more efficient, but one thing I don't understand is how const_iterator helps at all. Suppose I use

#include <string>
#include <iostream>

int main()
{
    const std::string s = "Vote for Pat Buchanan in 2016";
    for (std::string::const_iterator i1(s.cbegin()), i2(s.cend()); i1 != i2; ++i1) 
        std::cout << *i1 << std::endl;

    return 0;
}

instead of

#include <string>
#include <iostream>

int main()
{
    const std::string s = "Vote for Pat Buchanan in 2016";
    for (std::string::iterator i1(s.begin()), i2(s.end()); i1 != i2; ++i1) 
        std::cout << *i1 << std::endl;

    return 0;
}

Both are valid. How would the former be more efficient? How does iterating through a string with a const_iterator go any faster than iterating through a string with a regular iterator? Aren't they the same data structure? 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?

For instance, if I wrote my own string class StringCool that used nodes

node
{
    char c;
    node * next, * previous;
}

to iterate through it, I don't see why I would need a different kind of node to iterate through constant instances of StringCool. The only thing different about the constant version of a StringCool instance is that the class would disallow writing. I could give it a node with fields

const char c;
const node * next, * previous;

but I don't see how iterating through a linked list of such nodes would be any faster.

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

Did Stroustrup actually say `const_iterator` is more efficient, or are you extrapolating? — Jonathan Wakely, Nov 21 '14 at 14:54

Jonathan Wakely · Accepted Answer · 2014-11-21T15:09:03.900

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.

But then again, the question isn't about type safety and immutability at all. — Bartek Banachewicz, Nov 21 '14 at 14:59
The question is about `const_iterator` so it is indirectly about type safety immutability. — Jonathan Wakely, Nov 21 '14 at 15:01

score 0 · Answer 2 · answered Nov 21 '14 at 14:55

0

Because a compiler can assume you won't modify its contents and i.e. cache it differently. Sometimes this means avoiding a copy, for example.

Related answer: Yes, by the means of const-qualifier on class member functions' overloads.

answered Nov 21 '14 at 14:55

Bartek Banachewicz

38,596
7
91
135

I might have misunderstood "define what happens" - please comment and tell me if that's the case. – Bartek Banachewicz Nov 21 '14 at 14:58
1

In most cases it's very difficult for compiler to prove that the object isn't changed, it can only prove that the object isn't changed trough the given iterator. Moreover, it even can be changed through the iterator using const_cast (it's legal except of the object is initially defined as const) – user396672 Nov 21 '14 at 15:09

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

2 Answers2