¿Hay alguna razón técnica por la que std:: lower bound no está especializada para iteradores de árbol rojo-negro?

Hay múltiples razones:

1. Cuando se usa la versión no miembro se puede usar un predicado diferente. De hecho, un predicado diferente tiene para ser utilizado cuando se usa, por ejemplo, un std::map<K, V> como el predicado de 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 usa un par de nodos en algún lugar del árbol en lugar del nodo raíz que sería necesario para una búsqueda eficiente. A pesar de que es probable que haya punteros de los padres, requerir así para el árbol parece inapropiado.
3. Los iteradores proporcionados al algoritmo no deben ser el t.begin() y el 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 ni algoritmos que operen en árboles. Aunque los contenedores ordenados asociativos están [probablemente] implementados usando á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 rápidos).

Gran pregunta. Honestamente creo que no hay ninguna razón buena/convincente/objetiva para esto.

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

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

Aunque es probable que haya punteros padres, lo que requiere para el el árbol parece inapropiado.

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

¿Por qué? Porque la complejidad temporal de set::insert(iterator, value) está garantizada para ser tiempo constante amortizado si el iterador apunta a la ubicación correcta.

Considera que:

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

¿Cómo puede evitar almacenar punteros de padres aquí?

Sin punteros padre, para asegurar que el árbol esté equilibrado después de la inserción, el árbol debe ser atravesado comenzando desde la raíz cada vez, lo que ciertamente es no tiempo constante amortizado.

Obviamente no puedo demostrar matemáticamente que no existe una estructura de datos que pueda proporcionar esta garantía, por lo que claramente 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-negro.

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

(Elaborando un comentario)

Creo que es posible suministrar un predicado que no es equivalente al suministrado a std::set y aún así cumplir con el requisito de parcialmente ordenado (para conjuntos especiales). Así que solo puede reemplazar el algoritmo lower_bound por una versión especial rojo-negro si el predicado es equivalente al orden 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]

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

Devuelve 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 compatibles con binarios; no podíamos requerir que el usuario recompilara nuestros programas o complementos, y tampoco podíamos estar seguros de the version of GCC they were compiled on or the version of the STL they were compiled against.

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

Este problema ha desaparecido en gran medida, afortunadamente, y bibliotecas como boost han intervino para proporcionar incluir solo versiones de los contenedores STL. En GCC 4, no veo 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, tácita, dependencia

Supongamos que mañana, sale una nueva estructura de datos, que supera sustancialmente a red black trees, pero no proporciona la garantía de que algunos iteradores especializados sean disponible. Una de esas implementaciones que fue muy popular hace solo unos años fue la lista de exclusión, que ofrecía las mismas garantías con una huella de memoria posiblemente sustancialmente menor. La lista de exclusión no parecía dar resultado, pero otra estructura de datos muy bien podría. Mi preferencia personal es usar tries, que ofrecen un rendimiento de caché sustancialmente mejor y un rendimiento algorítmico más robusto; sus iteradores serían sustancialmente diferentes de un árbol rojo negro, si alguien en el libstdc++ decide que estas estructuras ofrecen un mejor rendimiento para la mayoría de los usos.

Siguiendo estrictamente el estándar, la compatibilidad binaria hacia atrás se puede mantener incluso frente a los cambios en la estructura de datos. Esto es algo Bueno (TM) para una biblioteca destinada a ser utilizada dinámicamente. Para uno que se utilizaría estáticamente, como la biblioteca de contenedores Boost, no me molestaría si tales optimizaciones estuvieran bien implementadas y bien utilizadas.

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