c++ - ¿Hay alguna razón técnica por la que std:: lower_bound no esté especializado para iteradores de árbol rojo-negro?

algorithm c++11

Question

Siempre he asumido que std::lower_bound() ejecuta en tiempo logarítmico si le paso un par de iteradores de árbol rojo-negro ( set::iterator o map::iterator ). Tuve que quemarme dos veces para notar que std::lower_bound() ejecuta en tiempo O (n) en este caso, al menos con la implementación libstdc ++. Entiendo que la norma no tiene el concepto de iteradores de árbol rojo-negro; std::lower_bound() los tratará como iteradores bidireccionales y los advance en tiempo lineal. Todavía no veo ninguna razón por la que la implementación no pueda crear una etiqueta de iterador específica de la implementación para los iteradores de árbol rojo-negro y llamar a un lower_bound() si los iteradores pasados ​​son iteradores de árbol rojo-negro.

¿Hay alguna razón técnica por la cual std::lower_bound() no está especializado para iteradores de árbol rojo-negro?

ACTUALIZACIÓN: Sí, soy consciente de las funciones de miembro de búsqueda pero no es el punto. (En un código con plantilla, es posible que no tenga acceso al contenedor o que trabaje solo en una parte del contenedor).

Después de que la recompensa haya expirado: las respuestas de Mehrdad y Yakk me parecen las más convincentes. No pude decidir entre los demasiado; Le doy la recompensa a Mehrdad y acepto la respuesta de Yakk.

Answer 1

(Elaborando un comentario)

Creo que es posible proporcionar un predicado que no es equivalente al suministrado a std::set y aún cumplir con el requisito de clasificación parcial (para conjuntos especiales). Por lo tanto, solo puede reemplazar el algoritmo lower_bound por una versión especial de rojo y negro si el predicado es equivalente al orden de std::set .

Ejemplo:

#include <utility>
#include <algorithm>
#include <set>
#include <iostream>

struct ipair : std::pair<int,int>
{
    using pair::pair;
};

bool operator<(ipair const& l, ipair const& r)
{  return l.first < r.first;  }

struct comp2nd
{
    bool operator()(ipair const& l, ipair const& r) const
    {  return l.second > r.second; /* note the > */ }
};

std::ostream& operator<<(std::ostream& o, ipair const& e)
{  return o << "[" << e.first << "," << e.second << "]";  }

int main()
{
    std::set<ipair, comp2nd> my_set = {{0,4}, {1,3}, {2,2}, {3,1}, {4,0}};
    for(auto const& e : my_set) std::cout << e << ", ";

    std::cout << "/n/n";

    // my_set is sorted wrt ::operator<(ipair const&, ipair const&)
    //        and       wrt comp2nd
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend()) << "/n";
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend(),
                                comp2nd()) << "/n";

    std::cout << "/n/n";

    // implicitly using operator<
    auto res = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{3, -1});
    std::cout << *res;

    std::cout << "/n/n";

    auto res2 = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{-1, 3},
                                 comp2nd());
    std::cout << *res2;
}

Salida:

[0,4], [1,3], [2,2], [3,1], [4,0], 1 1 [3,1] [1,3]

Answer 2

Aquí hay una razón no técnica muy simple: el estándar no lo exige, y cualquier cambio futuro romperá la compatibilidad con el código compilado existente sin ninguna razón.

Regrese el reloj a principios de la década de 2000, durante la transición entre GCC y GCC 3, y más tarde, durante revisiones menores de GCC 3. Muchos de los proyectos en los que trabajé estaban destinados a ser binarios compatibles; no podríamos exigir al usuario que vuelva a compilar nuestros programas o complementos, y tampoco podríamos estar seguros de la versión de GCC en la que se compilaron o la versión de la STL con la que se compilaron.

La solución: no usar el STL. Teníamos cadenas internas, vectores e intentos en lugar de usar el STL. La solución al infierno de la dependencia introducida por una parte aparentemente estándar del lenguaje fue tan grande que la abandonamos . Tampoco en uno o dos proyectos.

Este problema ha desaparecido en gran medida, por suerte, y las bibliotecas como boost han intervenido para proporcionar incluir solo las versiones de los contenedores STL. En GCC 4, no vería ningún problema con el uso de contenedores STL estándar, y de hecho, la compatibilidad binaria es mucho más fácil, en gran parte debido a los esfuerzos de estandarización.

Pero su cambio introduciría una nueva dependencia tácita.

Supongamos que mañana saldrá una nueva estructura de datos que supera sustancialmente a los árboles rojos y negros, pero no ofrece la garantía de que haya disponibles algunos iteradores especializados. Una de esas implementaciones que fue muy popular hace solo unos años fue la lista de saltos, que ofrecía las mismas garantías en una huella de memoria posiblemente mucho menor. La lista de omisiones no parecía tener un buen resultado, pero otra estructura de datos podía hacerlo muy bien. Mi preferencia personal es usar try, que ofrece un rendimiento de caché sustancialmente mejor y un rendimiento algorítmico más robusto; sus iteradores serían sustancialmente diferentes de los árboles rojos y negros, si alguien en libstdc ++ decidiera que estas estructuras ofrecen un mejor rendimiento general para la mayoría de los usos.

Al seguir estrictamente el estándar, se puede mantener la compatibilidad binaria hacia atrás incluso ante cambios en la estructura de datos. Esta es una Good Thing (TM) para una biblioteca destinada a ser utilizada de forma dinámica. Para una que se usaría de forma estática, como la biblioteca de Contenedores Boost, no me importaría si esas optimizaciones estuvieran bien implementadas y bien utilizadas.

Pero para una biblioteca dinámica como libstdc ++, la compatibilidad con binarios hacia atrás es mucho más importante.

Answer 3

Gran pregunta Sinceramente, creo que no hay una razón objetiva, convincente o buena para esto.

Casi todas las razones que veo aquí (por ejemplo, el requisito del predicado) no son un problema para mí. Pueden ser inconvenientes de resolver, pero son perfectamente solucionables (por ejemplo, solo se requiere un typedef para distinguir los predicados).

La razón más convincente que veo en la respuesta superior es:

Aunque es probable que haya indicadores principales, el requisito para el árbol parece inapropiado.

Sin embargo, creo que es perfectamente razonable suponer que los punteros de los padres están implementados.

¿Por qué? Debido a que la complejidad de tiempo de set::insert(iterator, value) se garantiza que se amortiza a tiempo constante si el iterador apunta a la ubicación correcta.

Considere eso:

1. El árbol debe mantenerse equilibrado.
2. Mantener un árbol equilibrado requiere mirar el nodo principal en cada modificación .

¿Cómo puedes evitar guardar aquí los punteros de los padres?

Sin los punteros principales, para garantizar que el árbol esté equilibrado después de la inserción, el árbol debe atravesarse comenzando desde la raíz cada vez, lo que ciertamente no se amortiza a tiempo constante.

Obviamente, no puedo demostrar matemáticamente que no exista una estructura de datos que pueda proporcionar esta garantía, por lo que existe la posibilidad de que me equivoque y esto es posible.
Sin embargo, en ausencia de tales estructuras de datos, lo que estoy diciendo es que esta es una suposición razonable , dada por el hecho de que todas las implementaciones de set y map que he visto son de hecho árboles rojo-negros.

Nota al lower_bound , pero tenga en cuenta que simplemente no pudimos especializar parcialmente las funciones (como lower_bound ) en C ++ 03.
Pero eso no es realmente un problema porque podríamos haber especializado un tipo y reenviar la llamada a una función miembro de ese tipo.

Answer 4

Hay múltiples razones:

1. Cuando se usa la versión no miembro, se puede usar un predicado diferente. De hecho, se debe usar un predicado diferente cuando se usa, por ejemplo, un std::map<K, V> ya que el predicado del mapa opera en K s mientras que el rango opera en pares de K y V
2. Incluso si el predicado es compatible, la función tiene una interfaz que utiliza un par de nodos en algún lugar del árbol en lugar del nodo raíz que se necesitaría para una búsqueda eficiente. Aunque es probable que haya indicadores principales, el requisito para el árbol parece inapropiado.
3. No se requiere que los iteradores proporcionados al algoritmo sean t.begin() y t.end() del árbol. Pueden estar en algún lugar del árbol, haciendo que el uso de la estructura del árbol sea potencialmente ineficiente.
4. La biblioteca estándar no tiene una abstracción de árbol o algoritmos que operen en árboles. Aunque los contenedores ordenados asociativos se implementan [probablemente] utilizando árboles, los algoritmos correspondientes no están expuestos para uso general.

La parte que considero cuestionable es el uso de un nombre genérico para un algoritmo que tiene complejidad lineal con iteradores bidireccionales y complejidad logarítmica con iteradores de acceso aleatorio (entiendo que el número de comparaciones tiene complejidad logarítmica en ambos casos y que los movimientos se consideran ser rapido).

Answer 5

No hay ninguna razón técnica por la que esto no pueda ser implementado.

Para demostrarlo, esbozaré una manera de implementar esto.

SkipableIterator una nueva categoría de iterador, SkipableIterator . Es un subtipo de BiDirectionalIterator y un supertipo de RandomAccessIterator .

SkipableIterator s garantiza que la función between realizada en un contexto en el que std::between sea ​​visible.

template<typeanme SkipableIterator>
SkipableIterator between( SkipableIterator begin, SkipableIterator end )

between devuelve un iterador entre begin y end . Devuelve end si y solo si ++begin == end ( end es justo después de begin ).

Conceptualmente, between debe encontrar de manera eficiente un elemento "a mitad de camino entre" begin y end , pero debemos tener cuidado de permitir que una lista de omisión aleatoria o un árbol negro rojo equilibrado funcionen.

Los iteradores de acceso aleatorio tienen una implementación realmente simple de between - return (begin + ((end-begin)+1)/2;

Agregar una nueva etiqueta también es fácil. La derivación hace que el código existente funcione bien siempre y cuando utilicen correctamente el envío de etiquetas (y no se especialicen explícitamente), pero aquí existe una pequeña preocupación de rotura. Podríamos tener "versiones de etiqueta" donde iterator_category_2 es un refinamiento de iterator_category (o algo menos hacky), o podríamos usar un mecanismo completamente diferente para hablar de iteradores omitibles (¿un rasgo de iterador independiente?).

Una vez que tengamos esta capacidad, podemos escribir algoritmos de búsqueda rápida ordenada que funcionen en map / set y multi . También funcionaría en un contenedor de lista de omisión como QList . ¡Podría ser incluso la misma implementación que la versión de acceso aleatorio!