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

Question

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

Navigation

#1 by (2 votes)

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).

lista c++11 vector eficiencia

asked by Slifer Dragon 23.10.2017 в 15:51

source

1 answer

Verification of a Checkbox Cursor Android Studio Get data

score 2 · Accepted Answer

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).