哪种 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

您可以在 C++ 中使用地图声明可以做为

map<int,int>map_name;

为了插入你可以运行一个循环

for(auto itr:list_name)
    map_name[itr]++;

for(auto c:map_name)
cout << c.first << " " << c.second << endl;

Answer 2

首先请注意，要求“最有效”的数据结构并不是对您的要求的恰当描述。您想要一个解决方案吗：

用起来最快？在什么情况下使用？
占用内存最少？
最多maintainable/readable?
是最不容易出错的吗？
是写的最快吗？
与原始数据结构一起存在（对于未计算的值），还是取而代之？

你看，效率有不同的种类和方面。

话虽如此，你可以试试：

@songyuanyao 和@RahulGupta 向您建议了一个简单直接的解决方案：使用地图 - 如果您想按递增顺序对值计数进行交互，则使用 std::map，或者std::unordered_map 如果您不关心顺序。这将易于编写和维护，并且在插入或删除元素的时间方面还算可以。不过，这两个映射结构都是，因此您可能会重新考虑是否需要标准库映射实现。
@KonradRudolph 在评论：std::pair<std::vector<value_type>, std::vector<count_type>> 或 std::vector<std::pair<value_type, count_type>>；并确保 count_type 足够大，不会超过它，但要尽可能小，以减少阅读整个结构所需的时间。这些将使用 lot 比地图少 space，因为没有 bucket-lists，没有空

请注意，vector-of-pairs 还是 pair-of-vectors 之间的选择是数据结构设计中的常见困境，也称为“数组结构 vs 结构数组”，或 SoA vs AoS。请参阅 concrete example here on the site and there are many others. AoS is better when you usually access both fields, and need the corresponding values together; SoA is better when you often need just one field (e.g. you want to sum up the counts between some range of values; or you want to obtain the set of all prime values etc.) This also relates to the architecture of databases - row-oriented vs column-oriented，前者更适合事务处理，后者更适合分析工作负载。

哪种 C++ stl 数据结构对于存储唯一值及其计数最有效？

which c++ stl data structure will be the most efficient for storing unique values and their counts?

c++

performance

data-structures

c++-standard-library