# Insert an element in a position in a C ++ 11 list

1

I need to insert an element within a list declared as follows:

``````list < list <unsigned int> > bucket (16);
``````

I must insert an element into one of the bucket lists as efficiently as possible. I have the position in which I should insert this value, but I can not think of the best way to insert it (preferably, insert should be avoided).

My current code uses, instead of `list< list <unsigned int> > bucket (16);` , `vector< list <unsigned int> > bucket (16);` , this being the following:

``````void LSDRadixSortList (list<unsigned int> &v, int m)
{
int logaritmo = (log10(m))/(log10(16));
vector< list <unsigned int> > bucket (16);

for (int i = 0; i <= logaritmo; ++i)
{

for (auto buck : bucket){
buck.clear();
}

for_each(v.begin(),
next(v.begin(),v.size()),
[i,&bucket](unsigned int x){

int digit = x;

int mult = 0xF;
mult <<= 4 * i;

digit = digit & mult;

digit >>= 4 * i;

bucket.at(digit).push_back(x); ///< Esta es la linea a mejorar
});
v.clear();

for (auto buck : bucket){
v.splice(v.end(), move(buck));
}
}
}
``````

I need something that equates to `bucket.at(digit).push_back(x);` for lists and without being so expensive (so I know, lists tend to work better than vectors).

asked by Slifer Dragon 23.10.2017 в 15:51
source

2

preferably, insert should be avoided

I do not see the reason to avoid the use of `insert` ... saaaavo you are working with `vector` Why?

`std::vector` is a type of container in which the elements occupy contiguous memory locations. Thus, if we assume that each element occupies only one byte and that the list has 3 elements (A, B, C) these would be found as follows:

``````Posición de memoria aleatoria
vvvv
0xA0 0xA1 0xA2
A    B    C
``````

If you now wish to insert an element in the second position you would have to move elements 2 and 3 in order to make room for the new element:

``````0xA0 0xA1 0xA2 0xA3
A    D    B    C
``````

The cost of this operation is dependent on the number of elements to move.

Now, if instead of a container type `std::vector` , you use `std::list` the thing changes. Why? Basically because `std::list` implements a doubly linked list. In a linked list the cost of inserting an element (once the location is located) is constant, since you only need to readjust pointers ... in fact the documentation already makes it clear:

std :: list is a container that supports constant time insertion and removal of elements from anywhere in the container.

Now, the problem with a linked list is that each element is in a random position in the memory ... to get to a position before you have to go through all the previous nodes (or later if you are going backwards). .. in this case the cost of the operation will depend on how quickly you get to the insertion point. So, summarizing:

• `std::vector` allows you to quickly iterate through its elements but penalizes inserts
• `std::list` allows fast insertions but penalizes searches

So you see that `insert` is not a daemon ... if an operation takes too long it may be because you are using the wrong containers (or you are using them incorrectly).