C++
std :: map

備考

要素へのアクセス

std::mapは(key, value)ペアを入力として受け取ります。

次のstd::map初期化の例を考えてみましょう。

std::map < std::string, int > ranking { std::make_pair("stackoverflow", 2), 
                                        std::make_pair("docs-beta", 1) };

std::mapでは、要素を次のように挿入できます。

ranking["stackoverflow"]=2;
ranking["docs-beta"]=1;

上記の例では、キーのstackoverflowがすでに存在する場合、その値は2に更新されます。まだ存在しない場合は、新しいエントリが作成されます。

std::mapでは、キーにインデックスを付けることによって、要素に直接アクセスできます。

std::cout << ranking[ "stackoverflow" ] << std::endl;

マップ上でoperator[]を使用すると、実際には照会されたキーとともに新しい値がマップに挿入されます。これは、キーがすでにマップに格納されていても、 const std::mapで使用できないことを意味します。この挿入を防止するには、要素が存在するかどうか（たとえば、 find()使用at() ）、またはat()を以下のように使用するかどうかを確認します。

std::cout << ranking.at("stackoverflow") << std::endl;

std::mapとstd::multimap両方のコンテナでは、イテレータを使用して要素にアクセスできます。

// Example using begin()
std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                         std::make_pair(1, "docs-beta"),
                                         std::make_pair(2, "stackexchange")  };
auto it = mmp.begin();
std::cout << it->first << " : " << it->second << std::endl; // Output: "1 : docs-beta"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackoverflow"
it++;
std::cout << it->first << " : " << it->second << std::endl; // Output: "2 : stackexchange"

// Example using rbegin()
std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                    std::make_pair(1, "docs-beta"),
                                    std::make_pair(2, "stackexchange")  };
auto it2 = mp.rbegin();
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "2 : stackoverflow"
it2++;
std::cout << it2->first << " : " << it2->second << std::endl; // Output: "1 : docs-beta"

std :: mapまたはstd :: multimapの初期化

std::mapとstd::multimap両方は、コンマで区切られたキーと値のペアを提供することで初期化できます。キーと値のペアは、 {key, value}いずれかによって提供されるか、 std::make_pair(key, value)によって明示的に作成されstd::make_pair(key, value) 。 std::mapは重複キーを許さず、カンマ演算子は右から左へ実行するので、右のペアは左の同じキーを持つペアで上書きされます。

std::multimap < int, std::string > mmp { std::make_pair(2, "stackoverflow"),
                                     std::make_pair(1, "docs-beta"),
                                     std::make_pair(2, "stackexchange")  };
// 1 docs-beta
// 2 stackoverflow
// 2 stackexchange

std::map < int, std::string > mp {  std::make_pair(2, "stackoverflow"),
                                std::make_pair(1, "docs-beta"),
                                std::make_pair(2, "stackexchange")  }; 
// 1 docs-beta
// 2 stackoverflow

どちらもイテレータで初期化できます。

// From std::map or std::multimap iterator
std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {6, 8}, {3, 4}, 
                               {6, 7} };
                       // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 8}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); //moved cursor on first {6, 5}
std::map< int, int > mp(it, mmp.end()); // {6, 5}, {8, 9}

//From std::pair array
std::pair< int, int > arr[10];
arr[0] = {1, 3};
arr[1] = {1, 5};
arr[2] = {2, 5};
arr[3] = {0, 1};
std::map< int, int > mp(arr,arr+4); //{0 , 1}, {1, 3}, {2, 5}

//From std::vector of std::pair
std::vector< std::pair<int, int> > v{ {1, 5}, {5, 1}, {3, 6}, {3, 2} };
std::multimap< int, int > mp(v.begin(), v.end()); 
                        // {1, 5}, {3, 6}, {3, 2}, {5, 1}

要素の削除

すべての要素を削除する：

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
mmp.clear(); //empty multimap

イテレータの助けを借りてどこかから要素を削除する：

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
std::advance(it,3); // moved cursor on first {6, 5}
mmp.erase(it); // {1, 2}, {3, 4}, {3, 4}, {6, 7}, {8, 9}

範囲内のすべての要素を削除する：

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
auto it = mmp.begin();
auto it2 = it;
it++; //moved first cursor on first {3, 4}
std::advance(it2,3);  //moved second cursor on first {6, 5}
mmp.erase(it,it2); // {1, 2}, {6, 5}, {6, 7}, {8, 9}

指定された値を持つすべての要素をキーとして削除する：

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                            // {1, 2}, {3, 4}, {3, 4}, {6, 5}, {6, 7}, {8, 9}
mmp.erase(6); // {1, 2}, {3, 4}, {3, 4}, {8, 9}

述語predを満たす要素を削除する：

std::map<int,int> m;
auto it = m.begin();
while (it != m.end())
{
   if (pred(*it))
       it = m.erase(it);
   else
       ++it;
}

要素を挿入する

要素がstd::mapまだ存在しない場合にのみ、要素をstd::map挿入することができます。例えば、

std::map< std::string, size_t > fruits_count;

• キーと値のペアは、 insert()メンバー関数を介してstd::map挿入されます。それは引数としてpairを必要とします：

  fruits_count.insert({"grapes", 20});
  fruits_count.insert(make_pair("orange", 30));
  fruits_count.insert(pair<std::string, size_t>("banana", 40));
  fruits_count.insert(map<std::string, size_t>::value_type("cherry", 50));
  

  insert()関数は、イテレータとbool値からなるpair返します。

  • 挿入が成功した場合、イテレータは新しく挿入された要素を指し、 bool値はtrueです。
  • 同じkey持つ要素が既に存在する場合、挿入は失敗します。それが起こると、反復子は競合を引き起こす要素を指し、 boolは値がfalseです。

  挿入操作と検索操作を組み合わせるには、次のメソッドを使用できます。

  auto success = fruits_count.insert({"grapes", 20});
  if (!success.second) {           // we already have 'grapes' in the map
      success.first->second += 20; // access the iterator to update the value
  }
  

• 便宜上、 std::mapコンテナは、 std::map内の要素にアクセスする添え字演算子を提供し、存在しない場合は新しいものを挿入します。

  fruits_count["apple"] = 10;
  

  簡単ですが、要素がすでに存在するかどうかをユーザーが確認するのを防ぎます。要素がない場合、 std::map::operator[]暗黙的にそれを作成し、指定された値で上書きする前にデフォルトのコンストラクタで初期化します。

• insert()は、ペアのブレースリストを使用して複数の要素を一度に追加するために使用できます。このバージョンのinsert（）はvoidを返します：

  fruits_count.insert({{"apricot", 1}, {"jackfruit", 1}, {"lime", 1}, {"mango", 7}}); 
  

• insert()は、 value_type値の開始と終了を示すイテレータを使用して要素を追加するためにも使用できます。

  std::map< std::string, size_t > fruit_list{ {"lemon", 0}, {"olive", 0}, {"plum", 0}};
  fruits_count.insert(fruit_list.begin(), fruit_list.end()); 
  

例：

std::map<std::string, size_t> fruits_count;
std::string fruit;
while(std::cin >> fruit){
    // insert an element with 'fruit' as key and '1' as value
    // (if the key is already stored in fruits_count, insert does nothing)
    auto ret = fruits_count.insert({fruit, 1});
    if(!ret.second){            // 'fruit' is already in the map 
        ++ret.first->second;    // increment the counter
    }
}

std::mapはツリーとして実装されているため、挿入操作の時間の複雑さはO（log n）です。

std::map< std::string , int > runs;
runs.emplace("Babe Ruth", 714);
runs.insert(make_pair("Barry Bonds", 762));

std::map< std::string , int > runs;
auto it = runs.emplace("Barry Bonds", 762); // get iterator to the inserted element
// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it, "Babe Ruth", 714);

std :: mapまたはstd :: multimapを繰り返し処理する

std::mapまたはstd::multimapは次の方法でトラバースできます：

std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
                               
//Range based loop - since C++11
for(const auto &x: mmp) 
    std::cout<< x.first <<":"<< x.second << std::endl;

//Forward iterator for loop: it would loop through first element to last element
//it will be a std::map< int, int >::iterator
for (auto it = mmp.begin(); it != mmp.end(); ++it)
std::cout<< it->first <<":"<< it->second << std::endl; //Do something with iterator

//Backward iterator for loop: it would loop through last element to first element
//it will be a std::map< int, int >::reverse_iterator
for (auto it = mmp.rbegin(); it != mmp.rend(); ++it)
std::cout<< it->first <<" "<< it->second << std::endl; //Do something with iterator

std::mapまたはstd::multimapを繰り返し処理する間は、無用な暗黙的な変換を避けるためにauto使用することをおstd::multimapします（詳細はSO答えを参照してください）。

std :: mapまたはstd :: multimapで検索する

std::mapまたはstd::multimapでキーを検索する方法はいくつかあります。

• キーの最初の出現のイテレータを取得するには、 find()関数を使用できます。キーが存在しない場合はend()返します。

    std::multimap< int , int > mmp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
    auto it = mmp.find(6);
    if(it!=mmp.end())
        std::cout << it->first << ", " << it->second << std::endl; //prints: 6, 5
    else
        std::cout << "Value does not exist!" << std::endl;
  
    it = mmp.find(66);
    if(it!=mmp.end())
        std::cout << it->first << ", " << it->second << std::endl; 
    else
        std::cout << "Value does not exist!" << std::endl; // This line would be executed.
  

• エントリがstd::mapまたはstd::multimap存在するかどうかを調べるもう1つの方法は、 count()関数を使用して、指定されたキーに関連付けられている値の数を数えます。 std::mapは各キーに1つの値しか関連付けていないため、 count()関数は0（キーがない場合）または1（存在する場合）を返すことができます。 std::multimap場合、同じキーに複数の値が関連付けられている可能性があるため、 count()は1より大きい値を返します。

   std::map< int , int > mp{ {1, 2}, {3, 4}, {6, 5}, {8, 9}, {3, 4}, {6, 7} };
   if(mp.count(3) > 0) // 3 exists as a key in map
       std::cout << "The key exists!" << std::endl; // This line would be executed.
   else
       std::cout << "The key does not exist!" << std::endl;
  

  ある要素が存在するかどうかだけが気になる場合、 findは厳密には良いです。それはあなたの意図を記録し、 multimaps場合、最初に一致する要素が見つかると停止します。

• std::multimap場合、同じキーを持つ複数の要素が存在する可能性があります。この範囲を取得するには、iteratorの下限（上限）と上限（上限）を持つstd::pairを返すequal_range()関数を使用します。キーが存在しない場合、両方のイテレータはend()指します。

    auto eqr = mmp.equal_range(6);
    auto st = eqr.first, en = eqr.second;
    for(auto it = st; it != en; ++it){
        std::cout << it->first << ", " << it->second << std::endl; 
    }
        // prints: 6, 5
        //         6, 7
  

要素数の確認

コンテナstd::mapは、マップが空であるかどうかに応じてtrueまたはfalseを返すメンバー関数empty()があります。メンバー関数size()は、 std::mapコンテナに格納されている要素の数を返します。

std::map<std::string , int> rank {{"facebook.com", 1} ,{"google.com", 2}, {"youtube.com", 3}};
if(!rank.empty()){
    std::cout << "Number of elements in the rank map: " << rank.size() << std::endl;
}
else{
    std::cout << "The rank map is empty" << std::endl;
}

マップの種類

レギュラーマップ

マップは、キーと値のペアを含む連想型コンテナです。

#include <string>
#include <map>
std::map<std::string, size_t> fruits_count;

上記の例では、 std::stringはキータイプであり、 size_tは値です。

キーはマップ内のインデックスとして機能します。各キーは一意でなければならず、注文する必要があります。

• 同じキーを持つ複数の要素が必要な場合は、 multimap使用を検討してください（後述）

• 値のタイプで順序が指定されていない場合、またはデフォルトの順序をオーバーライドする場合は、次のいずれかを指定します。

  #include <string>
  #include <map>
  #include <cstring>
  struct StrLess {
      bool operator()(const std::string& a, const std::string& b) {
          return strncmp(a.c_str(), b.c_str(), 8)<0;
                 //compare only up to 8 first characters
      }
  }
  std::map<std::string, size_t, StrLess> fruits_count2;
  

  StrLess比較器が2つのキーに対してfalseを返す場合、実際の内容が異なっていても同じものとみなされます。

マルチマップ

マルチマップでは、同じキーを持つ複数のキーと値のペアをマップに格納できます。それ以外の場合は、そのインターフェイスと作成は通常のマップに非常に似ています。

 #include <string>
 #include <map>
 std::multimap<std::string, size_t> fruits_count;
 std::multimap<std::string, size_t, StrLess> fruits_count2;

ハッシュマップ（順序付けられていないマップ）

ハッシュマップには、通常マップと同様のキーと値のペアが格納されます。しかし、キーに関して要素を順序付けることはありません。代わりに、キーのハッシュ値を使用して、必要なキーと値のペアにすばやくアクセスします。

#include <string>
#include <unordered_map>
std::unordered_map<std::string, size_t> fruits_count;

順序付けられていないマップは通常は高速ですが、要素は予測可能な順序で格納されません。たとえば、 unordered_mapすべての要素を反復処理すると、一見無作為な順序で要素がunordered_mapます。

ユーザー定義型をキーとしてstd :: mapを作成する

クラス内のキーをマップ内のキーとして使用できるようにするには、キーに必要なのは、それがcopiableでassignableです。マップ内の順序は、テンプレートの3番目の引数（およびコンストラクタが使用されている場合はその引数）によって定義されます。これはデフォルトではstd::less<KeyType>に設定されています。デフォルトは<演算子ですが、デフォルトを使用する必要はありません。比較演算子を書くだけです（できれば関数オブジェクトとして）：

struct CmpMyType
{
    bool operator()( MyType const& lhs, MyType const& rhs ) const
    {
        //  ...
    }
};

C ++では、 "compare"述部は厳密な弱い順序でなければなりません。特に、 compare(X,X)は任意のXに対してfalseを返す必要があります。つまり、 CmpMyType()(a, b)がtrueを返す場合、 CmpMyType()(b, a)はfalseを返さなければならず、両方がfalseを返す場合、要素は等しいと見なされます。

厳格な弱い注文

これは、2つのオブジェクト間の関係を定義する数学的な用語です。
定義は次のとおりです。

f（x、y）とf（y、x）の両方がfalseの場合、2つのオブジェクトxとyは等価です。オブジェクトは、それ自体に相当する（非再帰不変不変によって）常に存在することに注意してください。

C ++の場合、指定された型のオブジェクトが2つある場合は、<と比較して次の値を返す必要があります。

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

等価/以下を定義する方法は、オブジェクトのタイプに完全に依存します。