std::mapまとめ

#まえがき

この記事はstd::mapについての殴り書き.
この記事をりーまに捧ぐ.
最初に言っておくことが一つだけある.
**サンプルコードは以下のC++17の機能を使い放題している.**
C++17 If statement with initializer
C++17 Structured binding declarations

#std::map


std::mapとはC++標準ライブラリに用意された平衡二分木.
特徴は要素の要素数に対する対数オーダーでの高速な検索能力と
内部で要素がソート状態で保持されるというところだろう.
こと特徴から使い方としては辞書みたいな使い方が多いと思われる.
高速な要素検索のみが必要でソートされることに関心がない場合はふつう**unordered_map**を使い, mapを使わない.

例として, 社員の名前から時給を検索できるようなコードをあげよう.
まずmapを宣言する.
次に社員名とその時給を登録する.
そうすると, operator[]で社員名を指定すると時給が取得できる.

```cpp
std::map<std::string,int> salary;

salary["John"] = 1400;
salary["Tom"] = 1000;
salary["Harry"] = 0;

int a = salary["John"]; // 1400
int b = salary["Tom"]; // 1000
int c = salary["Harry"]; // 0
```

##keyとvalue

まず

```cpp
std::map<std::string, int>
```

であるが

テンプレート第一引数の`std::string`がkey
テンプレート第二引数の`int`がvalue
である.

mapはkeyからvalueを検索するのが得意である.
mapを利用する理由の殆どはその高速な値の検索にあると言って良い.

##map::operator[]

検索キーを指定して値を検索できる.
計算量は要素数に対して対数時間となる.
operator[]の特徴は存在しないキーを指定した場合の挙動だ.
存在しないキーを指定すると自動で値が追加され, デフォルト値が返ってくる.

```cpp
#include <iostream>
#include <map>
using namespace std;
int main()
{
  std::map<int,int> m{};

  cout << m.size() << endl; // 何も要素を追加していないので当然 0
  cout << m[1] << endl; // 要素は存在しない, 自動で0が追加される
  cout << m.size() << endl; // 自動で要素が追加されているので 1
}
```

このように, operator[]はmap変更を伴うのでconstなmapにはoperator[]ではアクセスできない.
constなmapにアクセスしたい場合には次にあげるmap::atを使う.

##map::at

検索キーを指定して値を検索できる.
計算量は要素数に対して対数時間となる.
こちらは存在しないキーを指定するとout_of_range例外を送出する.

```cpp
#include <iostream>
#include <map>
using namespace std;
int main()
{
  std::map<int,int> m{};

  cout << m.size() << endl; // 何も要素を追加していないので当然 0
  cout << m.at(1) << endl; // 要素は存在しない, Abort! out_of_range
}
```

##mapのvalue_type

mapはvectorやlistのようなコンテナの仲間なのでイテレータを取得できる.
mapの内部ではキーが昇順になるよう要素がソートされている（詳しくは後述）.
`map<key, value>`のイテレータを参照剥がしして得られる型は.
`std::pair<const key, value>`である.
言い換えると`map<key, value>`のvalue_typeは`pair<const key, value>`である.
mapの内部ではkeyとvalueはセットで保持されており, keyは変更されないのが前提なのでconstになっている.

```cpp
#include <map>
#include <iostream>

int main(){
	std::map<std::string, unsigned> dictionary{
        {"John", 1000},
        {"Tom", 1400},
        {"Harry", 800}
    };
    
    typename std::map<std::string, unsigned>::iterator iter = begin(dictionary); // 最初の要素を指すイテレータを取得
    std::pair<const std::string, unsigned> p = *iter; // 参照剥をがして最初の要素をとり出す
    const std::string& name = p.first; // 名前の辞書順で一番はじめはHarry
    unsigned& sarary = p.second; // 800
}

```

##std::pair

std::pairとは以下のように２つの値を保持するアグリゲートクラスである.

```cpp
template < class First, class Second >
struct pair{
  First first;
  Second second;
};
```

pairに保持した値はfirst, secondでアクセスできる.
make_pairするとpairを作ることができる.

```cpp
std::pair<int,int> p = std::make_pair(1,2);
```

`std::pair<int,int>`などという長い型を書かずにautoを使うことを強くおすすめする.

```cpp
auto p = std::make_pair(1,2);
```



##自動で値を挿入せず, 例外も出さずに存在しない可能性のあるキーを指定したい

キーが存在するかを調べるしかないだろう.
キーを検索する場合はmap::findを使う.

```cpp
#include <map>
#include <iostream>

int main(){
	std::map<std::string, unsigned> dictionary{
        {"John", 1000},
        {"Tom", 1400},
        {"Harry", 800}
    };
    
    if ( auto iter = dictionary.find("hoge"); iter != end(dictionary) ) {
        std::cout << iter->second << std::endl;
    } else {
        std::cout << "not exists" << std::endl;
    }
} 
```

===== Begin:追記（2018/3/12）=====

@kur さんよりコメントを頂いたので追記する.
mapのキーの存在を確かめるためにはmap::countを使うことができる.
mapのキーは重複できないのでmap::countは 0 か 1 しか返さない.
したがって、

```cpp
dictionary.find("hoge") != dictionary.end(dictionary)
```

は

```cpp
dictionary.count("hoge") 
```

に置き換えることができる.
しかし、字面が悪い気がする.
0,1 しか返さないとはいえ、countの返り値の型はsize_tなので、暗黙の型変換になる.

```cpp
#include <map>
#include <iostream>

int main(){
	std::map<std::string, unsigned> dictionary{
        {"John", 1000},
        {"Tom", 1400},
        {"Harry", 800}
    };
    
    if ( dictionary.count("hoge") ) {
        std::cout << "exists" << std::endl;
    } else {
        std::cout << "not exists" << std::endl;
    }
} 
```

===== End:追記 =====


##mapのイテレーション

mapはコンテナなのでイテレータを取得してレンジを回すことができる.

```cpp
#include <map>
#include <iostream>

int main(){
	std::map<std::string, unsigned> dictionary{
        {"John", 1000},
        {"Tom", 1400},
        {"Harry", 800}
    };
    
    for (const auto& [key, value] : dictionary){
        std::cout << key << " => " << value << "\n";
    }
}
```

**output**
>Harry => 800
John => 1000
Tom => 1400

##双方向イテレータ

mapのイテレータは双方向イテレータである.
双方向イテレータの詳しい解説はしない, ググってくれ.
何ができないのかだけを書いておく.
random accessはできない.
したがってイテレータを進めたい場合, `iter+3`のように書くことはできない.
`std::next(iter, 3)`とすれば良い.

```cpp
int main(){
    std::map<std::string, unsigned> hash{
        {"John", 1000},
        {"Tom", 1400},
        {"Harry", 800}
    };
    
    auto iter = hash.begin();
    iter = std::next(iter, 2); // iterをふたつすすめる
    std::cout << iter->first << std::endl; // Tom
}
```

##mapの内部構造とstrict weak ordering

mapの内部では要素がキーでソートされていると言った.
mapはキーがソートできる`operator<`が定義されている型であることを要求する.

ソートできる`operator<`とわざわざ言ったのには理由がある.
ただ定義されていればいいわけではないのだ.

ソートを行うためには`operator<`の満たすべき性質があり
それはstrict weak orderと呼ばれるものである.

定義

- 非反射性：operator<(x, x)は常にfalseである
- 推移性：operator<(x, y)がtrueでありoperator<(y, z)がtrueであるならoperator<(x, z)はtrueである
- equivalence推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

xとyがequivalentであるというのは，operator<(x, y)がfalseであり
かつoperator<(y, x)がfalseである，ということです．

これを満たして実装しなければただしくソートされる保証はなくなる.

strict weak orderの詳しい解説は[Cry's Diary](http://d.hatena.ne.jp/Cryolite/touch/20050531/p2)に譲る.

#mapへの要素操作

##要素挿入
###map::insert

insertを使えばkeyとvalueのpairを挿入できる.
mapの内部は自動でソートされるのでどこに挿入するかなど一切考える必要はない.

```cpp
map<int,int> dic{};

dic.insert(std::make_pair(1,3));
```

###map::emplace

insertと似ているが, こちらは値をkeyとvalueのコンストラクタに転送し値を構築する.
以下を見てほしい.

```cpp
std::map<int,int> dic{};

dic.emplace(1,3); // dic.insert(std::make_pair(1,3))と同様のことができる
```

面倒なpairの構築が不要になる.

emplaceを使い, 値をkeyとvalueのコンストラクタに複数ずつ転送することもできる.
piecewise constructという.

```cpp
std::map<std::string, std::complex<double>> dic{};

// string(3,'B')とcomplex<double>(5,6)のpairが挿入される
dic.emplace(std::piecewise_construct,
            std::forward_as_tuple(3, 'B'),
            std::forward_as_tuple(5, 6));

auto const& [k, v] = *begin(dic);
std::cout << k << " : " << v; // BBB : (5,6)
```

##要素削除

###key指定のmap::erase

keyを指定して要素を削除

```cpp
std::map<int,int> dic{
    {1,2},
    {2,3},
    {3,4}
};

dic.erase(1); // (1,2)は消える

// (2,3)
// (3,4)
for (auto const& [k, v] : dic)
    printf("(%d,%d)\n", k, v); 
```

###イテレータ指定のmap::erase

イテレータを指定して要素を削除

```cpp
std::map<int,int> dic{
    {1,2},
    {2,3},
    {3,4}
};

dic.erase(begin(dic)); // 最初の要素(1,2)は消える

// (2,3)
// (3,4)
for (auto const& [k, v] : dic)
    printf("(%d,%d)\n", k, v); 
```

###イテレータ範囲指定のmap::erase

イテレータ範囲を指定して要素を削除
[first, last)を指定して消す.
firstからlastの前まで消える.
lastは消えない.

```cpp
std::map<int,int> dic{
    {1,2},
    {2,3},
    {3,4},
    {4,5},
    {5,6}
};
// 最初のから数えて３つ分消す
dic.erase(begin(dic), std::next(begin(dic), 3));

// (4,5)
// (5,6)
for (auto const& [k, v] : dic){
    printf("(%d,%d)\n", k, v); 
}
```

###map::clear

全部消す

```cpp
std::map<int,int> dic{
    {1,2},
    {2,3},
    {3,4},
    {4,5},
    {5,6}
};
// さくじょ～
dic.clear();

// もちろん何も出力されない
for (auto const& [k, v] : dic)
    printf("(%d,%d)\n", k, v); 
}
```


#mapテクニック

##stringをkeyにする場合にstd::less<>を第3テンプレート引数に指定する

文字列リテラルをfindやlower_bound, upper_boundなどのアルゴリズムに渡したときのコピーをなくすことができる.

```cpp
std::map<std::string, int, std::less<>> hash = {
      {"John", 1},
      {"Bob",  2},
      {"Mary", 3}
    };

    // std::lessのvoidに対する特殊化を使用することで、
    // 文字列リテラルをfind()関数の引数として渡した際に、
    // std::string型の一時オブジェクトが生成されない。
    auto it = hash.find("Bob");
    if (it != hash.end()) { // 見つかった
      std::cout << it->second << std::endl;
    }
```

##map::emplace_hintを使って挿入時のfindを省く

mapは常にソートされている状態を保つため, 挿入時にどこに挿入すればいいかを毎回findする.
emplace_hintを使えば, 予めどこに挿入するのかがわかっている場合に挿入時のfindを省くことができる.

```cpp
std::map<int, char> hash;

  hash.emplace(1, 'A');

  // キー2の要素が最後尾に追加されることが予めわかっているので, hash.end()をヒントとして与える
  hash.emplace_hint( hash.end(), 2, 'B' );
```


##mapのvalue_typeはautoで推論する

`map<key, value>`の要素型が**`pair<const key, value>`**であることを忘れて（または知らずに）**`pair<key, value>`**で値を受け取るのはパフォーマンスに関わるかもしれない無駄なコピーを生み出す.

```cpp
map<std::string, int> hash{
    {"hoge",0},
    {"fuga",0},
    {"puyo",0},
    //...
    {"last",0}
};

for(auto iter = begin(hash); iter != end(hash); ++iter) {
    // 参照したいのだろうが型が違うのでコピーが発生, 改めた方がいいコード
    const std::pair<std::string, int>& hoge = *iter;
    // ...
}
```

そもそも`const std::pair<std::string, int>&`などという複雑な型を書くべきではない.
コンパイラに推論させておけば良いのだ.
`auto`を使いなさい.

```cpp
map<std::string, int> hash{
    {"hoge",0},
    {"fuga",0},
    {"puyo",0},
    //...
    {"last",0}
};

for(auto iter = begin(hash); iter != end(hash); ++iter) {
    const auto& hoge = *iter; // 型推論しておけば型がちがったり絶対しない
    // ...
}
```

#C++17時代

執筆中

#おわりに

C++まじで分からん.