关联式容器

[Xeonacid]

https://oi-wiki.org/lang/csl/associative-container/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[DeterCider]

为什么说了是个有排序的容器，却不说默认排序的顺序……

[lnw143]

set 中不会出现值相同的元素，那 count(x) 还有什么意义

[Draudnaut]

算法竞赛里面估计没啥意义。工程里面主要是维持和别的容器类的兼容性吧。

[lnw143]

主要是反馈的结果是错的，insert 了两次，count 返回一个 1

[Draudnaut]

insert同一个值么，那这个返回是正确的呀。count反映的是容器内部某个元素的个数。同样的元素不会被插入两次的。set里面的count只有0和1两种回值。

[lnw143]

懂了，一直以为 set 设计有问题

[lnw143]

谢谢

[yhddd123]

lower_bound(s.begin(),s.end(),v) 的复杂度是 log 还是 log^2 还是 O(n)？

[yhddd123]

实践证明 n=200000 跑不动。但是 O(n) 怎么解释？如果是直接找，指针移动不用 n log n 吗

[alphagocc]

难道不应该是 s.lower_bound(x) 吗？

[Draudnaut]

lower_bound肯定是log啊，亲手试了一下，200000没问题，测试代码应该写错了吧。https://en.cppreference.com/w/cpp/algorithm/lower_bound

[lnw143]

注意 Complexity 下面有

However, if ForwardIt is not a LegacyRandomAccessIterator, the number of iterator increments is linear in N. Notably, std::map, std::multimap, std::set, and std::multiset iterators are not random access, and so their member lower_bound functions should be preferred.