std: container c++ move to front

问题:

I'm looking for a std container like a std::list that can efficiently move an element to the front:

a-b-c-d-e

move "b" to front:

a-c-d-e-b

There is no such function in the std containers. Therefor, I think I must combine a remove and push_front function but has anyone can find a better idea?

Thank in advance.

回答1:

If you don't have to maintain the order of the other elements, then the simplest solution is doubtlessly just to swap the element you want with the first element in the container. This will be efficient with all containers.

Otherwise, std::list offers a splice operation which could be used. Something like the following, I think:

void
moveToFront( 
    std::list<MyType>& list,
    std::list<MyType>::iterator element )
{
    if ( element != list.begin() ) {
        list.splice( list.begin(), list, element, std::next( element ) );
    }
}

This should end up with only a couple of pointer operations, and no copies. On the other hand, std::list can be very slow in general (because of its poor locality); I'd measure very carefully against the naïve implementation using std::vector, to make sure it was a win globally. Eliminating all copies here may not be a win if iterating to find the element you want to move to the front is ten time more expensive. (A lot of this depends on how expensive MyType is to copy, and how large it is. If sizeof(MyType) is close to the size of a page, or accessing MyType ends up accessing a lot of indirectly allocated objects, the locality argument won't hold.)

With an std::vector, rather than the obvious erase/insert

void
moveToFront( 
    std::vector<MyType>& list,
    std::vector<MyType>::iterator element )
{
    MyType tmp( *element );
    std::copy_backwards( list.begin(), std::prev( element ), element );
    *list.begin() = tmp;
}

This will result in less copies than the erase (which copies all of the following elements) insert (which also copies all of the following elements—which means all of the elements, because we are inserting at the beginning) pattern.

回答2:

On std::vector, you could use std::rotate, which has linear complexity

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

std::vector<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   // swap ranges [1, 2) and [2, 5)
   auto it = std::next(v.begin(), 1); // O(1)
   auto rb = std::next(it);
   auto re = v.end();
   std::rotate(it, rb, re); // O(N)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));   
   std::cout << "\n";
}

On a std::list you could use the member function splice, which (given iterators) has constant complexity

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

std::list<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   auto it = std::next(v.begin(), 1); // O(N)
   auto rb = std::next(it);
   auto re = v.end();   
   v.splice(it, v, rb, re); // O(1)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
   std::cout << "\n";   
}

NOTE: the last element is conventially denoted as back in the STL containers, and the first element as front. For std::vector, getting iterators to a certain element is constant time, and swapping is linear time. For std::list, getting iterators is linear time, but splicing into the same list is constant time. However, the much better memory caching behavior of vector is also important as this benchmark by Stroustrup shows.

UPDATE: Several commenters mentioned simply swapping elements: this only applies if you want to transform a-b-c-d-e into a-e-c-d-b. In that case, use std::iter_swap on any container you like. For the transformation of a-b-c-d-e into a-c-d-e-b, use std::rotate or list::splice.