c++ - 我应该使用哪个容器

Question

假设我想要一箱价格不同的苹果。我希望它们始终按价格排序(最高价格在前)，但我也想按 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 查找(所以我需要遍历所有这些)。出于同样的原因，删除和插入会很慢。

感觉是错误的选择。

但是如果我有一张 map ，那么它将根据 id 进行排序。每次我检索列表时，我都必须将它复制到某个容器中，例如，订购它，然后将它发送给用户，这也感觉很慢。

帮助!

Answer 1

您可以使用两个容器来做到这一点，一个按价格排序(优先级队列或链表)，另一个为您的 ID 编制索引( HashMap )。为了节省空间，您可以让这两个结构只保留指向您的 Apple 实例的指针，不过您需要为此编写自定义排序仿函数。

这样，你的条目删除是O(1)，插入是O(log n)，检索也是O(1)，并且更新是 O(log n)。我认为这应该很好，尤其是当您处理的项目数量如此之少 (450) 时。

编辑:

详细说明运营成本:

所有这些操作对于hash map来说都是常量时间，所以这是关于优先级队列的:

• 删除:如果您将成本推迟到插入，则优先级队列的摊销成本为 O(1)。有许多巧妙的实现方式可以向您展示如何做到这一点。
• 插入:任何基本的优先级队列实现都将在 O(log n) 中执行此操作，如果您想要固定时间删除，保持这种方式会有点棘手.
• 检索:您为此使用 map ，无需查看优先级队列。
• 更新:我不认为有一种(简单的)方法可以比 O(log n) 更复杂地更新，即使是摊销，你可能会对于一般情况，必须在优先级队列中洗牌。