Перейти к содержанию

Последнее обновление：2026-10-12

STL map и multimap

map/multimap построены на базе rb_tree, поэтому обладают свойством автоматической сортировки элементов; основой сортировки служит key.

map/multimap предоставляют операцию «обхода» и iterators. При обходе по обычным правилам (++iter) элементы получаются в отсортированном виде.

Мы не можем изменять key элементов с помощью iterators map/multimap (поскольку key подчиняется своим строгим правилам упорядочивания), но можем с их помощью изменять data элементов. Поэтому внутри map/multimap автоматически делает указанный пользователем key type константой, тем самым запрещая присваивание элементам key.

key элемента map должен быть уникальным, поэтому его insert использует _M_insert_unique() из rb_tree, тогда как key элемента multimap может повторяться, и его insert использует _M_insert_equal() из rb_tree.

В этом разделе мы разберём следующие моменты:

  • у map key — это key, а value — это key+data, что отличает его от set, где key — это value, а value — это key.
  • key в map неизменяем; map и multimap вызывают разные функции вставки, что и определяет, сопоставляется ли key с value.
  • использование initializer_list
  • у map есть оператор [], а у multimap оператора [] нет.

1. map

key — это key, value — это key+data

В приведённом ниже map мы видим, что value_type — это 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;
};
map_data.png

Указанный выше функтор по умолчанию — _Select1st; в stl_function мы видим такие исходники:

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 — это struct; как же можно называть его функтором? Потому что внутри перегружен оператор (), ха-ха~

Теперь реализуем свой:

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;
}

key нельзя менять, data — можно

В приведённых исходниках: к key автоматически добавляется const, поэтому key изменить нельзя. 

typedef std::pair<const _Key, _Tp>                    value_type;

2. insert

внутри insert используется _M_insert_unique

Несколько способов insert:

（1） вставка pair

std::pair<iterator, bool> insert(const value_type& __x)
{ return _M_t._M_insert_unique(__x); }

внутри map

（2） вставка pair в указанную позицию 

iterator insert(iterator __position, const value_type& __x)
{ return _M_t._M_insert_equal_(__position, __x); }

（3） вставка из диапазона

template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_t._M_insert_equal(__first, __last); }
（4） вставка из list

void
insert(initializer_list<value_type> __l)
{ this->insert(__l.begin(), __l.end()); }

В последнем insert есть initializer_list — пример, и всем всё станет ясно.

3. Использование initializer_list

Практика реального программирования

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 подобным образом всем хорошо знакома — почему так можно инициализировать? Взглянем на исходники vector:

 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());
}

Поскольку среди параметров его конструктора есть initializer_list, мы можем использовать это и для map. Впрочем, у map нет аналогичного конструктора — initializer_list применяется в конструкторе map, в insert и в =, то есть в тех же трёх местах, ха-ха~

Три места использования initializer_list:

// 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()); }

Практика реального программирования

Использование initializer_list в map (в 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的=操作符
Почему в этих двух случаях один вызов — конструктора, а другой — оператора =?

При инициализации, в момент определения с присваиванием, вызывается сразу конструктор; при последующем повторном присваивании сначала вызывается копирующий конструктор (который компилятор может оптимизировать), а затем оператор =.

Разбор примера

Разберём на конкретном примере:

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;
    }

};
Вызов: 
Foo<int> foo=ll;
foo={1,2};
Результат без оптимизации компилятора:

Foo(initializer_list<_Tp> &list)
调用了=操作符重载
Мы отключили оптимизацию компилятора: g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors

Foo(initializer_list<_Tp> &list)
调用了拷贝构造函数
调用了=操作符重载

4. multimap

Как и map, multimap не позволяет изменять key. Но вставка использует _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 и rbtree. 
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;
Вывод:

1 asdqw
1 qweq
2 abc
2 cde

5. Важные операторы map и multimap

Оператор [] у map и multimap: оператор [] у map возвращает второй параметр, переданный в map.

Передайте оператору [] key: если он найден, получите 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的第二个参数。
}

А вот у multimap оператора [] нет!!!

Подумаем: multimap по одному key может содержать несколько value — если мы попытаемся через [] получить value для key, какой именно value мы получим? Поэтому в исходниках STL этот оператор не перегружен!

Похожие темы

Комментарии