この節では、3 つのプログラム例で map と multimap の使用例を説明します。例として、電話データベース、グラフ、用語索引を扱います。
注: 完全なプログラム例は、tele.cpp チュートリアルファイルにあります。
単純な電話番号のデータベースのプログラムの保守は、map に適した用途です。データベースは単純にインデックス付けされた構造で、人名や職業 (string) がキー値であり、電話番号 (long) が関連付けられたエントリです。このようなクラスは、以下のように書きます。
typedef map<string, long, less<string> > friendMap;
typedef friendMap::value_type entry_type;
class telephoneDirectory {
public:
void addEntry (string name, long number) // データベースに新しいエントリ
// を追加する
{ database[name] = number; }
void remove (string name) // データベースからエントリを削除する
{ database.erase(name); }
void update (string name, long number) // エントリを更新する
{ remove(name); addEntry(name, number); }
void displayDatabase() // データベース全体を表示する
{ for_each(database.begin(), database.end(), printEntry); }
void displayPrefix(int); // 接頭辞と一致するエントリを表示する
void displayByPrefix(); // 接頭辞によってソートされたデータベースを表示する
private:
friendMap database;
};
データベースでの単純な演算は、map コマンドによって直接的に実装されます。データベースへの要素の追加には insert、要素の削除には erase を使用し、更新にはこの 2 つを組み合わせて使用します。データベースのすべてのエントリを印刷するには、for_each() アルゴリズムを使用し、次の単純なユーティリティルーチンを各エントリに適用します。
void printEntry(const entry_type & entry)
{ cout << entry.first << ":" << entry.second << endl; }
次に、第 13 章で説明する、map で使用できるいくつかのアルゴリズムの使用方法を説明するために、少し複雑な演算の組み合わせを使用します。特定の 3 桁の初期接頭辞 1 が付いたすべての電話番号を表示するとします。クラス map の find() メンバー関数と混同しないように、find_if() 関数を使用し、最初のエントリを検出します。この位置から開始して、次に find_if() を呼び出すと、エントリが連続して表示されます。
void telephoneDirectory::displayPrefix(int prefix)
{
cout << "Listing for prefix " << prefix << endl;
friendMap::iterator where;
where =
find_if (database.begin(), database.end(),
checkPrefix(prefix));
while (where != database.end()) {
printEntry(*where);
where = find_if (++where, database.end(),
checkPrefix(prefix));
}
cout << "end of prefix listing" << endl;
}
この演算の述語には、データベースのエントリを示す pair という 1 つの引数だけを使用するブール型の関数が必要で、これは指定された接頭辞であるかどうかを示します。これに明らかに適した関数はなく、テスト接頭辞が引数として比較関数に渡されることはありません。この問題の解決策は、一般的な標準 C++ ライブラリ手法を適用することです。すなわち、クラスのインスタンスとして述語関数を定義し、クラスが作成されると初期化されるクラスのインスタンス変数としてテスト述語を格納します。目的の関数は、関数を呼び出すクラスの演算子として定義されます。
int prefix(const entry_type & entry)
{ return entry.second / 10000; }
class checkPrefix {
public:
checkPrefix (int p) : testPrefix(p) { }
int testPrefix;
bool operator () (const entry_type & entry)
{ return prefix(entry) == testPrefix; }
};
最後の例では、接頭辞によってソートされたディレクトリを表示します。map 自体の順序を変更することはできません。代わりに、逆の要素型の新しい map を作成し、値を新しい map へコピーすると、接頭辞によって値が順序付けられます。新しい map が作成されると出力されます。
typedef map<long, string, less<long> > sortedMap;
typedef sortedMap::value_type sorted_entry_type;
void telephoneDirectory::displayByPrefix()
{
cout << "Display by prefix" << endl;
sortedMap sortedData;
friendMap::iterator itr;
for (itr = database.begin(); itr != database.end(); itr++)
sortedData.insert(sortedMap::value_type((*itr).second,
(*itr).first));
for_each(sortedData.begin(), sortedData.end(),
printSortedEntry);
}
以下は、ソートされたエントリーの印刷に使用される関数です。
void printSortedEntry (const sorted_entry_type & entry)
{ cout << entry.first << ":" << entry.second << endl; }
注: このプログラムの実行可能バージョンは、graph.cpp ファイルにあります。
各要素自体が map である map は、指定されたグラフの自然な表現です。たとえば、都市名を符号化する文字列を使用して、エッジに関連付けられた値を、2 つの都市間の距離とする map を作成するとします。このグラフは、以下のように作成することができます。
typedef map<string, int> stringVector;
typedef map<string, stringVector> graph;
const string pendleton("Pendleton"); // 都市名の文字列を
// 定義する
const string pensacola("Pensacola");
const string peoria("Peoria");
const string phoenix("Phoenix");
const string pierre("Pierre");
const string pittsburgh("Pittsburgh");
const string princeton("Princeton");
const string pueblo("Pueblo");
graph cityMap; // map を保持するグラフを宣言する
cityMap[pendleton][phoenix] = 4; // グラフにエッジを追加する
cityMap[pendleton][pueblo] = 8;
cityMap[pensacola][phoenix] = 5;
cityMap[peoria][pittsburgh] = 5;
cityMap[peoria][pueblo] = 3;
cityMap[phoenix][peoria] = 4;
cityMap[phoenix][pittsburgh] = 10;
cityMap[phoenix][pueblo] = 3;
cityMap[pierre][pendleton] = 2;
cityMap[pittsburgh][pensacola] = 4;
cityMap[princeton][pittsburgh] = 2;
cityMap[pueblo][pierre] = 3;
stringVector 型は、string によってインデックス付けされた integer の map です。graph 型は、実質的に 2 次元の疎配列で、strings によってインデックス付けされ、integer 値を保持します。代入文のシーケンスは、グラフを初期化します。
多数の古典的なアルゴリズムを使用して、この形式で表現されるグラフを操作することが可能です。その一例に、ダイクストラ (Dijkstra) の最短経路アルゴリズムがあります。ダイクストラのアルゴリズムは、初期地点として指定された特定の都市から開始します。距離/都市の priority queue の pair が作成され、開始都市からの距離で初期化されます (すなわち、0)。距離の pair のデータ型の定義は、次のとおりです。
struct DistancePair {
unsigned int first;
string second;
DistancePair() : first(0) { }
DistancePair(unsigned int f, const string & s)
: first(f), second(s) { }
};
bool operator < (const DistancePair & lhs, const DistancePair & rhs)
{ return lhs.first < rhs.first; }
次のアルゴリズムでは、各ステップで、最大ではなく最小の値をコレクションから引き出そうとするため、条件付きテストが priority queue で逆になることに注意してください。ループの反復のたびに、queue から都市を引き出します。都市への最短経路が見つからない場合は、現在の距離が記録され、グラフを検証することによって、この都市から隣接する各都市への距離を計算することができます。この処理は、priority queue がすべて処理されるまで続きます。
void shortestDistance(graph & cityMap,
const string & start, stringVector & distances)
{
// 都市への距離の priority queue を処理する
priority_queue<DistancePair, vector<DistancePair>,
greater<DistancePair> > que;
que.push(DistancePair(0, start));
while (! que.empty()) {
// queue から最も近い都市を引き出す
int distance = que.top().first;
string city = que.top().second;
que.pop();
// まだ検出されない場合は、処理する
if (0 == distances.count(city)) {
// 最短距離 map に追加する
distances[city] = distance;
// 値を queue に入れる
const stringVector & cities = cityMap[city];
stringVector::const_iterator start = cities.begin();
stringVector::const_iterator stop = cities.end();
for (; start != stop; ++start)
que.push(DistancePair(distance + (*start).second,
(*start).first));
}
}
}
これは vector、map、string、priority queue を使用する比較的単純なアルゴリズムであることに注意してください (第 11 章)。
用語索引は、各語句が発生する行番号を示すテキスト内の語句の、アルファベット順一覧です。
用語索引は map および multimap のコンテナクラスの使用を示すために開発されたものです。データ値は multimap による用語索引で維持され、string (語句) でインデックス付けされ、integer (行番号) を保持します。同じ語句が複数の異なる行に表示されることがあるため、multimap が適用されます。事実、このような関係を見つけ出すことが、用語索引の主要な目的の 1 つです。もう 1 つの map 使用の可能性は、関連付けられた値として整数要素の set を使用することです。
class concordance {
typedef multimap<string, int less <string> > wordDictType;
public:
void addWord (string, int);
void readText (istream &);
void printConcordance (ostream &);
private:
wordDictType wordMap;
};
用語索引の作成は 2 つのステップに分けられます。すなわち、プログラムが入力ストリームから行を読み取って用語索引を生成するステップと、結果を出力ストリームに出力するステップです。これは、2 つのメンバー関数 readText() と printConcordance() に反映されます。1 つ目は readText() で、次のように書かれます。
void concordance::readText (istream & in)
{
string line;
for (int i = 1; getline(in, line, "\n"); i++) {
allLower(line);
list<string> words;
split (line, " ,.;:", words);
list<string>::iterator wptr;
for (wptr = words.begin(); wptr != words.end(); ++wptr)
addWord(*wptr, i);
}
}
行は 1 行ごとに入力ストリームから読み取られます。まず、行のテキストが小文字に変換され、次に 12.3 節 に記述されている関数 split() を使用して行が語句に分割されます。各語句は用語索引に入力されます。用語索引への値の入力に使用されるメソッドは、次のとおりです。
void concordance::addWord (string word, int line)
{
// list に word が出現するかどうか検証する
// 最初に同じキーのエントリーの範囲を取得する
wordDictType::iterator low = wordMap.lower_bound(word);
wordDictType::iterator high = wordMap.upper_bound(word);
// エントリーをループし、現在の行と一致する行があるかどうか確認する
for ( ; low != high; ++low)
if ((*low).second == line)
return;
// 出現しない、追加する
wordMap.insert(wordDictType::value_type(word, line));
}
addWord() の大部分は、1 行に同じ語句が 2 回発生する場合、値が語句 map で重複しないようにするために費やされます。これを確実にするために、キーと一致する値の範囲が検証され、各値がテストされた結果、一致する行番号がない場合は挿入が実行されません。行番号が検出されることなくループが終了した場合に限り、新しい語句/行番号の組み合わせが挿入されます。
最後のステップは用語索引の出力です。これは、次のように実行されます。
void concordance::printConcordance (ostream & out)
{
string lastword("");
wordDictType::iterator pairPtr;
wordDictType::iterator stop = wordMap.end();
for (pairPtr = wordMap.begin(); pairPtr != stop; ++pairPtr)
// 語句が前の語句と同じである場合、行番号だけが出力される
if (lastword == (*pairPtr).first)
out << " " << (*pairPtr).second;
else { // 語句の最初のエントリー
lastword = (*pairPtr).first;
cout << endl << lastword << ": " << (*pairPtr).second;
}
cout << endl; // 最後の行の終了
}
反復子ループは、語句一覧で維持される要素の循環に使用されます。新しい語句ごとに新しい出力行が生成され、その後、空白で区切られた行番号が表示されます。たとえば、入力がテキストの場合は以下のようになります。
It was the best of times,
it was the worst of times.
best から worst までの出力は次のようになります。
|
best: |
1 |
|
it: |
1 2 |
|
of: |
1 2 |
|
the: |
1 2 |
|
times: |
1 2 |
|
was: |
1 2 |
|
worst: |
1 |