STL containers: list. Part 4

In the third part of the lessons of the STL containers,  we finished the consideration vectors, let us say, type vector<float> as the equivalent of an array of real numbers. For these "arrays" very quickly carried out the operation to access the element (read-write) the index and inserting, deleting an element to the end vector. Much worse (performance) performed the operation-the removal of the insert element somewhere in the middle of the vector, or moving element from one position to another.

For example, vector size 15 operation of moving element 10 in position 2 will require:

• Remember in the intermediate variable element 10 minutes;

• for all elements 9th to 2nd (in reverse order, possibly using the reversed iterator) copy the next position (8 copy operations);

• saved earlier in the intermediate variable element is copied to the position 2;

Total, for this simple operation it took us 10 copy operations. Each element of the vector, as we discussed earlier, It may be difficult to fail-composite structure. And its up - it is a time consuming operation.

For “collections”, wherein the active addition of planned, delete and move elements, STL library offers another kind of container - doubly linked list, list. For such access to the container elements (reading, record) consistent, not as effective. But the addition operation, delete or change the order of items is very fast.

iterator list It is not a direct access iterator. Therefore it notapply operation +,  –,  +=,  -=, and container notadmissible operation indexation. Iterators for the container move sequentially operations++  and  — .

To illustrate the work with such a container, we write all the same problem of finding all prime numbers, not exceeding N (for consistency and comparison to previous versions):

Here, the first half of the code (operator << for a list) Only decorative implementation for diagnostics and convenience, and the remainder of the following is done:

• Formed list list<int>  natural numbers range [2…N] – strings 19 – 22;

• For each (remaining) the number of all subsequent list deleted multiple elements to it – string 31;

• And so on until, yet another number to be tested does not exceed the square root of N – string 26 (in number theory shows, divisibility that can be checked not to N-1, to a number, greater than the square root of N);

Of the features of the code, and container list at all, you need to pay attention to what, that after the removal of the element, Indicates the current value of the iterator, iterator value becomes uncertain. If we want to continue to iterate, we have to work with a copy of iterator (i code shown in).

The code is executed, we can check, that the results it exactly similar to previous versions. Before starting the program, do not forget to define the commands equal to argument 300, as we did in the previous lesson.