連想集合、連想配列

１．連想集合、連想配列

C#のHashSet、Dictionaryに対応するのが std::set / std::unordered_set、std::map / std::unordered_mapである。

ただし、set と map はツリー構造である。これに対して unordered_set, unordered_map はハッシュ構造である。 このため、一般には、unordered_set,unordered_map の方が抽出速度が速い。

２．プログラム例

#include <iostream>
#include <unordered_set>

using namespace std;
    
unordered_set<int> set;

void find(int n) {
    auto it = set.find(n);
    if (it == set.end()) cout << n << "はありません\n";
    else cout << n << "はあります\n";
}

int main() {
    set.insert(34);
    set.insert(55);
    set.insert(93);
    find(55);
    find(44);
}

mapをvectorに変換して，それをvalueの値でsortする [1]

unordered_map<int, int> mp_even;
vector<pair<int, int> > elem_even(mp_even.begin(), mp_even.end());
sort(elem_even.begin(), elem_even.end(),
     [](pair<int, int> a, pair<int, int> b) { return a.second > b.second; });

地図システムでの使用例

地図システムで std::unordered_set を使ってみた。関係部分の抜粋を下に示す。 レンダリング処理時間は 10ミリ秒のオーダーである。 find関数の実行時間は無視できるほど小さいと思うが、もし大きいようならば 自前でハッシュ関数を書いてみよう。

測定マシンの仕様は不明だが、ある測定では、100万回のfind実行時間が 680ms になっていた。 １回あたり 0.001ミリ秒にも満たないので、わがPCでも問題なく小さいであろう。

std::unordered_set<long>* faas[4] = { NULL };

void Render(int th, int minzoom, int maxzoom, int x, int y, int factor, int sock, Map* map) {
    if (minzoom >= 17 && maxzoom != -1) {
        std::unordered_set<long>* set = faas[minzoom-17];
        long xy = (((long)x) << 32) + y;
        auto it = set->find(xy);
        if (it == set->end()) return; // FFAではない
    }
    // レンダリング処理(省略)
}

void LoadFAA(int zoom, std::unordered_set<long>* set) {
    char path[256];
    sprintf(path, "/media/sf_gis/sys/faa/faa%d.dat", zoom);
    std::ifstream fin(path, std::ios::in | std::ios::binary);
    if (!fin){
        std::cout << "ファイル " << path << " が開けません\n";
        return;
    }
    while(!fin.eof()){  //ファイルの最後まで続ける
        long xy;
        fin.read((char*)&xy, sizeof(long));
        set->insert(xy); 
    }
    fin.close();  //ファイルを閉じる
}

        if (maxzoom >= 17 && faas[0] == NULL) {
            // 最初のリクエストで全データを読み込んでおく
            for (int zoom = 17; zoom <= 20; zoom++) {
                faas[zoom-17] = new std::unordered_set<long>();
                LoadFAA(zoom, faas[zoom-17]);
            }
        }
        Render(n, minzoom, maxzoom, x, y, factor, client_sockfd, map);

Ａ．リファレンス