vector与STL中的列表
我注意到有效的STL
vector是默认应该使用的序列的types。
这是什么意思？ 似乎忽略效率vector可以做任何事情。
任何人都可以向我提供一个场景， vector不是一个可行的select，但必须使用list ？
你想插入很多项目的地方，但重复序列的末尾。
检查每种不同types容器的复杂性保证：
标准容器的复杂性保证是什么？
向量：
- 连续的记忆。
- 为将来的元素预先分配空间，因此超出元素本身所需的额外空间。
- 每个元素只需要元素types本身的空间（没有额外的指针）。
- 可以在添加元素的任何时候为整个向量重新分配内存。
- 最后的插入是不变的，摊销的时间，但在其他地方的插入是昂贵的O（n）。
- vector末尾的擦除是恒定的，但其余的是O（n）。
- 你可以随机访问它的元素。
- 如果向vector添加元素或从vector中删除元素，则迭代器将失效。
- 如果您需要一组元素，则可以轻松地获取底层数组。
列表：
- 非连续的内存。
- 没有预先分配的内存。 列表本身的内存开销是不变的。
- 每个元素都需要额外的空间来存放元素，包括指向列表中下一个元素和前一个元素的指针。
- 从来没有必要为整个列表重新分配内存只是因为你添加一个元素。
- 插入和删除很便宜，无论它们在哪里出现。
- 将列表和拼接结合起来很便宜。
- 您不能随机访问元素，因此获取列表中的特定元素可能很昂贵。
- 即使添加或删除列表中的元素，迭代器仍然有效。
- 如果你需要一个元素的数组，你将不得不创build一个新的元素并将它们全部添加到它，因为没有底层数组。
一般来说，当你不关心你正在使用什么types的顺序容器的时候使用向量，但是如果你在容器中的任何地方进行了很多插入或擦除操作，除了结束之外，你会想要使用列表。 或者，如果你需要随机访问，那么你会想要vector，而不是列表。 除此之外，自然会根据您的应用程序需要一个或另一个，但总的来说，这些都是很好的指导方针。
如果你不需要经常插入元素，那么vector将会更有效率。 它比列表有更好的CPUcaching局部性。 换句话说，访问一个元素使得下一个元素很有可能出现在caching中，并且可以在不读取慢速RAM的情况下进行检索。
std :: list的一个特殊function是拼接（链接或将整个列表的一部分或整个列表移动到不同的列表中）。
或者，如果你的内容是非常昂贵的复制。 例如，在这种情况下，可能会比较便宜。
另外请注意，如果集合很小（并且内容的复制不是特别昂贵），即使在任何地方插入和擦除，vector仍然可能优于列表。 列表分配每个节点，这可能比移动一些简单的对象更昂贵。
我不认为有很严格的规定。 这取决于你最想做什么与容器，以及你期望容器有多大，包含的types。 一个向量通常胜过一个列表，因为它将其内容分配为一个连续的块（它基本上是一个dynamic分配的数组，在大多数情况下，数组是最有效的方法来保存一堆东西）。
这里的大多数答案错过了一个重要的细节：什么？
你想保留在遏制者什么？
如果它是一个int s的集合，那么std::list将在每个场景中松散，不pipe是否可以重新分配，只需从前面移除等等。列表的运行速度较慢，每次插入都会花费您与分配器的交互…准备一个例子，其中list<int>击败vector<int>是非常困难的。 即使如此， deque<int>可能会更好或者更接近，而不仅仅是列表的使用，这会有更大的内存开销。
然而，如果你正在处理大量的丑陋的数据 – 而且其中很less – 你不想在插入时重新定位，并且由于重新分配而复制将是一场灾难 – 那么你可能会更好一个list<UglyBlob>比vector<UglyBlob> 。
不过，如果您切换到vector<UglyBlob*>或甚至vector<shared_ptr<UglyBlob> > ，则列表将落后。
因此，访问模式，目标元素数量等仍然影响比较，但在我看来 – 元素大小 – 复制成本等。
那么我们class的学生似乎很难向我解释什么时候使用向量更有效，但是build议我使用列表的时候看起来相当高兴。
这是我的理解
列表 ：每个项目都包含下一个或上一个元素的地址，因此使用此function，即使未对项目进行sorting，也可以对项目进行随机化，顺序不会更改：如果内存碎片，则效率更高。 但是它也有一个很大的优势：你可以很容易地插入/删除项目，因为你唯一需要做的就是改变一些指针。 缺点：要读取随机的单个项目，您必须从一个项目跳转到另一个项目，直到find正确的地址。
vector ：当使用vector时，内存组织更像常规数组：每个第n项存储在第（n-1）项之后和第（n + 1）项之前。 为什么比列表好？ 因为它允许快速的随机访问。 这里是如何：如果你知道一个向量中的项目的大小，并且如果它们在内存中是连续的，那么可以容易地预测第n项目在哪里; 你不必浏览一个列表中的所有项目来阅读你想要的一个，用vector，直接阅读它，用你不能的列表。 另一方面，修改vector数组或者改变一个值要慢得多。
列表更适合跟踪可以在内存中添加/删除的对象。 如果要从大量单个项目访问元素，vector更合适。
我不知道列表是如何优化的，但是你必须知道，如果你想快速读取访问，你应该使用向量，因为STL系统的列表有多好，读取访问速度不会比向量快。
任何时候你都不能让迭代器失效。
当在序列中间有很多插入或删除的时候。 例如内存pipe理器。
基本上vector是一个具有自动内存pipe理的数组。 数据在内存中是连续的。 尝试在中间插入数据是一个代价高昂的操作。
在列表中，数据存储在不相关的存储位置。 在中间插入不涉及复制一些数据，为新的空间。
要更具体地回答您的问题，我将引用此页面
向量通常是访问元素以及从序列的末尾添加或移除元素的最有效的时间。 对于涉及插入或移除除了结尾之外的位置的元素的操作，它们比deques和列表执行更差，并且具有比列表更less的一致性迭代器和引用。
保持迭代器的有效性是使用列表的一个原因。 另一个是当你不想要一个向量重新分配时推送项目。 这可以通过reserve（）的智能使用来pipe理，但在某些情况下，使用列表可能会更容易或更可行。
当你想在容器之间移动对象时，你可以使用list::splice 。
例如，图分区algorithm可以有递增地在不断增加的容器数量之间分配的恒定数量的对象。 对象应该初始化一次，并始终保持在内存中的相同位置。 通过重新链接重新排列它比重新分配要快得多。
编辑：当库准备实现C ++ 0x时，将子序列拼接到列表中的一般情况随着序列的长度而变得线性复杂。 这是因为splice （现在）需要遍历序列来计算其中元素的数量。 （因为列表需要logging它的大小。）简单地计算和重新链接列表仍然比任何替代方法都快，并且拼接整个列表或单个元素是特殊情况，具有不变的复杂性。 但是，如果你有很长的序列拼接，你可能需要挖掘一个更好的，老式的，不兼容的容器。
必须使用list的唯一硬性规则是您需要将指针分发到容器元素的位置。
与vector不同，你知道元素的内存不会被重新分配。 如果可能的话，你可能会有指向未使用的内存，这至多是一个大的SEGFAULT ，最坏的是一个SEGFAULT 。
（从技术上讲， *_ptr的vector也可以，但是在这种情况下，你正在模拟list所以这只是语义）。
其他软规则与将元件插入容器中间的可能的性能问题有关，因此list将是优选的。
