Advanced Minds

I am reading David Musser's STL Tutorial and Reference Guide Second Edition. In that book, on pages 68-69, definition has been given that an iterator can be mutable or constant depending on whether the result of operator* is a reference or a constant reference. As per this definition, on page 71 in this book, it is mentioned that for 'set' and 'multiset', both the iterator and const_iterator types are constant bidirectional types - in fact they are the same type. The reason given in this book is as follows: set<int s; s.insert(3); s.insert(5); s.insert(7); set<int::iterator i = s.begin(); *i = 4; // incorrect On page 72, it is given that for container set<T, set<T::iterator is constant bidirectional iterator category and for container multiset<T, multiset<T::iterator is constant bidirectional iterator category. My understanding: Along the same above discussion, shouldn't map<Key, T::iterator and multimap<Key, T::iterator also be constant bidirectional iterators ? (This is what I expected because for both set, multiset, map, multimap, the key is constant) However in this book, it is mentioned that for container map<Key, T, map<Key, T::iterator is mutable bidirectional iterator category and for container multimap<Key, T, multimap<Key, T::iterator is mutable bidirectional iterator category. Is this correct? Is my understanding wrong ? Kindly clarify. Thanks V.Subramanian

I am reading David Musser's STL Tutorial and Reference Guide Second Edition. In that book, on pages 68-69, definition has been given that an iterator can be mutable or constant depending on whether the result of operator* is a reference or a constant reference. As per this definition, on page 71 in this book, it is mentioned that for 'set' and 'multiset', both the iterator and const_iterator types are constant bidirectional types - in fact they are the same type. The reason given in this book is as follows: set<int s; s.insert(3); s.insert(5); s.insert(7); set<int::iterator i = s.begin(); *i = 4; // incorrect On page 72, it is given that for container set<T, set<T::iterator is constant bidirectional iterator category and for container multiset<T, multiset<T::iterator is constant bidirectional iterator category. My understanding: Along the same above discussion, shouldn't map<Key, T::iterator and multimap<Key, T::iterator also be constant bidirectional iterators ? (This is what I expected because for both set, multiset, map, multimap, the key is constant) No, the key may be constant, but the value is mutable.

My understanding: Along the same above discussion, shouldn't map<Key, T::iterator and multimap<Key, T::iterator also be constant bidirectional iterators ? (This is what I expected because for both set, multiset, map, multimap, the key is constant) No, the key may be constant, but the value is mutable. The salient difference between a std::map and a std:et is that each value stored in a std:et is also a key. So the reason why values stored in a std:et are immutable - is because the std:et's keys are immutable (to ensure a proper order). But since the std:et's keys and its values are one and the same, it follows that a std:et's values are immutable because they are also keys.. With a std::map, the values are distinct from their keys - so although the keys in a std::map are immutable, the values in a map need not be. Because - unlike a std:et - changing a value stored in a std::map will not affect the sorted order of the container. Greg

My understanding: Along the same above discussion, shouldn't map<Key, T::iterator and multimap<Key, T::iterator also be constant bidirectional iterators ? (This is what I expected because for both set, multiset, map, multimap, the key is constant) However in this book, it is mentioned that for container map<Key, T, map<Key, T::iterator is mutable bidirectional iterator category and for container multimap<Key, T, multimap<Key, T::iterator is mutable bidirectional iterator category. Is this correct? Is my understanding wrong ? Kindly clarify. To add some more info to what Ian and Greg already told you, each standard container has a nested typedef named value_type which represents the type of the values stored in the container (and the iterator are just like pointers to value_type , so when you dereference an iterator you get either a value_type& or a value_type const& depending if it is a mutable iterator or not). std:et<Key defines value_type to be Key so the fact that both iterator and const_iterator operator* return value_type const& means both iterator types are not mutable. However, for std::map<Key, Value, value_type is std:air<Key const, Value (that's why you need all those iter-second _expression_s to refer to the pointed to value) and const_iterator::operator* returns a value_type const& while iterator::operator* returns a value_type& so technically the later is a mutable iterator while the former is not. But, even so, you cannot change the Key pointed to by an mutable map iterator because the mutable iterator will just give you access to a std:air<Key const, Value& so you cannot modify the Key part of the pair. Which means that while technically map<Key, Value::iterator is a mutable iterator, logically it is semi-mutable because it allows you mutable access only to the value part.