我應該使用哪個容器

比方說，我想擁有一個具有不同價格的蘋果容器。我希望他們總是按照他們的價格排序（最高價格第一），但我也想通過他們的ID快速找回他們。我至今是以下我應該使用哪個容器

struct AppleClass 
{ 
    string id; 
    int price; 

    bool operator<(const AppleClass& o) const 
    { 
     return price > o.price; 
    } 
}; 

int main() 
{ 
    set<AppleClass> myapples; 
    myapples.insert({"apple1", 500}); 
    myapples.insert({"apple2", 600}); 
    myapples.insert({"apple3", 400}); 

    for (auto& apple : myapples) 
    { 
     cout << apple.id << "," << apple.price << endl;   
    } 
}

http://ideone.com/NcjWDZ

我的應用程序將花費20％的是時間刪除條目，20％的插入項，25％的檢索它們（檢索整個列表），以及35 ％更新它們（價格會增加或減少）。

容器最多有450個條目。

我的代碼只解決排序問題。查找是無用的，因爲我想通過他們的ID找到（所以我需要遍歷所有這些）。由於同樣的原因，刪除和插入操作會很慢。

這感覺就像是錯誤的選擇。

但是，如果我有地圖，那麼它將根據ID進行排序。每次檢索列表時，我都必須將其複製到某個容器中，然後將其排序，然後將其發送給用戶，這也感覺很慢。

幫助！

來源

2016-05-09 James

要解決這個問題需要多一點堆棧溢出問題的可接受性。如果您已經編寫了代碼來嘗試解決您的問題，並且它不能正常工作，那麼這裏就是主題。如果你的問題是「我怎麼開始使用它？」不是。 – mah

@mah因此，根據你，如果我的代碼工作，但速度慢，那麼我不應該問在stackoverflow哪個其他容器會解決它？因爲我不知道？ – James

你還沒有真正提供足夠的信息。爲什麼以不同方式檢索甚至是重要的？然而，一個簡單的方法是使用'std :: vector'，並保留兩個副本 - 一個按價格排序，另一個按ID排序。此外，而不是'id'是'const char *'，使用'std :: string'。這允許將id設置爲運行時間（例如基於用戶輸入），而不是要求字符串文字。 – Peter

您可以使用兩個容器（一個保持按價格排列）（優先隊列或鏈接列表）和一個索引您的id（哈希映射）的容器。爲了節省空間，你可以讓這兩個結構只保留指向你的Apple實例的指針，但你需要爲此編寫一個自定義的分類函子。

這樣，您的輸入刪除是O(1)，插入是O(log n)，檢索也是O(1)，更新是O(log n)。我認爲這應該很好，特別是當你處理這麼少的項目時（450）。

編輯：

在闡述運營成本：

所有這些操作都是恆定的時間哈希映射，所以這是對優先級隊列：

去除：可以如果您推遲插入成本，請使用優先級隊列獲得O(1)的攤銷成本。有很多聰明的實現可以告訴你如何做到這一點。
插入：任何基本的優先級隊列實現都會在O(log n)中執行此操作，如果要持續不斷地刪除，那麼保持這種方式會有點棘手。
檢索：您使用此地圖，無需查看優先級隊列。
正在更新：我認爲沒有一種（簡單）的方法可以獲得比O(log n)更好的更新複雜度，甚至可以攤銷，但您可能必須在優先級隊列中對所有情況進行洗牌。

來源

2016-05-09 02:24:22 yelsayed

你能解釋一下，你是如何得出漸近的複雜性的？ – MikeMB

當然，我編輯了答案。 – yelsayed

我應該使用哪個容器

回答

相關問題