Inserting and deleting from sequences C++

Question

I read this in a book and am exactly pasting the text. I took a screenshot but not enough reputation so...

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.

The starting of the second paragraph, it says that sequences have a certain order to maintain and so inserting and deleting elements is possible. Doesn't that ruin the whole thing about maintaining a certain order? Please help. This is driving me mad. Thanks.

Answer 1

Some containers are ordered, some are sorted, some are both, some are neither. For example:

std::list and std::vector are ordered, but not sorted (unless you go out of your way to do so).

std::map and std::set are both sorted and ordered.

std::unordered_map and std::unordered_set are unordered and unsorted (they are hash maps basically)

The insert, delete, push, pop, etc functions all take these container requirements into account. For sorted containers, insert must ensure that the element is inserted in the right position and the remaining elements are adjusted as needed.

A sequence must be ordered, but not necessarily sorted.

So when you say that you want to insert element e at index i, that concept is only meaningful for ordered containers, because unordered containers have no notion of indices or positions.

The one thing you have to be careful about (among others) is if you have an iterator to a container, often times modifying the container (insert, delete, etc) may invalidate that iterator, which brings about things like the erase-remove idiom

Here is a (sort of incomplete) diagram that shows the properties of the various C++ Standard Library containers.

_{created by David Moore and licensed CC BY-SA 3.0}

Answer 2

Inserting elements in sequences needs as argument the position where you want to put it (same for erase),

In order that the "ith position" makes sense, there should be an order

Must not confuse ordered with sorted ... to sort we need a comparator, ordered may also mean indexed (I think)

the sequence : 4 5 2 is ordered, 4 comes first then 5 then 2 and the sequence 5 2 4 is also ordered