Removing from a vector took less time than deleting from a list. What for?

Question

In the C ++ manual, I found the following:

Vectors are relatively effective at adding or removing elements from the end. For operations related to inserting or deleting elements at positions other than the end, they perform worse than others and have less consistent iterators and links than lists and forward_lists.

In addition, in the "complexity" of the method to "erase" a vector, I found the following:

Linearly by the number of elements to be erased (destruction) plus the number of elements after the last element has been deleted (moving).

In the 'complexity' of the 'erase' method of the next list:

The linear number of elements to be erased (destruction).

But when I tested it in 30 million elements in each container (I deleted from element 24357 to element 2746591), I got that removing from the vector took 5 ms, but from the list of 8857 ms. The difference is huge and confusing ...

Here is my code:

#include "stdafx.h"
#include <vector>
#include <list>
#include <iostream>
#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    const long int x = 30000000;
    vector<char> v;
    vector<char>::iterator itv1, itv2;
    list<char> l;
    list<char>::iterator itl1, itl2;
    unsigned start, end;

    long int first, last;

    cout << "Please enter first position: \n";
    cin >> first;
    cout << "Please enter last position: \n";
    cin >> last;

    for (long int i = 0; i < x; ++i)    {
        char c;
        c = (rand() % 26) + 'a';
        v.push_back(c);
        l.push_back(c);
    }

    cout << "Starting deletion\n";
    start = clock();
    itv1 = v.begin() + first;
    itv2 = v.begin() + last;
    v.erase(itv1, itv2);
    end = clock();
    cout << "End " << end-start << "\n";

    start = clock();
    itl1 = itl2 = l.begin();
    advance(itl1, first);
    advance(itl2, last);
    l.erase(itl1, itl2);
    end = clock();
    cout << "End " << end-start << "\n";
    return 0;
}

Could you explain what makes this difference? My opinion is that moving iterators in the list is much slower than in vectors - but I'm not sure.

Many thanks!

Answer 1

Erasing a number of elements from a vector simply requires moving all the finite elements forward, before the break begins. This can be done using the memory move command, which is very efficient. It depends on the number of finite elements, and not on the number of deleted elements.

, .

1000 , . , () .

:

Please enter first position: 
1
Please enter last position: 
1000
Starting deletion
End 10000
End 0
/tmp$ ./del
Please enter first position: 
29999000         
Please enter last position: 
29999999
Starting deletion
End 0
End 360000

: -)

Answer 2

, , - , , , advance erase.

: O() , . O (1) . , ; , .

, , , . , , , .

Answer 3

, .

erase(): .

, , .

erase(): .

Answer 4

, , ! , , , , . , O (N) - , ( ) , , , , .

Answer 5

, , O (n), . , 1 (itl1) 2 (itl2), , . , , O (n) . , , , .

, , , .