コンテンツにスキップ

最終更新：2026-10-12

STL map と multimap

map/multimap はrb_treeを基盤構造とするため、要素が自動的にソートされる特徴があり、ソートの基準はkeyです。

map/multimapは「走査」操作とiteratorsを提供します。正常な規則（++iter）で走査すれば、ソートされた状態を得ることができます。

map/multimapのiteratorsを使って要素のkeyを変更することはできません（keyには厳格な整列規則があるためです）が、要素のdataを変更することはできます。そのためmap/multimapの内部では、ユーザーが指定したkey typeを自動的にconstに設定し、ユーザーによる要素のkeyへの代入を禁止しています。

map要素のkeyは一意でなければならないため、そのinsertにはrb_treeの_M_insert_unique()が使われます。一方、multimap要素のkeyは重複できるため、そのinsertにはrb_treeの_M_insert_equal()が使われます。

本節では、以下の内容を述べていきます：

  • mapのkeyはkey、valueはkey+dataであり、setとは異なります。setはkeyこそがvalue、valueこそがkeyです。
  • mapのkeyは変更できず、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には同様のコンストラクタはなく、mapのコンストラクタ、insert、=の3箇所で使われています。上と同じく3箇所です、哈哈～

initializer_listを使う3箇所：

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

実際のプログラミング実践

mapでのinitializer_listの使用（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的=操作符
この2つはなぜ片方はコンストラクタを呼び、片方は=演算子を呼ぶのでしょうか？

初期化のとき、定義と代入を同時に行うと直接コンストラクタが呼ばれ、後で再び代入すると、まずコピーコンストラクタが呼ばれ（コンパイラによって最適化される可能性があります）、その後=演算子が呼ばれます。

実例分析

次の具体的な例で分析してみましょう：

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の2つの方式で練習します。 
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に渡された第2引数を返します。

[]に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が対応する可能性があります。もし[]で対応するkeyのvalueを取得するとしたら、いったいどのvalueを取得するのでしょうか。そのため、STLのソースコードではこの演算子はオーバーロードされていないのです！

関連トピック

コメント