我应该使用哪个容器

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找到(所以我需要迭代所有这些).出于同样的原因,删除和插入会很慢.

这感觉是错误的选择.

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

救命!

Answer 1

您可以使用两个容器来完成此操作，一个容器按价格排序（优先级队列或链接列表），另一个容器索引您的 id（哈希映射）。为了节省空间，您可以让两个结构只保留指向Apple实例的指针，但您需要为此编写一个自定义排序函子。

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

编辑：

详细说明运营成本：

所有这些操作对于哈希映射来说都是恒定时间，所以这是关于优先级队列的：

• 删除O(1)：如果您将优先级队列的成本推迟到插入，您可以获得优先级队列的摊销成本。有很多巧妙的实现可以向您展示如何做到这一点。
• 插入：任何基本的优先级队列实现都会在 中执行此操作O(log n)，如果您想要恒定时间删除，则保持这种方式会有点棘手。
• 检索：您可以使用映射来执行此操作，无需查看优先级队列。
• 更新：我认为没有一种（简单）方法可以比O(log n)更新获得更好的复杂性，即使是摊销，对于平均情况，您可能必须在优先级队列中进行调整。