我应该使用哪种容器来实现这个功能呢？

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进行排序。每次检索列表时，我都需要将其复制到某个容器中，例如，对其进行排序，然后再将其发送给用户，这也感觉很慢。

求助！

- Gam

---

回答这个问题需要比Stack Overflow问题所允许的更多的交流。如果您已经编写了代码来尝试解决问题，但它并没有正常工作，那么这是适合在这里讨论的。如果您的问题是“我该如何入门？”，那么就不适合在这里提问。 - mah

根据你的说法，如果我的代码能够工作但是很慢，那么我就不应该在stackoverflow上询问哪种容器可以解决它，因为我不知道？ - Gam

你并没有提供足够的信息。为什么以不同的方式检索甚至很重要呢？然而，一个简单的方法是使用std::vector，并维护两个副本 - 一个按价格排序，另一个按ID排序。此外，不要使用id作为const char *，而是使用std::string。这允许在运行时设置ID（例如基于用户输入），而不需要字符串字面值。 - Peter

你可以使用第二个容器来提供对现有set的快速索引，例如std::map<std::string, std::set<AppleClass>::iterator>。boost提供了一个多索引容器库来简化这个过程。 - Tony Delroy

@TonyD 谢谢，boost MultiIndex 看起来不错。 - Gam

Answer 1

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

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

编辑：

关于操作成本的详细说明：

所有这些操作对于哈希映射来说都是常数时间，因此这是关于优先队列的：

• 删除：如果将成本延迟到插入操作中，使用优先队列可以获得摊销成本为O(1)。有很多聪明的实现方法可以向您展示如何做到这一点。
• 插入：任何基本的优先队列实现都可以在O(log n)中完成，如果要保持常数时间的删除，则会变得有些棘手。
• 检索：对于此操作，您可以使用地图，无需查看优先队列。
• 更新：我认为没有比O(log n)更好的复杂度（即使是摊销的），平均情况下，您可能需要在优先队列中重新排列东西。

- yelsayed

---

你能解释一下，你是如何推导出渐进复杂度的吗？ - MikeMB