How does std::list?

How is the container std::list in C++?

Specifically, I can't understand these lines:
1) "a List is a container which supports fast insertion and deletion of elements from any position in the container.
Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions."

2) "Fast random access is not supported.
The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position


Any position and random access is not the same?

On the basis of the first statement, if you write:
myList.emplace(it, 5, "Value"); // this should be very fast


And judging by the second, this entry should work for O(n)
July 4th 19 at 22:56
2 answers
July 4th 19 at 22:58
Solution
Random access is access by index, with a constant complexity (O(1)) when computing the offset and we can jump directly to the desired element, as in std::vector using [] or method at(index).

In std::listto get (insert, delete, etc.) somewhere in the middle, we need this place to get to, along the way beating lower(higher) elements lying one after the other. It is quite slow (O(n)). But the insertion itself will be cheap anywhere (O(1)).
I'm about the same, but in cplusplus.com/reference/ it is recommended to use the leaves to insert data in the middle, and says that access to all components is constant (one) time: "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions." - Chadd_Hane commented on July 4th 19 at 23:01
: insert easy because there is no need to shift the "tail" on each insert. About constant complexity dostupa inside std::list there is nothing written. Insert at the iterator - constant complexity, but the iterator you need to find =)

*sorry for edit* - Elna.Volkman92 commented on July 4th 19 at 23:04
And, that is, the process of insertion, for example, 500-th position will still take o(500) ? Because it = begi90n+500 - Will be held on all these elements? And when we have a pointer to it then the insert will happen quickly? - Chadd_Hane commented on July 4th 19 at 23:07
If you have an iterator at the desired position, you spend only the time required for a copy sheet and overridden references to it from previous and subsequent elements. Regardless of the insertions, i.e. the complexity of insertion constant. And if you want to insert the new item _na sixth positiu, the iterator is there, still need to get going with beginning to present the 6th element. - Elna.Volkman92 commented on July 4th 19 at 23:10
: Well, by itself, insert a constant that I already knew. Thank you) But: "the iterator there is still needed to" to make this the 'constant' box is necessary to obtain an iterator that is still linear time, right? - Chadd_Hane commented on July 4th 19 at 23:13
In the General case, Yes. But remember that iterators to std::list is not "I" when inserting, as it happens in std::vector, it is convenient in some situations. If no kaih special requirements, it is better to use a std::vector this often enough. Then you need to look at the lists (delvie insert in the middle, Dolci random access), deki (compromise between access and insertion), the hash table (fast access, fast insertion, huge memory consumption)... - Elna.Volkman92 commented on July 4th 19 at 23:16
Yeah, I got it. That is despite the fact that to insert in the middle we need to let 20 000 items to find the right iterator, but we still get the win, because during insert change only pointers and not have to move all the remaining elements in the vector, right? - Chadd_Hane commented on July 4th 19 at 23:19
Yes. But again focuses: std::list is not a silver bullet and in most cases for a small collection of tiny objects he will lose the std::vector as performance and memory consumption. - Elna.Volkman92 commented on July 4th 19 at 23:22
: I know, thanks for the clarification - Chadd_Hane commented on July 4th 19 at 23:25
July 4th 19 at 23:00
Solution
The worksheet is not sorted in-memory array, the relationship between the elements is carried out by storing a pointer to the next and/or previous element. When you delete or add an item, just change these pointers so that explains the "supports fast insertion and deletion of elements from any position in a container".

"myList.emplace(it, 5, "Value"); " will work as follows ( shareware )
auto item = new ItemType( 5, "Value" );
item->next = it->next;
it->next = item;

Fast random access - means access the element N in constant time. The sheet provides access only in linear time, since to access the N element, you must loop through all previous elements.
Well, it seems you begin to understand. So true that the leaves in C++ you need to use when you need to often do an insert in the middle? Because they provide more speed?
I can't understand what to paste on the same 5-th position after all you still need to go to the 5th email. then to associate the pointer? - Chadd_Hane commented on July 4th 19 at 23:03
That is, the process of insertion, for example, 500-th position will still take o(500) ? Because it = begin()+500 - Will be held on all these elements to get the desired iterator? And when we've already got a pointer to it then the insert will happen quickly? - Elna.Volkman92 commented on July 4th 19 at 23:06
in the list you can have a long walk to the fifth element, and then there a thousand times to quickly insert an element.
In vector (vector) on the contrary - you can easily walk to the fifth element, but if you insert there a new item you need to move all the right elements right to make room for the inserted. One thousand of these panels will be very long. - Chadd_Hane commented on July 4th 19 at 23:09
: insert 20000 items in list: 0.1 s, in vector: 0.2 s, but the analogy thank you - Elna.Volkman92 commented on July 4th 19 at 23:12
:
This run, we can well see the difference.
#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main()
{
 list<int> l;
 vector<int> v;

 for (int i = 0; i < 100000; i++) {
 l.push_back(i + 1);
 v.push_back(i + 1);
}

 cout << "list insert start" << endl;
 for (int i = 0; i < 100000; i++) {
 l.insert(l.begin(), 5);
}
 cout << "list insert end" << endl;

 cout << "vector insert start" << endl;
 for (int i = 0; i < 100000; i++) {
 v.insert(v.begin(), 5);
}
 cout << "vector insert end" << endl;

 return 0;
}</int></int></list></vector></iostream>
- Chadd_Hane commented on July 4th 19 at 23:15
: See the difference in time. There is a box 5*100000 = 500 000 email. right? - Elna.Volkman92 commented on July 4th 19 at 23:18
: 100000 inserted the number 5 in the beginning. The difference is there are any number of elements. Just to see her naturally in the shell is 100,000 inserts. - Chadd_Hane commented on July 4th 19 at 23:21

Find more questions by tags C++