Last updated：2026-10-12
STL map and multimap¶
map/multimap use rb_tree as their underlying structure, and therefore have the characteristic of automatic element sorting, with sorting based on the key.
map/multimap provide "traversal" operations and iterators. Traversing by the normal rules (++iter) yields the sorted order.
We cannot use map/multimap iterators to change an element's key (because the key has its strict ordering rules), but we can use them to change the element's data. Therefore map/multimap internally automatically sets the user-specified key type to const, thereby forbidding users from assigning to an element's key.
The key of a map element must be unique, so its insert uses the rb_tree's _M_insert_unique(), while the key of a multimap element may repeat, so its insert uses the rb_tree's _M_insert_equal().
In this section we will cover the following:
- map's key is the key and its value is key+data, which differs from set, where the key is the value and the value is the key.
- map's key cannot be modified; map and multimap call different insertion functions, which affects whether a key maps to multiple values.
- initializer_list usage
- map has the
[]operator, while multimap does not have a[]operator.
1.map¶
the key is the key, the value is key+data
In the map below we can see that value_type is a pair.
template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{
public:
typedef _Key key_type;
typedef _Tp mapped_type;
typedef std::pair<const _Key, _Tp> value_type;
typedef _Compare key_compare;
typedef _Alloc allocator_type;
private:
// key为key,value为key+data
typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
key_compare, _Pair_alloc_type> _Rep_type;
/// The actual tree structure.
_Rep_type _M_t;
};
The default functor above is _Select1st; in stl_function we see the following source:
template<typename _Pair>
struct _Select1st
: public unary_function<_Pair, typename _Pair::first_type>
{
typename _Pair::first_type&
operator()(_Pair& __x) const
{ return __x.first; }
};
_Select1st above is a struct — how can we call it a functor?
Because it overloads a () operator, haha~
Now let's implement one ourselves:
template<typename _T1>
struct mySelect1st
: public unary_function<_T1, typename _T1::first_type>
{
template<typename _T2>
typename _T2::first_type&
operator()(_T2& __x) const
{ return __x.first; }
};
int main() {
typedef pair<const int,int> value_type;
_Rb_tree<int, value_type, mySelect1st<value_type>, less<int>> it;
it._M_insert_unique(make_pair(1,3));
it._M_insert_unique(make_pair(3,6));
for(auto each:it)
cout<<each.first<<" "<<each.second<<endl;
}
the key cannot be modified, the data can
In the source above, a const is automatically added to the key, so the key cannot be modified.
2.insert¶
insert uses
_M_insert_unique
The several insert methods:
(1) Insert a pair
inside map
(2) Insert a pair at a specified position
iterator insert(iterator __position, const value_type& __x)
{ return _M_t._M_insert_equal_(__position, __x); }
(3) Insert from a range
template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_t._M_insert_equal(__first, __last); }
For the last insert, there is an initializer_list; an example will make it clear.
3.initializer_list usage¶
Hands-on practice
vector<int> v={1,2,3}; // 底层调用vector的构造函数
v={2,5,6}; // 底层调用vector的=操作符
initializer_list<int> ll={4,5,6};
v.insert(v.begin(),ll); // 底层调用下面insert函数
for(auto x:v) cout<<x<<" ";
cout<<endl;
vector<int> vv(ll); // 底层调用vector的构造函数
vector<string> city{"Berlin", "New York", "London", "Cairo","Tokyo", "Cologne"};
vector&
operator=(initializer_list<value_type> __l)
{
this->assign(__l.begin(), __l.end());
return *this;
}
iterator
insert(const_iterator __position, initializer_list<value_type> __l)
{ return this->insert(__position, __l.begin(), __l.end()); }
vector(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__l.begin(), __l.end(),
random_access_iterator_tag());
}
Because its constructor has an initializer_list parameter, we can apply this to map.
But map has no analogous constructor; it is applied in map's constructor, insert, and = — the same three places as above, haha~
Three places where initializer_list is used:
// map构造
map(initializer_list<value_type> __l, const allocator_type& __a)
: _M_t(_Compare(), _Pair_alloc_type(__a))
{ _M_t._M_insert_unique(__l.begin(), __l.end()); }
// =操作符重载
map&
operator=(initializer_list<value_type> __l)
{
this->clear();
this->insert(__l.begin(), __l.end());
return *this;
}
// insert插入
void
insert(std::initializer_list<value_type> __list)
{ insert(__list.begin(), __list.end()); }
Hands-on practice
Using initializer_list with map (used the same way with set):
// 这里要注意，pair的first参数必[须是const
initializer_list<pair<const strin[g,int>> l = {{"hello", 1}, {"world", 2}};
map<string,int> mm(l); // map构造函数
map<string, int> m2{{"hello", 1}, {"world", 2}}; // map构造函数
map<string, int> m1={{"hello", 1}, {"world", 2}}; // map构造函数
m1 = {{"h", 1}, {"w", 3}}; // 底层调用map的=操作符
map<string, int> mp;
mp.insert(l); // insert插入[
map<string, int> m1={{"hello", 1}, {"world", 2}}; // map构造函数
m1 = {{"h", 1}, {"w", 3}}; // 底层调用map的=操作符
At initialization time, when defining and assigning in one go, the constructor is called directly; a later re-assignment first calls the copy constructor (which may be optimized away by the compiler) and then the = operator.
Example analysis
Let's analyze it with a concrete example:
template <typename _Tp>
class Foo
{
public:
Foo(initializer_list<_Tp> &list)
{
cout << "Foo(initializer_list<_Tp> &list)"<< endl;
}
Foo(int)
{
cout << "Foo(int )"<< endl;
}
Foo(const Foo& f)
{
cout << "调用了拷贝构造函数"<< endl;
}
Foo& operator=(initializer_list<_Tp> __l)
{
cout<<"调用了=操作符重载"<<endl;
return *this;
}
};
g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors
4.multimap¶
Like map, multimap does not allow modifying the key. But its insertion uses _M_insert_equal.
template <typename _Key, typename _Tp,
typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class multimap
{
public:
typedef std::pair<const _Key, _Tp> value_type;
}
multimap<int, string> c;
c.insert(make_pair(1,"asdqw"));
c.insert(make_pair(1,"qweq"));
for(auto each:c) cout<<each.first<<" "<<each.second<<endl;
typedef pair<const int,string> valueT;
_Rb_tree<int, valueT, _Select1st<valueT>, less<int>> mulm;
mulm._M_insert_equal(make_pair(2,"abc"));
mulm._M_insert_equal(make_pair(2,"cde"));
for(auto each:mulm)
cout<<each.first<<" "<<each.second<<endl;
5.Important operators of map and multimap¶
For the [] operator of map and multimap: map's [] operator returns the second parameter passed to the map.
Pass a key to []; if it is found, you get the value, otherwise the default value 0.
mapped_type&
operator[](const key_type& __k)
{
iterator __i = lower_bound(__k);// 找到__k第一个。
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first))
#if __cplusplus >= 201103L
__i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
std::tuple<const key_type&>(__k),
std::tuple<>());
#else
__i = insert(__i, value_type(__k, mapped_type()));
#endif
return (*__i).second; // 返回key的value，此value为传递进map的第二个参数。
}
But multimap has no [] operator!!!
Let's think about it: since a multimap key may correspond to multiple values, if we fetched the value for a key via [], which value would we actually get? That is why the STL source code does not overload this operator!
Related Topics¶
- STL array source code analysis | C++那些事
- STL string deep dive | C++那些事
- STL string interview questions in depth | C++那些事
- STL deque source code analysis | C++那些事
- STL empty base optimization EBO | C++那些事
- STL hand-written hash table implementation | C++那些事
- STL hashtable hash table | C++那些事
- STL iterator source code analysis | C++那些事
- STL list source code analysis | C++那些事
- STL queue and stack source code analysis | C++那些事