使用元素鍵迭代STL容器

Question

我需要一些幫助來選擇一個有效的算法，將元素從一個向量放入預分類的桶中 - 或理想地輸出迭代器範圍（因爲它們效率很高）。下面的例子完全是人爲設計的，但想法是使用一個元素的關鍵字來確定輸出存儲區。我不要求如何進行排序，因爲這是簡單地調用一個很簡單的事情（根據其關鍵工程和重新排序元素）

std::sort(testVec.begin(), testVec.end(), comparator); 

我把live example上coliru，它是非常容易修改和修復（很簡單，或者我不會問這個問題）。我也可以通過這個有序列表中的元素，而鍵值是相同的，將它附加到一個新的桶中，但我正在尋找更像自然界中的STL，現在上面的味道有點像最後的解決辦法，最終的解決方案也需要高效，因爲testVec可能很大，而且對象也很大。我不想修改testvec - 所以它應該是不可變的。

理想情況下，我正在尋找某種類型的構造，吐出範圍迭代器或類似效率的東西。實際的對象很大，所以傳遞引用或移動它們是唯一的選擇 - 我的實際對象（相當於MyStr）是可移動的。某種關鍵的foreach，應用關鍵謂詞或者我找不到的是我正在尋找的東西。我硬編碼下面的3個桶，以顯示我需要達到什麼 - 這完全是一種破解。

預先感謝這個問題

#include <string> 
#include <iostream> 
#include <sstream> 
#include <iterator> 
#include <vector> 
#include <algorithm> 

struct MyStr 
{ 
    int key; 
    std::string strval; 

    MyStr(int key, const std::string& rStrVal) 
     : key(key) 
     , strval(rStrVal) 
    {} 

    // let stream operators be friend functions instead of members! 
    inline friend std::ostream& operator << (std::ostream& os, const MyStr& val) { 
     os << "key[" << val.key << "], strval['" << val.strval << "']"; 
     return os; 
    } 

    bool operator < (const MyStr& str) const { 
     return (key > str.key); 
    } 
}; 

int main() 
{ 
    std::vector <MyStr> testVec = { 
     MyStr(4, "key 4"), 
     MyStr(3, "key 3"), 
     MyStr(3, "key 3"), 
     MyStr(2, "key 2"), 
     MyStr(2, "key 2"), 
     MyStr(2, "key 2") 
    }; 

    //auto comparator = [](const MyStr& lhs, const MyStr& rhs) { 
    // return lhs.key < rhs.key; 
    //}; 

    std::vector <MyStr> foursBucket; 
    std::vector <MyStr> threesBucket; 
    std::vector <MyStr> twosBucket; 

    auto ostriter = std::ostream_iterator<MyStr>(std::cout, ","); 
    std::for_each(testVec.begin(), testVec.end(), 
     [&](const MyStr& next){ 
      switch (next.key) { 
      case 4: 
       foursBucket.push_back(next); 
       break; 
      case 3: 
       threesBucket.push_back(next); 
       break; 
      case 2: 
       twosBucket.push_back(next); 
       break; 
      } 
     }); 
    std::cout << "Elements with Key Value 2" << std::endl; 
    std::copy(twosBucket.begin(), twosBucket.end(), ostriter); 
    std::cout << std::endl; 
    std::cout << "Elements with Key Value 3" << std::endl; 
    std::copy(threesBucket.begin(), threesBucket.end(), ostriter); 
    std::cout << std::endl; 
    std::cout << "Elements with Key Value 4" << std::endl; 
    std::copy(foursBucket.begin(), foursBucket.end(), ostriter); 
    std::cout << std::endl; 
} 

任何幫助，將產生以下輸出

Elements with Key Value 2 
key[2], strval['key 2'],key[2], strval['key 2'],key[2], strval['key 2'], 
Elements with Key Value 3 
key[3], strval['key 3'],key[3], strval['key 3'], 
Elements with Key Value 4 
key[4], strval['key 4'], 

正如你所看到的結構非常簡單，我展示瞭如何我可以現在排序使用謂詞的對象，但我不知道選擇哪種算法來高效迭代

Answer 1

您正在尋找一個unordered_multimap。它是一個無序的關聯容器，將根據密鑰的哈希值（在以下示例中爲int）將鍵值對放入桶中。

std::unordered_multimap<int, std::string> 
    mymap{{4, "key 4"}, 
      {3, "key 3"}, 
      {3, "key 3"}, 
      {2, "key 2"}, 
      {2, "key 2"}, 
      {2, "key 2"}, 
     }; 

for(auto const& kv : mymap) { 
    std::cout << "key: " << kv.first << " value: " << kv.second << '\n'; 
} 

輸出：

key: 2 value: key 2 
key: 2 value: key 2 
key: 2 value: key 2 
key: 3 value: key 3 
key: 3 value: key 3 
key: 4 value: key 4 

Live demo

---

在下面你註釋澄清，收到一個輸入vector<MyStr>，並且容器類型不能改變。在這種情況下，使用std::equal_range來查找包含特定鍵的所有元素。

// comparator for equal_range 
struct comp 
{ 
    bool operator()(int key, MyStr const& m) const { return m.key < key; } 
    bool operator()(MyStr const& m, int key) const { return key < m.key; } 
}; 

// sort the vevctor 
std::sort(testVec.begin(), testVec.end()); 

// search for all elements with key=2 
auto range = std::equal_range(testVec.begin(), testVec.end(), 2, comp()); 

for(auto it = range.first; it != range.second; ++it) { 
    std::cout << "key: " << it->key << " value: " << it->strval << '\n'; 
} 

輸出：

key: 2 value: key 2 
key: 2 value: key 2 
key: 2 value: key 2 

Live demo

---

遍歷每個獨特的鍵，最簡單的方法是使用std::unique_copy創建僅持有具有獨特元素的新容器鍵。然後遍歷這個容器並在每個鍵上使用equal_range。

bool operator==(MyStr const& m1, MyStr const& m2) { return m1.key == m2.key; } 

// sort the vevctor 
std::sort(testVec.begin(), testVec.end()); 

std::vector<MyStr> unique_keys; 
std::unique_copy(testVec.begin(), testVec.end(), std::back_inserter(unique_keys)); 

for(auto const& u : unique_keys) { 
    std::cout << "Searching for key: " << u.key << '\n'; 
    auto range = std::equal_range(testVec.begin(), testVec.end(), u.key, comp()); 

    for(auto it = range.first; it != range.second; ++it) { 
     std::cout << "key: " << it->key << " value: " << it->strval << '\n'; 
    } 
} 

Live demo

如果元素複製昂貴的，你寧願避免創建一個新的集裝箱保持獨特的元素，你可以創建自己的輸出迭代器，模仿std::back_insert_iterator。它的operator=實現將會採取MyStr const&的參數，但是push_back只能將參數中的密鑰存入唯一密鑰容器中，在這種情況下應該是vector<int>。

另一種可以避免修改輸入範圍並避免將元素複製到新範圍的方法是創建vector<MyStr *>，其中每個元素指向相應的元素在原來的範圍內。然後重複上述所有步驟，但不要將vector::iterator s傳遞給算法，請使用boost::indirect_iterator。此迭代器將對容器中的指針應用額外級別的解引用，然後算法應該像在vector<MyStr>上運行一樣。