CODEWITHSUNDEEP
c++listvector
tongbaiming
tongbaiming

Reputation: 3

if I insert or erase the element of a list in std::vector<std::list>, will it result in move afterward lists in vector

As insert an element in vector will relocate the afterward elements, as below said:

Because vectors use an array as their underlying storage, inserting elements in positions other than the vector end causes the container to relocate all the elements that were after position to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

I want to know, will it relocate elements of other lists in the vector, if I insert or erase the elements of one list in std::vector<std::list<int>>. I concern the efficiency of this kind of insert and erase operation. Is the complexity of this kind of insert and erase operation still be constant as normal insert and erase operation in std::list<int>?

Upvotes: 0

Views: 132

Answers (1)

eesiraed
eesiraed

Reputation: 4654

If you're referring to inserting an element in the list, it would be constant time and not affect other elements in the vector. Why would it? If you're inserting a list into the vector, then that would move the elements behind it and take linear time.

#include <vector>
#include <list>
int main()
{
    std::vector<std::list<int>> foo(3, std::list<int>({2, 3, 4}));

    foo.emplace(foo.begin(), std::list<int>({7, 8})); //shifts all lists behind insertion point

    foo[0].insert(foo[0].begin(), 42); //const time, has nothing to do with other lists
}

Note that even though the lists are shifted, the elements stored inside likely won't be shifted since the lists only stores pointers to them. This allows a list to be moved in constant time, therefore the time it takes inserting a list into a vector isn't affected by the number of elements in the lists.

Upvotes: 0

Related Questions