what is the difference between const_iterator and iterator?

Question

What is difference between these two regarding implementation inside STL. what is the difference regarding performance? I guess when we are traversing the vector in "read only wise", we prefer const_iterator, right?

Thank you.

Solution 1

There is no performance difference.

A const_iterator is an iterator that points to const value (like a const T* pointer); dereferencing it returns a reference to a constant value (const T&) and prevents modification of the referenced value: it enforces const-correctness.

When you have a const reference to the container, you can only get a const_iterator.

Edited: I mentionned “The const_iterator returns constant pointers” which is not accurate, thanks to Brandon for pointing it out.

Edit: For COW objects, getting a non-const iterator (or dereferencing it) will probably trigger the copy. (Some obsolete and now disallowed implementations of std::string use COW.)

Solution 2

Performance wise there is no difference. The only purpose of having const_iterator over iterator is to manage the accessesibility of the container on which the respective iterator runs. You can understand it more clearly with an example:

std::vector<int> integers{ 3, 4, 56, 6, 778 };

If we were to read & write the members of a container we will use iterator:

for( std::vector<int>::iterator it = integers.begin() ; it != integers.end() ; ++it )
       {*it = 4;  std::cout << *it << std::endl; }

If we were to only read the members of the container integers you might wanna use const_iterator which doesn't allow to write or modify members of container.

for( std::vector<int>::const_iterator it = integers.begin() ; it != integers.end() ; ++it )
       { cout << *it << endl; }

NOTE: if you try to modify the content using *it in second case you will get an error because its read-only.

Solution 3

if you have a list a and then following statements

list<int>::iterator it; // declare an iterator
    list<int>::const_iterator cit; // declare an const iterator 
    it=a.begin();
    cit=a.begin();

you can change the contents of the element in the list using “it” but not “cit”, that is you can use “cit” for reading the contents not for updating the elements.

*it=*it+1;//returns no error
    *cit=*cit+1;//this will return error

Comments

[Brandon]

Correct, except (const T*) is not a constant pointer, it is a pointer to const.

[WiSaGaN]

There may be performance difference. Const iterator is a hint to the compiler so that it can assume the underlying object will not be changed through iterator manipulation. Compiler can use such hint to do more specific optimization.

[ysdx]

@WiSaGaN: I do not think it is true. The underlying object could very well change by some other way and I do not think the compiler is allowed to assume that the underlying object does not change (gotw.ca/gotw/081.htm).

[Michael]

I am not sure that there is no performance difference. Sometimes providing const-reference is much cheaper than providing a reference: in the latter case the container must be able to accept modification of the referenced value. In particularly, in (non-STL) copy-on-write containers the difference may be enormous. Ditto containers that trace changes.

[ysdx]

@Michal: Yes, Indeed. I was thinking about plain STL-ish containers. For COW containers (or assimilated), you should expect to have a significant cost of deduplication/state-tracking for getting or dereferencing non-const iterators.

[v.oddou]

@ysdx they do. simply they don't rely on C++ written const, they rely on their own "coloration" tags.

[ysdx]

@v.oddou: Do you have reference on this? Are you talking about Qt containers?

[v.oddou]

Yes, clang source code, llvm/IR/Attribues.h Attribute::AttrKind::ReadOnly the comment is Function only reads from memory. There are many of those coloration tags, they even merge and combine themselves hierarchically (i.e. they are call graph aware). The compiler is capable to know many things, for example if a function has no side effects... There is this nice doc about the optimizer passes here llvm.org/docs/Passes.html this gives a quick overview about stuff compilers are doing.

[mkl]

I think the OP was foremost interested in the difference regarding performance and was quite aware of the read-only character of the const_iterator.

[metamorphosis]

I can confirm that with colony (plf::colony) performance improvements were achieved simply via changing some internal code from iterator to const_iterator. The codegen size actually went Up when using const_iterator, but the resulting performance was greater.