c++ - 哪种c++ STL数据结构对存储唯一值及其计数最有效？

Question

我有一个值列表，有一些重复出现，例如:{1,2,2,3,3,3,3,7,8,1}
我想在列表中将唯一值及其计数存储在数据结构中。

    --------------
    |value |count|
    --------------
    |  1   |  2  |
    --------------
    |  2   |  2  |
    --------------
    |  3   |  4  |
    --------------
    |  7   |  1  | 
    --------------
    |  8   |  1  |
    --------------

哪种c++标准库数据结构将是最有效的方法？
编辑:我不会以任何方式修改结构，我只想知道计数，因为计数将帮助我确定编程问题的输出。

Answer 1

首先请注意，要求“最高效”的数据结构并不能正确描述您的需求。您是否需要以下解决方案:

是最快使用的吗？在哪些用例中？

占用最少的内存？

是最易维护/可读的吗？

是最不容易出错的吗？

是最快写的吗？

与原始数据结构(对于未计数的值)并存吗？

您会发现，效率有不同的种类和方面。
话虽如此，您可以尝试:

@songyuanyao和@RahulGupta向您建议了一个简单明了的解决方案:使用 map -如果您想按递增顺序插入值(value)计数，则使用std::map；如果您不关心顺序，则使用std::unordered_map。这将易于编写和维护，并且在插入或删除元素的时间方面还可以。尽管如此，这两个映射结构都是quite slow，因此您可能会重新考虑是否需要标准库映射实现。

@KonradRudolph在注释中建议的一种替代解决方案-如果执行大量读取并且很少执行插入/更新操作，则在空间和时间方面会更有效率-std::pair<std::vector<value_type>, std::vector<count_type>>或std::vector<std::pair<value_type, count_type>>；并确保count_type足够大，以至于您不会超出它，但应尽可能小，以减少读取整个结构所需的时间。这些将比 map 占用更少的空间，因为没有存储区列表，没有空
请注意，在 vector 对或 vector 对之间进行选择是数据结构设计中的常见难题，也被称为“数组结构vs结构数组”或SoA vs AoS。在网站上可以看到concrete example，还有很多其他的。当您通常同时访问两个字段并同时需要相应的值时，AoS会更好。当您通常只需要一个字段时(例如，您想要对某个值范围之间的计数求和；或者您想要获得所有素值的集合等)，SoA会更好。这也与数据库的体系结构-row-oriented vs column-oriented有关，前者更适合事务处理，后者更适合分析工作负载。