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.

The guideline we use is:

Always prefer const over non-const

If you tend to use const object, you get used to using only constant operations on the objects you get and that is as much as using const_iterator as much as possible.

Constness has a viral property. Once you get to use it, it propagates to all your code. Your non-mutating methods become constant, and that requires using only constant operations on the attributes, and passing constant references around, that itself forces only constant operations...

To me, the performance advantage of using constant iterators over non constant iterators (if any at all) is much less important than the improvement in the code itself. Operations meant (designed) to be non-mutating are constant.

They are for non-trivial containers/iterators. Get your habits straight and you won't lose performance when it does matter.

Also, there are several reasons to prefer const_iterator, no matter what:

1. Use of const expresses code intent (i.e. reading only, no mutating of these objects).
2. Use of const(_iterator) prevents accidental modification of data. (see above)
3. Some libraries use lack-of-const begin() to flag data as dirty (i.e. OpenSG) and will send it to other threads/over-network on sync, so there it has real performance implications.
4. Also, allowing you to access non-const member functions could have side-effects that you don't intend (in much the same way as above), for instance detaching copy-on-write containers from shared data. Qt for one, does exactly that.

As an example of the last point above, here's an excerpt from qmap.h in Qt:

inline iterator begin() { detach(); return iterator(e->forward[0]); }
inline const_iterator begin() const { return const_iterator(e->forward[0]); }

Even if iterator and const_iterator are practically equivalent (except for the const), detach() creates a new copy of the data if there are two or more objects using it. This is completely useless if you're just going to read the data, which you indicate by using const_iterator.

Of course, there are data points in the other direction:

1. For STL containers and and many simple-copy-semantic containers it won't matter for performance. The code is equivalent. However, the able to write clear code and avoid bugs wins out.
2. Const is viral, so if you're working in a legacy code base where const is poorly (or simply not) implemented, you might have to work with non-const iterators.
3. Apparently, some pre C++0x STL has a bug where const_iterators couldn't be used to erase() elements from containers.

I can't see why they would be - constness is a compile time check. But the obvious answer is to write a test.

Edit: Here is my test - it gives identical timings on my machine:

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;;


int main() {
    vector <int> v;
    const int BIG = 10000000;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }
    cout << "begin\n";
    int n = 0;
    time_t now = time(0);
    for ( int a = 0; a < 10; a++ ) {
        for( vector <int>::iterator it = v.begin(); it != v.end(); ++it ) {
            n += *it;
        }
    }
    cout << time(0) - now << "\n";
    now = time(0);
    for ( int a = 0; a < 10; a++ ) {
        for( vector <int>::const_iterator cit = v.begin(); cit != v.end(); ++cit ) {
            n += *cit;
        }
    }
    cout << time(0) - now << "\n";;

    return n != 0;

}

It depends on the container and implementation you use.

Yes, const_iterator may perform better.

For some containers the implementation of const iterators and mutable iterators may differ. A first example I can think of is the SGI's STL rope container. The mutable iterator has additional pointer to the parent rope in order to support updates. This implies additional resources wasted for reference counting updates + memory for the pointer to the parent rope. See the implementation notes here.

However, as others said, the compiler cannot use const by itself to do optimization. const just grants read-only access to the referenced object rather than saying that it is immutable. For a container like std::vector, whose iterators are usually implemented as a simple pointers, there won't be any difference.