Differencebetween Const_Iterator and Non-Const Iterator in the C++ Stl

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).

what is the difference between const_iterator and iterator?

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.)

In C++, is const_iterator the same as const iterator?

No, they are not the same.

Like any const object, you can not make changes to a const iterator:

// ++it gives error below since we try to change it:
for(const std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {}

You are, however, allowed to change the value of the object a const iterator is pointing at:

// this is ok (assuming there is at least one element in the vector):
const std::vector<int>::iterator it = vec.begin();
*it = 10;

A const_iterator is mutable, but you can not change the object that the iterator is pointing at:

// ++it is ok below:
for(std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it) {
    *it = 10;   // error:  `*it`  is an `int const&`
}

With a const const_iterator, you can neither make changes to the iterator nor what it is pointing at.

const std::vector<int>::const_iterator it = vec.begin();
++it;                     // error
*it = 10;                 // error
std::cout << *it << '\n'; // ok

A constructed example to illustrate:

struct foo {
    using const_iterator = char const*;
    using iterator = char*;

    const_iterator cbegin() const { return data; };
    const_iterator cend() const { return data + sizeof data; };
    const_iterator begin() const { return cbegin(); }
    const_iterator end() const { return cend(); }
    iterator begin() { return data; };
    iterator end() { return data + sizeof data; };

    char data[2];
};

As seen above, const_iterator and iterator are user defined type definitions. Only by convention are the names called what they are called. Using these conventional names also helpes when creating containers that are supposed to work well with other classes, since these type definitions are often used to create or specify instances/types. The names const_iterator and iterator do not give these alias any special properties though. It's all up to the creator of the class.

const_iterator vs iterator for std::list

You are missing a few things described below, and the class is not "templetized" yet, but the approach is the same as what one implementation of the Standard Template Library is using.

Both iterators need a default constructor - this provides a way to make a null iterator, which you can assign later
const_iterator must be constructible from iterator - Add a constructor to const_iterator to accept "regular" iterator.

As far as code duplication is concerned, this is a fair observation indeed. However, most implementations fit on a single line, and return different types, so trying to share implementations across the two templates would make the code harder to read.

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.

Does const containers have only const iterator?

Suppose you have

iterator begin() const;

instead of

const_iterator begin() const;

Now, think what happens when you have

const vector<Foo> v;

You will be able to do something like

*v.begin() = other_foo;

which of course shouldn't be legal if you want to preserve logical const-ness. The solution is therefore to make the return type const_iterator whenever you invoke iterators on const instances.

The situation is similar to having const classes that have pointer members. In those cases, you may modify the data the pointer points to (but not the pointer itself), so logical const-ness is not preserved. The standard library took a step forward and disallowed these kind of modifications on standard containers via const overloads that return const_iterators.

const to non-const iterator comparisons, are they valid

Yes, this will work like you expect.

The Standard guarantees that for any container type, some_container::iterator can be implicitly converted to some_container::const_iterator.

The first table in 23.2.1 [container.requirements.general], after defining X as a container type which contains objects of type T, has:

Expression: X::iterator
Return type: iterator type whose value type is T
Note: any iterator category that meets the forward iterator requirements. convertible to X::const_iterator.
Expression: X::const_iterator
Return type: constant iterator type whose value type is T
Note: any iterator category that meets the forward iterator requirements.

(These aren't really expressions, and are types, rather than having "return types", but that's how they're squeezed into the table that is mostly expressions.)

So when you have ciObject2==iObject1, the compiler notices that the best operator== is ciObject2==some_container::const_iterator(iObject1). And operator== on two const_iterator tells you if they refer to the same element.

(I don't see anything explicitly saying that the result of this conversion refers to the same object as the original iterator. I guess that's just understood.)

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...

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.