從指針集合中快速檢索特定對象

我想要拿出從最有效莊園中的容器（地圖，矢量，）訪問/檢索對象的技術。從指針集合中快速檢索特定對象

所以，如果我有對象：

class Person 
{ 
    public: 
     string name; 
     unsigned int ID; // unique ID 
     double deposit; 
}; 

// And then I have a vector of pointers to person objects 
std::vector <Person*> people; 

Person* getPerson(string nName); 
Person* getPerson(unsigned int nID); // what would be a good method to quickly identify/retrieve the correct Person object from my vector?

我的想法：

這是迭代的解決方案，它是沒有效率的：

Person* getPerson(string nName) 
{ 
    for (int i=0; i<people.size(); i++) 
    { 
     if (people[i]->name == nName) { return people[i]; } 
    } 
}

另一種方式：有2個地圖

map <string, Person*> personNameMap; 

Person* getPerson(string nName) 
{ 
    return personNameMap[nName]; 
} 

map <string, Person*> personIDMap; 
Person* getPerson(unsigned int nID) 
{ 
    char id[2]; 
    atoi(nID, id, 10); // or is it itoa? 
    return personNameMap[id]; 
}

任何其他想法如何我可以存儲&從一個快速的&高效莊園收集我的對象？

來源

2011-05-05 user593747

地圖是在C查找最快的集裝箱++，如果指數是不是整數我希望這是一個好

來源

2011-05-05 11:06:18 Mayank

好的，但我希望能夠通過他們的名字和他們的ID（號碼）來查找Person的名字，那麼你會怎麼做 - 創建2個容器，按名稱查找地圖，查找時創建矢量/數組由ID。或者你會使用模板化功能來做到這一點？我正在學習用於組織和從集合中檢索對象的技術。 – user593747 2011-05-05 11:09:40

保留兩個容器。一張地圖 nameToIdMap。和一個矢量。但是，id和索引應該匹配。當你想用它查找時，只需返回objVec [index]'（其中索引應該是id）'。在使用名稱作爲關鍵字從地圖名稱搜索索引的情況下，返回objVec [index]。但爲了高效工作，您需要知道向量的大小，以便在填充之前對其進行初始化。然後填寫像objVec [id] =「Person」這樣的矢量，並避免ppush_back。 – Mayank 2011-05-05 11:17:23

std::map存儲其元素平衡的樹結構，並提供相當不錯的查找速度。但是插入std::map由於相同的原因在順序容器中較慢。所以map是你的選擇，如果你有很多外觀和相當少量的插入。

除此之外，我不明白爲什麼你製作map <string, Person*> personIDMap;而不是map <unsigned int, Person*> personIdMap。

來源

2011-05-05 11:08:23 beduin

感謝您的回覆。是的，我是地圖新手，我把它們看作是Python Dictionary，所以我必須擺脫我的頭腦，只有字符串可以用作鍵。你有什麼建議使用什麼技術來快速查找/檢索指針對象？或者你會做2個有序的地圖（按名稱（字符串作爲鍵））＆（通過ID（無符號整型作爲鍵））？ – user593747 2011-05-05 11:16:24

根據您的目的，您可以使用由Mayank提出的兩個'map'或解決方案。如果更頻繁地使用'by name'查找，那麼'two maps'似乎更好，如果使用'by name'和'by id'查找的頻率相等，則map + vector'解決方案更好。在這兩種情況下，你必須提供一致性（在兩張地圖之間或地圖和矢量之間）。 – beduin 2011-05-05 11:38:21

std::map是一個平衡樹，即O(log n)步驟進行搜索。 Boost offersboost::unordered_map這是一個哈希映射。它漸近地變差（O(n^2)），然而，它的平均表現更好。取決於容器的完整性，它是1-3個不變的步驟。一旦容器被裝滿（這意味着密鑰的值會耗盡），將會出現越來越多的衝突，並且性能會迅速下降。在大多數實現中，這發生在大約80％的飽滿度。在大多數情況下這不是問題，但要注意這個限制。

來源

2011-05-05 11:16:51

感謝您的回覆。當你說完整時，比如說我們正在談論一個使用字符串作爲鍵的地圖，當性能開始下降時地圖有多大。我知道你說的是80％，但是在大小方面，如果字符串鍵的長度必須<= 3個字符，那麼是10000？ – user593747 2011-05-05 11:21:16

大多數編譯器確實提供了散列映射，可以在'std :: tr1 :: unordered_map'或舊的SGI名稱'std :: hash_map'下（儘管VisualC++在簽名上與SGI版本稍有不同）。支持C++ 0x的編譯器提供它爲'std :: unordered_map'。這通常與增強版本相同。 – 2011-05-05 11:27:30

這對於'map'來說不是問題，因爲這是一棵平衡的樹（紅黑樹，我想，但我不確定）。我不認爲10000會是unordered_map的問題。（10000 /（256^3）小於80％）。 – 2011-05-05 11:31:10

從指針集合中快速檢索特定對象

回答

相關問題