libreria - list iterator c++

Ordenar una lista estándar:: usando iteradores

Question

¿Es posible ordenar parte de una lista (subconjunto de una lista) definida por iteradores como lo hace std::sort ?

es decir, con std::list la única clasificación disponible es a través de un método ( http://en.cppreference.com/w/cpp/container/list/sort ), me gustaría poder clasificar parte de una lista de sus iteradores usando std::sort . p.ej

std::sort(listItrStart, listItrEnd, [](T& a, T& b){ return a.something() < b.something()});

Aprecio que los iteradores queden invalidados una vez que se realice una operación de movimiento en un elemento, lo cual supongo que significa que los iteradores no pueden ordenar una lista sin volver a iterar en la ubicación deseada antes de la próxima "comparación".

¿En qué caso, cuál es la mejor práctica para clasificar los subconjuntos de listas sin llenar otro contenedor para este proceso (si existe)?

Muchas gracias.

Answer 1

¿Es posible ordenar parte de una lista (subconjunto de una lista) definida por iteradores como lo hace std :: sort?

Supongo que quiso decir std :: list :: sort. La implementación de Visual Studio 2015 hace esto, y sin tener que llenar otro contenedor. Es una ordenación de combinación descendente que es menos eficiente que la ordenación de fusión ascendente anterior, pero evita la asignación de memoria que hizo la versión anterior, ya que la versión anterior asignó una pequeña cantidad de listas. El código de Psuedo se vería así:

    right = std::next(right, 1);   // right = end of sub-list
    size = std::distance(left, right);
    left = MyListSort(list, left, right, size);
    right = std::next(left, size-1);  // right = last element of sub-list
    // ...
    MyListSort(list, left, right, size)
    {
        if(size < 2)
            return left;
        mid = std::next(left, size/2);
        MyListSort(list, left, mid, size/2);
        MyListSort(list, mid, right, size-size/2);
        firstloop = true;
        newleft = left;
        while(true){
            if(*left <= *mid){
                if(++left == mid)
                    return newleft;
            } else {
                if(firstloop)
                    newleft = mid;
                list.splice(left, list, mid);
                if(++mid == right)
                    return newleft;
            }
            firstloop = false;
        }
    }

Answer 2

El llenado de otro contenedor es inevitable. Pero no tiene que mover ni copiar ninguno de sus propios datos. Puede usar std::list::splice para extraer y volver a insertar los nodos que desea procesar en orden ordenado.

using list_t = std::list<widget>;
void process(list_t& in, list_t::const_iterator begin, list_t::const_iterator end) {
  list_t sorter;
  sorter.splice(sorter.end(), in, begin, end);
  sorter.sort();
  in.splice(end, sorter);
}

La función transfiere los nodos que desea ordenar a la lista de clasificación (el primer argumento del iterador es la posición antes de que se inserten los nodos, en este caso, el final de la lista).

La lista de clasificación se ordena (obviamente), y luego el contenido clasificado se transfiere nuevamente a la lista de origen, exactamente en el sub-rango original que originalmente se completó.

Como comentó @TC El siguiente paso es generalizarlo. Se puede convertir en una plantilla muy parecida a esta:

template<class List, class Compare = std::less<>>
void sort_subrange(List& in,
                   typename List::const_iterator begin,
                   typename List::const_iterator end,
                   Compare c = {}) {
  List sorter(in.get_allocator());
  sorter.splice(sorter.end(), in, begin, end);

  [[maybe_unused]] ScopeGuard sg([&]() { in.splice(end, sorter); }); 
  sorter.sort(std::move(c));
}

El comparador también se toma como un argumento aquí, y el sorter se construye con una copia del asignador de la entrada para la máxima genéricoidad. La parte posterior del empalme se realiza en una protección de alcance de nuestra elección para respaldar el caso en el que se realiza la función de comparación, por lo que nuestras bases ahora están cubiertas.

Aquí hay un ejemplo en vivo , con una implementación ingenua y algo tonta de una protección de alcance, para propósitos de exposición.