Eric Niebler gives in his recent blog post insights about iterators

To Be or Not To Be (an Iterator)

by Eric Niebler

From the article:

Way back in 1999, when the ink on the first C++ standard was still damp, Herb Sutter posed a GoTW puzzler in the still extant C++ Report (RIP): When Is a Container Not a Container? In that article, Herb described the problems of the now-infamous vector<bool>. According to the standard’s own container requirements, vector<bool> is not a container.

In a nutshell, it’s because vector<bool>‘s iterators claim to be random-access, but they’re not. Random-access iterators, when you dereference them, must return a real reference. They can only do that if the thing they point to really exists somewhere. But the bool that a vector<bool>::iterator points to does not exist anywhere. It’s actually a bit in a packed integer, and dereferencing a vector<bool>‘s iterator returns an object of some type that merely acts like a bool& without actually being a bool&.