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.

What's the difference? If you're implying that the order is just there and needn't be maintained, why bother mentioning it at all? — Krishna Keshan, Jun 18 '15 at 13:34
Since you've quoted a whole lot of text, please add a reference to the source. It might be useful for others, and it's polite to the copyright holder. — Kif, Jun 18 '15 at 13:35
@user3143420 There is an order, so when you want to add an element after the `i`'th element, we can find the `i`th element — Othman Benchekroun, Jun 18 '15 at 13:35
@OthmanBenchekroun It says that elements can be inserted and ranges can be deleted from wherever and not just first or last — Krishna Keshan, Jun 18 '15 at 13:37
you need to read the whole sentence : "inserting values *at a particular location*" (not just "inserting") and "erasing *a particular range*" (not just "deleting elements"). Its the "particular location" and "particular range" aspects that get enabled by the ordering. — Sander De Dycker, Jun 18 '15 at 13:38
@SanderDeDycker Particular just adds a specific location and doesn't generalise anything. Not sure if you understood my question. — Krishna Keshan, Jun 18 '15 at 13:41
@user3143420 I haven't said anything about last or first ... I think you are not understanding what they mean by order — Othman Benchekroun, Jun 18 '15 at 13:42
@user3143420 ordered means a sequence that has an order, you can say this node is first, this node is `i`'th, i think you are confusing it with sorted — Othman Benchekroun, Jun 18 '15 at 13:44
How about an analogy. If people are queuing up, they are ordered sequentially (in a line). Everyone (except the first and last) has one person immediately in front and one immediately behind. A person can cut in line between two people, or a person can leave the line. Neither of these actions change the ordered property of the line. On the other hand, consider that all of those people are just bunched up randomly. In that case, there's no order, and a person cannot place himself between two other people, because there is no such thing as "between". — Sander De Dycker, Jun 18 '15 at 13:46
@OthmanBenchekroun No no. I understand what sorted is. I'm taking ordered to mean that every element has the same elements behind it and in front of it all the time. Nothing to do with sorting. — Krishna Keshan, Jun 18 '15 at 13:46
@SanderDeDycker referring to your analogy, whether it's a line or a bunch, removing people into it and adding people to it is still possible. Does order mean just a line as in something in front and something behind? Is that your point? — Krishna Keshan, Jun 18 '15 at 13:48
@user3143420 I don't know what you mean by all time, but that doesn't look like a good understanding of ordered, look at my answer — Othman Benchekroun, Jun 18 '15 at 13:48
@user3143420 : that's basically the point yes. You can add a person to both a bunch and a line. But only a line allows you to add a person at a certain position in the line (ie. between two other people). That's the difference between an ordered set of people, and an un-ordered set of people. — Sander De Dycker, Jun 18 '15 at 13:50
But hey read the text again. It says that the order is definite and doesn't change from one iteration cycle to another. What about that? — Krishna Keshan, Jun 18 '15 at 13:57
@user3143420 : the ordering property doesn't disappear just because you made the sequence longer or shorter. Sure, the positions of the elements within the sequence can change with respect to the positions of other elements (they can be closer together or further away from each other eg.), but overall, the sequence remains ordered, no matter how many you add or remove. In other words, don't focus on the relative/absolute positions of elements (which can change over time), but rather on the fact that they HAVE a position to begin with. — Sander De Dycker, Jun 18 '15 at 14:04
Yeah I realised that. I had taken it to be that the position of elements with respect to one another remains unchanged. Thanks a lot. — Krishna Keshan, Jun 18 '15 at 14:05

Cory Kramer · Answer 1 · 2015-06-18T13:55:36.197

4

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.

C++ Standard Library Container Flow Chart _{created by David Moore and licensed CC BY-SA 3.0}

edited Jun 18 '15 at 13:55

answered Jun 18 '15 at 13:33

Cory Kramer

114,268
16
167
218

I'm a little confused. I clearly read in the text that all sequences are ordered as opposed to what you said. – Krishna Keshan Jun 18 '15 at 13:39
I was very deliberate about my terminology, though I should have been more explicit about the distinction. A "sequence" is a sub-set of "container". All of the examples I gave are "containers", but only `std::list` and `std::vector` would be considered a "sequence" (as would `std::string`, `std::deque`, etc) – Cory Kramer Jun 18 '15 at 13:40
oh okay. But vectors too don't have a definite order. They do until they're modified but that's the whole thing about modifying something. If vectors were to have a definite order, it shouldn't have been possible to modify elements in any way. – Krishna Keshan Jun 18 '15 at 13:44
2

@user3143420 again confusing ordered with sorted – Othman Benchekroun Jun 18 '15 at 13:45
@OthmanBenchekroun Consider this vector: vector vec; vec.push_back(10); vec.push_back(4); vec.push_back(100); the elements are in no way sorted. But, if i inserted an element into the vector after 4, wouldn't it be disrupting the order? – Krishna Keshan Jun 18 '15 at 13:49
I particularly like this flowchart, is there a source for this image? – shuttle87 Jun 18 '15 at 13:49
@shuttle87 I borrowed this image from [this thread](https://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container) specifically from [@zdan](http://stackoverflow.com/a/471461/2296458). I will add the original citation for the image, I certainly didn't mean to deliberately plagiarize. – Cory Kramer Jun 18 '15 at 13:54
@CoryKramer, thanks. Certainly not making accusations of plagiarism, though I did want to avoid that myself as it seemed like a genuinely useful educational tool for less experienced c++ developers that I'd like to blog about perhaps. – shuttle87 Jun 18 '15 at 13:56

Othman Benchekroun · Answer 2 · 2015-06-18T13:46:36.570

0

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

edited Jun 18 '15 at 13:46

answered Jun 18 '15 at 13:39

Othman Benchekroun

1,998
2
17
36

Exactly what I'm trying to say. So is array considered a sequence in terms of the order aspect i.e. having an index feature? – Krishna Keshan Jun 18 '15 at 13:54

Inserting and deleting from sequences C++

2 Answers2