まえがき
この記事は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[]で社員名を指定すると時給が取得できる.
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
まず
std::map<std::string, int>
であるが
テンプレート第一引数のstd::stringがkey
テンプレート第二引数のintがvalue
である.
mapはkeyからvalueを検索するのが得意である.
mapを利用する理由の殆どはその高速な値の検索にあると言って良い.
map::operator[]
検索キーを指定して値を検索できる.
計算量は要素数に対して対数時間となる.
operator[]の特徴は存在しないキーを指定した場合の挙動だ.
存在しないキーを指定すると自動で値が追加され, デフォルト値が返ってくる.
#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例外を送出する.
#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になっている.
#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とは以下のように２つの値を保持するアグリゲートクラスである.
template < class First, class Second >
struct pair{
First first;
Second second;
};
pairに保持した値はfirst, secondでアクセスできる.
make_pairするとpairを作ることができる.
std::pair<int,int> p = std::make_pair(1,2);
std::pair<int,int>などという長い型を書かずにautoを使うことを強くおすすめする.
auto p = std::make_pair(1,2);
自動で値を挿入せず, 例外も出さずに存在しない可能性のあるキーを指定したい
キーが存在するかを調べるしかないだろう.
キーを検索する場合はmap::findを使う.
#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 しか返さない.
したがって、
dictionary.find("hoge") != dictionary.end(dictionary)
は
dictionary.count("hoge")
に置き換えることができる.
しかし、字面が悪い気がする.
0,1 しか返さないとはいえ、countの返り値の型はsize_tなので、暗黙の型変換になる.
#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はコンテナなのでイテレータを取得してレンジを回すことができる.
#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)とすれば良い.
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に譲る.
mapへの要素操作
要素挿入
map::insert
insertを使えばkeyとvalueのpairを挿入できる.
mapの内部は自動でソートされるのでどこに挿入するかなど一切考える必要はない.
map<int,int> dic{};
dic.insert(std::make_pair(1,3));
map::emplace
insertと似ているが, こちらは値をkeyとvalueのコンストラクタに転送し値を構築する.
以下を見てほしい.
std::map<int,int> dic{};
dic.emplace(1,3); // dic.insert(std::make_pair(1,3))と同様のことができる
面倒なpairの構築が不要になる.
emplaceを使い, 値をkeyとvalueのコンストラクタに複数ずつ転送することもできる.
piecewise constructという.
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を指定して要素を削除
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
イテレータを指定して要素を削除
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は消えない.
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
全部消す
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などのアルゴリズムに渡したときのコピーをなくすことができる.
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を省くことができる.
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>で値を受け取るのはパフォーマンスに関わるかもしれない無駄なコピーを生み出す.
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を使いなさい.
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++まじで分からん.