ViVi Home > 技術文書
> さくさく理解する C/C++ コンソールアプリ入門 >
手を動かしてさくさく理解する マップクラス std::map 入門
std::map とは C++ で標準に使用できる便利なマップクラスでござるぞ。
「マップクラス」とは検索可能なキーと、キーに対応する値の組（ペア）を要素とするコンテナクラスで、
保持している要素から、キーを指定して値を高速に取り出せるクラスのことだ。
例えば、string 型の人名と int 型の年齢を組にした要素を保持しておくと、名前をキーにして年齢を高速に取得することができる。 名前から年齢への写像（mapping.）のようなものなので map というクラス名を持つ。
ちなみに、単純な配列を使ってキーから要素を取得する処理時間は O(N) であるが、map は O(log N) である。 これは map クラスが２分木（正確には赤黒木）で実装されているからだ。
※ O(N) だと要素数が千倍になると処理時間が千倍になる。2分木の O(log N) であれば、要素数が千倍になっても処理時間の増加は約10倍でしかない。 要素数が100万倍になったときの差はもっと顕著だ。
本章では、map オブジェクトの宣言方法について説明する。
宣言方法を具体的に説明する前に、map を使うための準備について説明する。
map は C++標準ライブラリに含まれており、「#include <map>」を記述することで利用可能になる。
名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。
#include <map> // ヘッダファイルインクルード
int main()
{
std::map<std::string, int> mp; // ローカル変数として、mp を生成
.....
}
#include <map> // ヘッダファイルインクルード
using namespace std; // 名前空間指定
int main()
{
map<std::string, int> mp; // ローカル変数として、mp を生成
.....
}
std::map オブジェクトを生成するには「std::map<キー型, 値型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言するマップを識別するための名前のことだ。変数名と言ってもよい。
map はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
vector や list 等の通常コンテナクラスと異なるのは、型を２つ指定するところだ。
最初の型はキーとなるものの型で、string や int 型などいろいろな型を指定できる。
ただし、どんな型でも指定できるかというとそうではなく、オブジェクトの順序が計算可能であるという条件がある。
具体的には bool operator<() が定義されていないと最初の型には指定できない。
例えば、vector はキー型として指定できないが、vector の派生クラスを定義し、bool operator<() を定義してやれば大丈夫だ。
class KeyVectorInt : public std::vector<int>
{
bool operator<(const KeyVectorInt &rhs)
{
return size() < rhs.size(); // これは単なる例で、実際のコードとしては不適
}
};
std::map<vector<int>, int> mp1; // ビルドエラー
std::map<KeyVectorInt, int> mp2; // ビルドOK
値型の方には特に条件は無い。
下記は、string 型をキーとし、int 型を値とするマップ mp を宣言している例だ。
std::map<std::string, int> mp; // int 型の双方向リスト lst の宣言
このようにして宣言したオブジェクトの要素数は0だ。要素を追加する方法は次の章で説明する。
< > は何だ？と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。
深入りはせず、現在のところは取り扱う要素の型をこういう書き方で指定すると無条件で覚えてほしい。
コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::map<キー型, 値型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である必要がある。
※ 暗黙の型変換が可能な型であれば、コピー元オブジェクトとして指定可能ではある。
std::map<std::string, int> org;
org に値を設定
std::map<std::string, int> x(org); // コピーコンストラクタ
上記のコードは org をコピーし、同じ値を持つマップ x を生成する。
演習問題：解答例
マップオブジェクトにキーに対する値を設定するには「mp[キー] = 値;」と記述する。
例えば、std::map<std::string, int> mp に対し、キー"abc" の値を 123 に設定するには、以下のように記述します。
mp["abc"] = 123;
この書き方は直感的にわかりやすく便利でしょ。
値の設定は上書きすることが出来る。
mp["abc"] = 123;
mp["abc"] = 456;
上記の様に mp["abc"] の値を複数回設定した場合は、最後に設定した値が有効になる。
右辺値として mp[キー] と記述することで、mp から キー を検索し、その値を取得することが出来る。
例えば、前節のように mp["abc"] に 123 が設定されているとき、mp["abc"] は 123 を返す。
値が設定されていないキーを指定した場合、値型のデフォルト値が返される。
値が本当に設定されているかどうかを確認するには、次章で説明する検索機能を使用する。
begin() で最初の要素へのイテレータを、end() で最後の要素の次へのイテレータを取得できる。
要素はキーと値のペア（std::pair）のことで、キー・値それぞれを first, second で取得できる。
下記は、マップの最初から最後までをイテレータを回し、要素の内容を表示する例だ。
std::map<std::string, int> mp
いろんな値を登録;
for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
std::cout << "key = " << itr->first // キーを表示
<< ", val = " << itr->second << "\n"; // 値を表示
}
演習問題：解答例
find(キー) で、キーがマップに登録されているかどうかを調べることが出来る。
キーが登録されている場合は、キーと値のペアへのイテレータを返す。
キーが登録されていない場合は、end() へのイテレータを返す。
std::map<std::string, int> mp
いろんな値を登録;
auto itr = mp.find("xyz"); // "xyz" が登録されているか？
if( itr != mp.end() ) {
登録されている場合の処理
} else {
登録されていない場合の処理
}
キーと値のペアとは std::pair<キー型, 値型> のことである。なので、キーは first, 値は second で取得することが出来る。
auto itr = mp["xyz"];
if( itr != mp.end() ) {
cout << itr->first << "\n"; // "xyz" が表示される
cout << itr->second << "\n"; // mp["xyz"] の値が表示される
}
演習問題：解答例
マップに登録された要素の削除は erase(キー) または erase(iterator) で行う。
mp から、キー："abc" の要素を削除したい場合は mp.erase("abc") とすればよい。直感的で簡単だ。
存在しないキーを指定した場合は、無視され何も起こらない。
予め、キーが存在しているかどうかをチェックし、存在している場合のみ削除したい場合は、以下のように erase(イテレータ) を使用する。
auto itr = mp.find("abc");
if( itr != mp.end() ) // キーの要素が存在している場合
mp.erase(itr);
実はイテレータには end() を指定しても何も問題は起こらない。なので、単に mp.erase(mp.find("abc")); と書いてもいいのだが、 そう書くくらいなら mp.erase("abc") と書いた方が素直で好感が持てる。
演習問題：解答例
「bool empty()」はマップが空かどうかを判定する関数。
次に出てくる size() を使って、size() == 0 と判定するのと同等だ。
が、コンテナクラスによっては size() 計算よりも empty() の方が高速な場合がある。
なので、コンテナクラスに対しては empty() を使うことが推奨されている。
「size_t size()」は、要素数を返す関数。
通常配列だと「sizeof(data)/sizeof(data[0])」のように記述しないと、要素数を取得できないが、
map では「data.size()」と簡潔かつ分かりやすく書ける。
※ size_t はサイズを表す型で、符号なし整数の組み込み型である。ちなみに、sizeof() も size_t 型を返す。
「clear()」はマップを空にする関数。
サイズを0にする。vector とは違い、要素を delete し、メモリが解放される。
演習問題：解答例
本稿で説明したのは、std::map の基本的な部分のみである。説明していないメソッドもたくさんある。
それらについては以下のサイトなどで勉強してほしい。
通常、std::map はテンプレートライブラリになっており、ソースが公開されている。
ソースを探しだして、読んでみると勉強になるかもしれない。
ただし、かなりレベルが高いコードなので、ちゃんと理解するのはそれなりの能力と知識と経験が必要だ。
上級者でないと無理だ。ちょっと見て理解不能と思ったら、すぐに勇気ある撤退をしよう。
std::map<std::string, char> mp;
std::map<int, double> mp;
std::map<std::string, std::string> mp;
mp["aiueo"] = "あいうえお";
mp["kakikukeko"] = "かきくけこ";
std::map<std::string, int> mp;
mp["aiueo"] = 1;
mp["kakikukeko"] = 2;
std::cout << mp["aiueo"] << "\n";
std::cout << mp["kakikukeko"] << "\n";
std::cout << mp["sashisuseso"] << "\n";
bool isContained(const std::map<std::string &mp, int>, int val)
{
for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
if( itr->second == val ) // 値を発見した場合
return true;
}
return false; // 値が発見できなかった場合
}
std::map<std::string, int> mp;
mp["abc"] = 1;
mp["xyz"] = 9;
auto itr = mp.find("abc");
if( itr != mp.end() && itr->first == "abc" && itr->second == 1 )
std::cout << "OK\n";
else
std::cout << "NG\n";
itr = mp.find("xyz");
if( itr != mp.end() && itr->first == "xyz" && itr->second == 9 )
std::cout << "OK\n";
else
std::cout << "NG\n";
itr = mp.find("aiueo");
if( itr == mp.end() )
std::cout << "OK\n";
else
std::cout << "NG\n";
std::map<std::string, int> mp;
mp["abc"] = 1;
mp["xyz"] = 9;
mp.erase("abc");
for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
cout << "mp[" << itr->first << "] = " << itr->second << "\n";
}
std::map<std::string, int> mp;
mp["abc"] = 1;
mp["xyz"] = 9;
auto itr = mp.find("abc");
mp.erase(itr);
for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
cout << "mp[" << itr->first << "] = " << itr->second << "\n";
}
std::map<std::string, int> mp;
std::cout << mp.empty() << "\n";
std::cout << mp.size() << "\n";
mp["abc"] = 123;
mp["xyz"] = 987;
std::cout << mp.empty() << "\n";
std::cout << mp.size() << "\n";
mp.clear();
std::cout << mp.empty() << "\n";
std::cout << mp.size() << "\n";