檢查C std::unordered_map中是否存在鍵的最有效范例？

我對現代 C 和使用外國代碼庫比較陌生。有一個函式接受 std::unordered_map 并檢查映射中是否存在鍵。代碼大致如下

uint32_t getId(std::unordered_map<uint32_t, uint32_t> &myMap, uint32_t id) 
{
   if(myMap.contains(id))
   {
     return myMap.at(id);
   }
   else
   {
     std::cerr << "\n\n\nOut of Range error for map: "<< id << "\t not found" << std::flush;
     exit(74);
   }
}

似乎呼叫contains()后跟at()是低效的，因為它需要雙重查找。所以，我的問題是，實作這一目標的最有效方法是什么？我還有一個后續問題：假設地圖相當大（約 60k 個元素）并且此方法被頻繁呼叫，上述方法有多大問題？

經過一番搜索，似乎以下范例比上述范例更有效，但我不確定哪個最好。

• 在構造myMap.at()內部呼叫try-catch

  • 優點：at如果密鑰不存在，則自動拋出錯誤
  • 缺點：try-catch顯然成本相當高，并且還限制了優化器可以對代碼執行的操作

• 采用find

  • 優點：一個電話，沒有try-catch開銷
  • 缺點：涉及使用迭代器；比僅僅回傳值更多的開銷

    auto findit = myMap.find(id);
    if(findit == myMap.end())
    {
      //error message;
      exit(74); 
    }
    else
    {
      return findit->first;
    }

uj5u.com熱心網友回復：

你可以做

// stuff before
{
    auto findit = myMap.find(id);
    if ( findit != myMap.end() ) {
        return findit->first;
    } else {
       exit(74);
    }
}
// stuff after

或使用新的 C 17 init 陳述句語法

// stuff before
if ( auto findit = myMap.find(id); findit != myMap.end() ) {
    return findit->first;
} else {
   exit(74);
}
// stuff after

兩者都僅在本地范圍內定義迭代器參考。由于最明確地優化了 interator 的使用，我會選擇它。幾乎可以肯定，進行第二次哈希計算會更慢。

另請注意，findit->first回傳key而不是value。我不確定您希望代碼做什么，但問題中的代碼片段之一回傳值，而另一個回傳鍵

uj5u.com熱心網友回復：

如果您在僅洗掉額外的查找操作時沒有獲得足夠的加速，并且如果在多執行緒程式中有數百萬次 getId 呼叫，那么您可以使用 N 路映射來并行化 id-檢查：

template<int N>
class NwayMap
{
    public:
    NwayMap(uint32_t hintMaxSize = 60000)
    { 
         // hint about max size to optimize initial allocations
         for(int i=0;i<N;i  )
             shard[i].reserve(hintMaxSize/N);
    }
    
    void addIdValuePairThreadSafe(const uint32_t id, const uint32_t val)
    {
        // select shard
        const uint32_t selected = id%N; // can do id&(N-1) for power-of-2 N value

        std::lock_guard<std::mutex> lg(mut[selected]);

        auto it = shard[selected].find(id);
        if(it==shard[selected].end())
        {
            shard[selected].emplace(id,val);
        }
        else
        {
            // already added, update?
        }
    }

    uint32_t getIdMultiThreadSafe(const uint32_t id)
    {
        // select shard
        const uint32_t selected = id%N; // can do id&(N-1) for power-of-2 N value

        // lock only the selected shard, others can work in parallel
        std::lock_guard<std::mutex> lg(mut[selected]);

        auto it = shard[selected].find(id);
        // we expect it to be found, so get it quicker
        // without going "else"
        if(it!=shard[selected].end())
        {
              return it->second;
        }
        else
        {
              exit(74);
        }
    }

    private:
    std::unordered_map<uint32_t, uint32_t> shard[N];
    std::mutex mut[N];
};

優點：

• 如果您從它們自己的 CPU 執行緒中提供每個分片的 getId，那么您將從 N*L1 快取大小中受益。

• 即使在單執行緒用例中，您仍然可以交錯多個 id-check 操作并受益于指令級并行性，因為檢查 id 0 將具有與檢查 id 1 不同的獨立代碼路徑，并且 CPU 可以對它們進行亂序執行（如果管道足夠長）

缺點：

• 如果來自不同執行緒的大量檢查發生沖突，它們的操作會被序列化，并且鎖定機制會導致額外的延遲

• 當 id 值大多是跨步時，由于位置不平衡，并行化效率不高

uj5u.com熱心網友回復：

• 在構造 myMap.at()內部呼叫try-catch
  • 優點：at如果密鑰不存在，則自動拋出錯誤
  • 缺點：try-catch顯然成本相當高，并且還限制了優化器可以對代碼執行的操作

您的getId終止應用程式的實作，那么誰在乎例外開銷？

請注意，大多數編譯器（全部 AFAIK）實作 C 例外以在不引發例外時具有零成本。當拋出例外并匹配例外處理程式時展開堆疊時會出現問題。我在某處讀到，拋出例外時的懲罰是 x40，與通過簡單回傳（可能帶有錯誤代碼）展開堆疊的情況相比。

由于您只想終止應用程式，因此此開銷可以忽略不計。

標籤：C 表现 性病 无序映射

上一篇：CryptoServicesRegistrar.isInApprovedOnlyMode()和CryptoServicesRegistrar.setApprovedOnlyMode(true)已在充氣

下一篇：需要找到改善現有查詢運行時間的方法