c++ - 有序集/ map 的计数功能

Question

container.count(val) - 给出容器中“val”的频率。为什么 count 需要为有序集中的每个值“val”遍历直到结束。我的观点是对于有序集合/映射，元素将按顺序排列，因此我们甚至可以在到达终点之前获得计数的最终值。我明白，这不适用于其他容器(列表、 vector 等)。

例子:-

set<int, less<int>> s{1, 2, 3, 4, 5, 6};
int cnt = s.count(2);  // return 1

因为 set/map 可以计数为 0 或 1，一旦我达到 2，它应该打破循环而不是遍历到结束。此外，编译器知道比较器(更少或更大)。 multiset/multimap 也可以这样做，唯一的区别是计数可以 >1。

Answer 1

来自 n4618 ，第 23.2.6 节，第 848 页

关联容器要求

Expression: b.count(k)
Return type: size_type
Assertion/note/pre-/post-condition: returns the number of elements with key equivalent to k
Complexity: log(b.size()) + b.count(k)

这意味着，根据定义，这些函数无法在确定 k 的计数是多少之前对容器中的每个元素进行计数。