c++ - 维护对象的有序集合

Question

我对对象集合有以下要求:

• 动态大小(理论上没有限制，但实际上几千应该绰绰有余)
• 已排序，但允许在任意位置重新排序和插入。
• 允许删除
• 索引访问 - 随机访问
• 计数

我存储的对象并不大，只有几个属性和一两个小数组(256 个 bool 值)

在编写链表之前，有没有我应该了解的内置类？

Answer 1

原始答案:这听起来像标准库中的 std::list(双向链表)。

新答案:更改规范后，std::vector 可能会起作用，只要元素不超过几千个并且 vector 中间的插入和删除次数不多。中间插入和删除的线性复杂性可能被 vector 操作上的低常量所抵消。如果您只是在开始和结束处进行大量插入和删除操作，std::deque 可能也能正常工作。