C++ STL mapのコード集

# 概要
STL（Standard Template Library）の`map`関係のコード集です。対応確認環境はMicrosoft Visual Studio 2019 Communityのstd:c++latest (C++20 draft)です。最新のC++では制約が異なる可能性があります。

# 共通事項

- `using namespace std;`により`std::`は省略しています。
- `insert_iterator`は`insert_iterator(m, begin(m))`、`insert_iterator(m, end(m))`のどちらでも作成できます。`inserter`も同様です。
- `type var{...};`は`type var = {...};`と同様です。

## 出力用の関数

出力用に次の関数を定義しています。共通部分なので以降のコードでは省略します。

### `map`の出力

```cpp
template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map)
{
	for (const auto& [key, value] : map)
	{
		wcout << key << L", " << value << endl;
	}
}
```

### `vector`の出力

範囲`for`、`copy`と`ostream_iterator`の2種類が使用できます。

```cpp:範囲for
template <typename T>
void output(const vector<T>& v)
{
	for (const auto& i : v)
	{
		wcout << i << endl;
	}
}
```

```cpp:copyとostream_iterator
template <typename T>
void output(const vector<T>& v)
{
	copy(cbegin(v), cend(v),
		ostream_iterator<T, wchar_t>(wcout, L"\r\n"));
}
```

### 一般的な制約

- ラムダ式の引数は構造化束縛できません。`map`の要素を引数としたラムダ式では`const auto& pair`を使い、必要に応じてラムダ式内で構造化束縛`const auto& [key, value] = pair;`します。
- 範囲forでは構造化束縛できます。

# `map`のコピー

コンストラクタにイテレータを渡すと任意の範囲をコピーできます。キーは昇順でソートされることに注意してください。

## 全体のコピー

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};
	map<int, int> m2(cbegin(m1), cend(m1));

	output(m2);

	return 0;
}
```

```plaintext:出力
0, 0
1, 1
2, 2
```

## 部分のコピー

`cbegin`や`cend`に`next`や`prev`を適用して先頭からN個や末尾からN個を飛ばしてコピーできます。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}};
	// 先頭から2個、末尾から1個を飛ばしてコピー
	map<int, int> m2(next(cbegin(m1), 2), prev(cend(m1), 1));

	output(m2);

	return 0;
}
```

```plaintext:出力
2, 2
3, 3
```

## 逆順でコピー

`crbegin`と`crend`を適用して逆順でコピーできます。`next`や`prev`も適用可能です。出力時はキーが昇順ソートされることに注意してください。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}};
	// 逆順の末尾は{0, 0}なのでprev(crend(m1), 1)で除外されます。
	map<int, int> m2(crbegin(m1), prev(crend(m1), 1));

	output(m2);

	return 0;
}

```

```plain:出力
1, 1
2, 2
3, 3
4, 4
```

# `map`から別の`map`へコピーして追加

- ただのコピーして追加は`copy`や`map::insert`でも可能ですが、応用が効くのは`transform`です。
- いずれの方法にも`next`や`prev`、`crbegin`や`crend`のような関数を適用できます。

## `transform`の使用

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, int> m2;
	transform(cbegin(m1), cend(m1), inserter(m2, end(m2)),
		[](const auto& kv) {
			return kv;
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

### ラムダ式内で構造化束縛

#### クラステンプレートの型推論（return pair(key, value)）

ラムダ式内で構造化束縛すると次のようになります。戻り値では`key`、`value`から`pair`を作成する必要があります。ラムダ式の戻り値の型は省略できます。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, int> m2;
	transform(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return pair(key, value);
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

#### 生成関数（return make_pair(key, value)）

戻り値は`pair`コンストラクタの代わりに`make_pair`生成関数を使うこともできます。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, int> m2;
	transform(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return make_pair(key, value);
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

#### return {...}

戻り値には初期化子リストも指定できます。ただし、型推論のためにラムダ式の戻り値の型を明記する必要があります。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, int> m2;
	transform(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)),
		[](const auto& kv) -> decltype(m2)::value_type {
			const auto& [key, value] = kv;
			return {key, value};
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

## `copy`の使用

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};
	map<int, int> m2;
	copy(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)));

	output(m2);

	return 0;
}
```

## `map::insert`の使用

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};
	map<int, int> m2;
	m2.insert(cbegin(m1), cend(m1));

	output(m2);

	return 0;
}
```

# 値を`wstring`型に変換した`map`を作成する

`to_wstring`を使います。既存の`map`を指定することで要素の追加も可能です。

```cpp
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <map>

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, wstring> m2;
	transform(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return pair(key, to_wstring(value));
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

# 値を`string`型に変換した`map`を作成する

`to_string`を使います。既存の`map`を指定することで要素の追加も可能です。

```cpp
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <map>

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	map<int, string> m2;
	transform(cbegin(m1), cend(m1), insert_iterator(m2, end(m2)),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return pair(key, to_string(value));
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

# キーや値を`vector`へ変換する
## キーを`vector`に変換する

```cpp
#include <algorithm>
#include <iterator>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <typename T>
void output(const vector<T>& v)

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	vector<decltype(m1)::key_type> keys;
	transform(cbegin(m1), cend(m1), back_insert_iterator(keys),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return key;
		});

	output(keys);

	return 0;
}
```

```plain:出力
0
1
2
```

## 値を`vector`へ変換する

値の型は`map<>::mapped_type`です。`map<>::value_type`はキーと値のペアの`pair`型です。

```cpp
#include <algorithm>
#include <iterator>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	map<int, int> m1{{0, 0}, {1, 1}, {2, 2}};

	vector<decltype(m1)::mapped_type> values;
	transform(cbegin(m1), cend(m1), back_insert_iterator(values),
		[](const auto& kv) {
			const auto& [key, value] = kv;
			return value;
		});

	output(values);

	return 0;
}
```

# キーと値から`map`を作成する

`transform`の2入力イテレーター版で実現できます。

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

using namespace std;

template <typename KeyT, typename MappedT>
void output(const map<KeyT, MappedT>& map);

int main()
{
	vector keys{0, 1, 2};
	vector values{0, 1, 2};

	map<int, int> m1;
	transform(cbegin(keys), cend(keys), cbegin(values),
		insert_iterator(m1, end(m1)),
		[](const auto& key, const auto& value) {
			return pair(key, value);
		});

	output(m2);

	return 0;
}
```

```plain:出力
0, 0
1, 1
2, 2
```

入力イテレータ1が入力イテレーター2より長い場合は実行時エラーが発生することに注意してください。

```cpp:入力イテレータ1＞入力イテレーター2
vector keys{0, 1, 2, 3};
vector values{0, 1, 2};
// 異常終了
```

```cpp:入力イテレータ1＜入力イテレーター2
vector keys{0, 1, 2};
vector values{0, 1, 2, 3};
// 入力イテレータ2の超過した要素が無視
// 0, 0
// 1, 1
// 2, 2
```