std::map と std::unordered_map によるより特別なフレンド

最新の C++ には 8 つの連想コンテナーがありますが、特別な友達は std::map と std::unordered_map である必要があります。なんで?この投稿で説明させてください。

私の最後の投稿 C++ コア ガイドライン:std::array と std::vector はあなたの友達です。連想コンテナーについても同様のステートメントがあります。ユースケースの 95% では、std::map または std::unordered_map でまったく問題ありません。まれに、キーに関連付けられている値が必要ない場合があります。これらは不足している 5% です。この投稿を開始して、両方の連想コンテナーの概要と数値を説明する前に、今日の経験則を次に示します。 ::地図; std::unordered_map を使用しない場合。

最初の概要はこちら。詳細については、連想コンテナに関する以前の投稿をお読みください。

8 つのバリエーション

連想コンテナーの 8 つのバリエーションに順序を付けるには、3 つの質問に答える必要があります。各質問には、はいまたはいいえで答えることができます。 2 ^ 3 ==8. 3 つの質問は次のとおりです。

<オール>
  • コンテナは注文済みですか?
  • キーには関連する値がありますか?
  • 同じキーが複数存在する可能性はありますか?
  • そして、ここに答えがあります。

    <オール>
  • コンテナが順序付けされていない場合、それは順序付けられていないと呼ばれます。
  • キーに値が関連付けられている場合、それはマップと呼ばれます。設定されていない場合
  • コンテナが複数の同じキーを持つことができる場合、それはマルチと呼ばれます。
  • 順序付けられたコンテナーについて話すとき、キーの順序付けを意味します。

    おそらく、この分類法は複雑すぎたのでしょう。よりわかりやすい図を示しましょう。

    電話帳

    8 つのバリエーションは、電話帳の異なるバージョンです。電話帳とは何ですか?電話帳は、一連のキーと値のペアです。キー (姓) を使用して値 (電話番号) を取得します。

    電話帳の姓は、順序付きまたは順序なしにすることができ、電話帳は姓に関連付けられた電話番号を持つことも持たないこともでき、1 つだけの姓または複数の同一の姓を持つことができます。携帯電話番号と固定電話番号を電話帳に保存したい場合は、2 つの同一のキーを使用できることに非常に満足しています。

    この投稿の理由は、連想コンテナーについて説明するためではありません。理由は別のものです。順序付けされた連想コンテナへのアクセス時間は対数ですが、順序付けされていない連想コンテナへのアクセス時間は償却定数です。

    std::map と std::unordered::map のパフォーマンス

    std::unordered_map などの順序付けられていない連想コンテナーの償却定数アクセス時間は何を意味しますか?これは、電話番号のクエリが電話帳のサイズに依存しないことを意味します。あなたは私を信じていませんか?パフォーマンス テストをお見せしましょう。

    およそ 89,000 エントリの電話帳があります。エントリ数が 89,000,000 近くになるまで、サイズを 10 ずつ増やしていきます。各ステップの後、すべての電話番号を尋ねます。これは、すべての姓をランダムに使用することを意味します。

    次の画像は、最初の電話帳の一部を示しています。コロンで区切られた名前/番号のペアと、カンマで番号から区切られた名前を確認できます。

    プログラムは非常に読みやすいはずです。

    // telephoneBook.cpp
    
    #include <chrono>
    #include <fstream>
    #include <iostream>
    #include <map>
    #include <random>
    #include <regex>
    #include <sstream>
    #include <string>
    #include <unordered_map>
    #include <vector>
    
    using map = std::unordered_map<std::string, int>; // (1)
    
    std::ifstream openFile(const std::string& myFile){ 
    
     std::ifstream file(myFile, std::ios::in);
     if ( !file ){
     std::cerr << "Can't open file "+ myFile + "!" << std::endl;
     exit(EXIT_FAILURE);
     }
     return file;
     
    }
    
    std::string readFile(std::ifstream file){ 
     
     std::stringstream buffer;
     buffer << file.rdbuf();
     
     return buffer.str();
     
    }
    
    map createTeleBook(const std::string& fileCont){ 
     
     map teleBook; 
     
     std::regex regColon(":");
     
     std::sregex_token_iterator fileContIt(fileCont.begin(), fileCont.end(), regColon, -1);
     const std::sregex_token_iterator fileContEndIt;
     
     std::string entry;
     std::string key;
     int value;
     while (fileContIt != fileContEndIt){ // (2)
     entry = *fileContIt++;
     auto comma = entry.find(","); // (3)
     key = entry.substr(0, comma);
     value = std::stoi(entry.substr(comma + 1, entry.length() -1));
     teleBook[key] = value; // (4)
     }
     return teleBook;
     
    }
    
    std::vector<std::string> getRandomNames(const map& teleBook){ 
     
     std::vector<std::string> allNames;
     for (const auto& pair: teleBook) allNames.push_back(pair.first); // (5)
     
     std::random_device randDev;
     std::mt19937 generator(randDev());
     
     std::shuffle(allNames.begin(), allNames.end(), generator); // (6) 
     
     return allNames;
    }
     
    void measurePerformance(const std::vector<std::string>& names, map& m){ 
     
     auto start = std::chrono::steady_clock::now();
     for (const auto& name: names) m[name]; // (7)
     std::chrono::duration<double> dur= std::chrono::steady_clock::now() - start;
     std::cout << "Access time: " << dur.count() << " seconds" << std::endl;
     
    }
     
    int main(int argc, char* argv[]){
    
     std::cout << std::endl;
     
     // get the filename
     std::string myFile;
     if ( argc == 2 ){
     myFile= {argv[1]};
     }
     else{
     std::cerr << "Filename missing !" << std::endl;
     exit(EXIT_FAILURE);
     } 
     
     std::ifstream file = openFile(myFile);
     
     std::string fileContent = readFile(std::move(file));
     
     map teleBook = createTeleBook(fileContent);
     
     std::cout << "teleBook.size(): " << teleBook.size() << std::endl;
     
     std::vector<std::string> randomNames = getRandomNames(teleBook);
     
     measurePerformance(randomNames, teleBook); 
     
     std::cout << std::endl;
     
    }
    

    メインプログラムから始めましょう。ファイルを開き、コンテンツを読み取り、電話帳 (std::map または std::unordered_map) を作成し、ファミリ名の任意の順列を取得し、最後にパフォーマンス テストを行います。わかりました、これは簡潔すぎました。

    1行目は最も興味深いものです。 std::unordered_map は、std::map のインターフェースのスーパーセットをサポートします。これにより、パフォーマンス テストを行うのが非常に便利になります。最初に map =std::map; を使用してそれを行いました。次に、行を map =std::unordered_map; を使用するように変更しました。次の関係は、(std::set/std::unordered_set)、(std::mulitset、std::unordered_multiset)、および (std::multimap、std::unordered_multimap) のペアに適用されます。次の機能も非常に興味深いと思います:

    • createTeleBook
      • while ループは、正規表現 regColon によって作成されたすべての名前/番号トークンを反復処理します (2 行目)
      • 各トークンはコンマで区切られています (3 行目)
      • 最後に、名前と番号のペアが電話帳に追加されます (4 行目)
    • getRandomNames
      • すべての名前をベクトルに配置します (5 行目)
      • 名前をシャッフルします (6 行目)
    • パフォーマンスの測定
      • 電話帳の各名前を尋ねます (7 行目)

    そして最後に、std::map と std::unordered_map のパフォーマンス数値です。

    std::map

    std::unordered_map

    スクリーンショットは、電話帳の大きさを正確に示しています。最初の表に示したように、数字はアクセス時間を確認します。次のプロットは、std::map と std::unordered_map の間のパフォーマンスの関係を示しています。

    100,000 エントリの場合、std::map は std::unordered_map より 3 倍遅く、100,000,000 エントリの場合は 7 1/2 倍遅くなります。

    次は?

    この C++ コア ガイドラインからのちょっとした回り道の後、境界エラーとその回避方法について次の投稿で書きます。