c++ - 从序列中插入和删除 C++

Question

我在一本书上读到过这个，我正在准确地粘贴文本。我截图了但是reputation不够用所以...

Sequences

You can refine the basic container concept by adding requirements.The sequence is an important refinement because several of the STL container types—deque, forward_list (C++11), list, queue, priority_queue, stack, and vector—are sequences. (Recall that a queue allows elements to be added at the rear end and removed from the front.A double- ended queue, represented by deque, allows addition and removal at both ends.) The requirement that the iterator be at least a forward iterator guarantees that the elements are arranged in a definite order that doesn’t change from one cycle of iteration to the next. The array class also is classified as a sequence container, although it doesn’t satisfy all the requirements. The sequence also requires that its elements be arranged in strict linear order.That is, there is a first element, there is a last element, and each element but the first and last has exactly one element immediately ahead of it and one element immediately after it.An array and a linked list are examples of sequences, whereas a branching structure (in which each node points to two daughter nodes) is not.

Because elements in sequence have a definite order, operations such as inserting values at a particular location and erasing a particular range become possible.Table 16.7 lists these and other operations required of a sequence.The table uses the same notation as Table 16.5, with the addition of t representing a value of type T—that is, the type of value stored in the container, of n, an integer, and of p, q, i, and j, representing iterators.

第二段的开头，它说序列有一定的顺序来维护，因此插入和删除元素是可能的。这不会破坏维持特定秩序的整个过程吗？请帮忙。这让我发疯。谢谢。

Answer 1

有些容器是有序的，有些是有序的，有些两者都是，有些两者都不是。例如:

std::list 和 std::vector 是有序的，但未排序(除非你去别挡道)。

std::map 和 std::set 都是sorted 和ordered。

std::unordered_map 和 std::unordered_set 是无序 和未排序(它们基本上是 HashMap )

insert、delete、push、pop等函数都考虑到了这些容器需求。对于已排序的容器，insert 必须保证元素插入到正确的位置，其余元素根据需要调整。

一个序列必须是有序的，但不一定是有序的。

因此，当您说要在索引 i 处插入元素 e 时，该概念仅对有序容器有意义，因为无序容器没有索引或职位。

你必须注意的一件事(除其他外)是如果你有一个容器的迭代器，经常修改容器(插入、删除等)可能会使该迭代器无效，这会导致诸如 erase-remove idiom 之类的事情

这是一个(有点不完整的)图表，显示了各种 C++ 标准库容器的属性。

_{由 David Moore 和 licensed CC BY-SA 3.0 创建}