Есть ли какая-то техническая причина, почему std::lower_bound не специализирован для итераторов красно-черного дерева?

Нет технической причины, по которой это нельзя было бы реализовать.

Чтобы продемонстрировать, я набросаю способ реализовать это.

Мы добавляем новую категорию Iterator, SkipableIterator. Это подтип BiDirectionalIterator и надтип RandomAccessIterator.

SkipableIterators гарантируют, что функция between, выполненная в контексте, где виден std::between, работает.

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

between возвращает итератор между begin и end. Он возвращает end тогда и только тогда, когда ++begin == end (end идет сразу после begin).

Концептуально between должен эффективно находить элемент «примерно посередине между» begin и end, но мы должны быть осторожны, чтобы позволить работать как рандомизированному списку пропуска, так и сбалансированному красно-черному дереву.

Итераторы произвольного доступа имеют очень простую реализацию between -- return (begin + ((end-begin)+1)/2;

Добавить новый тег также легко. Деривация позволяет существующему коду работать хорошо, пока он правильно использует диспетчеризацию тегов (и не делает явную специализацию), но здесь есть небольшая проблема с поломкой. У нас могли бы быть "теговые версии", где iterator_category_2 является усовершенствованием iterator_category (или что-то менее хакерское), или мы могли бы использовать совершенно другой механизм, чтобы говорить о пропускаемых итераторах (независимая черта итератора?).

Как только у нас появится эта возможность, мы сможем написать алгоритм быстрого упорядоченного поиска, который работает на map/set и multi. Это также будет работать с контейнером списка пропуска, например QList. Это может быть даже та же реализация, что и в версии с произвольным доступом!

Причин несколько:

1. При использовании версии, не являющейся членом, можно использовать другой предикат. На самом деле, при использовании, например, std::map<K, V>, должен использоваться другой предикат должен, так как предикат карты работает с K, а диапазон работает с парами K и V.
2. Даже если предикат совместим, функция имеет интерфейс, использующий пару узлов где-то в дереве, а не корневой узел, который был бы необходим для эффективного поиска. Хотя вполне вероятно, что есть родительские указатели, требование об этом для дерева кажется неуместным.
3. Итераторы, предоставляемые алгоритму, не обязательно должны быть t.begin() и t.end() дерева. Они могут находиться где-то в дереве, что делает использование древовидной структуры потенциально неэффективным.
4. В стандартной библиотеке нет абстракции дерева или алгоритмов, работающих с деревьями. Хотя ассоциативно упорядоченные контейнеры [вероятно] реализованы с использованием деревьев, соответствующие алгоритмы не доступны для общего использования.

Часть, которую я считаю сомнительной, — это использование общего имени для алгоритма, который имеет линейную сложность с двунаправленными итераторами и логарифмическую сложность с итераторами произвольного доступа (я понимаю, что количество сравнений имеет логарифмическую сложность в обоих случаях и что движения считаются быть быстрым).

Отличный вопрос. Я искренне считаю, что для этого нет хороших/убедительных/объективных причин.

Почти все причины, которые я вижу здесь (например, требование предиката), не имеют для меня значения. Их может быть неудобно решать, но они вполне решаемы (например, просто требуется определение типа для различения предикатов).

Самая убедительная причина, которую я вижу в самом верхнем ответе:

Хотя вполне вероятно, что есть родительские указатели, требование об этом для дерева кажется неуместным.

Однако я считаю вполне разумным предположить, что родительские указатели реализованы.

Почему? Поскольку временная сложность set::insert(iterator, value) гарантированно равна амортизированному постоянному времени, если итератор указывает на правильное местоположение.

Считают, что:

1. Дерево должно оставаться самобалансирующимся.
2. Чтобы дерево было сбалансированным, необходимо смотреть на родительский узел при каждом изменении.

Как вы можете избежать хранения родительских указателей здесь?

Без родительских указателей, чтобы гарантировать сбалансированность дерева после вставки, дерево должно каждый раз проходиться, начиная с корня, что, конечно же, не амортизируется за постоянное время.

Очевидно, что я не могу математически доказать, что не существует структуры данных, которая могла бы обеспечить эту гарантию, поэтому вполне вероятно, что я ошибаюсь, и это возможно.
Однако в отсутствие такой структур данных, я хочу сказать, что это разумное предположение, учитывая тот факт, что все реализации set и map, которые я видел, на самом деле являются красно-черными деревьями.

Дополнительное замечание, но учтите, что мы просто не могли частично специализировать функции (например, lower_bound) в C++03.
Но это не проблема, потому что мы могли бы просто специализировать type вместо этого и переадресовал вызов функции-члену этого типа.

(Разработка комментария)

Я думаю, что можно указать предикат, который не эквивалентен предикату, предоставленному std::set, и при этом выполнить требование частичной сортировки (для специальных наборов). Таким образом, вы можете заменить алгоритм lower_bound специальной красно-черной версией только в том случае, если предикат эквивалентен порядку std::set.

Пример:

#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;
}

Выход:

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

1
1

[3,1]

[1,3]

Вот очень простая нетехническая причина: это не требуется по стандарту, и любые будущие изменения без всякой причины нарушат обратную совместимость с существующим скомпилированным кодом.

Вернем время назад к началу 2000-х, во время перехода между GCC и GCC 3, а затем, во время незначительных изменений GCC 3. Многие из проектов, над которыми я работал, должны были быть бинарно-совместимыми; мы не могли потребовать от пользователя перекомпилировать наши программы или плагины, а также мы не могли быть уверены в версии GCC, на которой они были скомпилированы, или версии STL, с которой они были скомпилированы.

Решение: не используйте STL. У нас были собственные строки, векторы и попытки, а не использование STL. Решение ада зависимостей, созданное якобы стандартной частью языка, было настолько отличным, что мы отказались от него. И не только в одном или двух проектах.

К счастью, эта проблема в значительной степени ушла, и такие библиотеки, как boost, включили только версии контейнеров STL. В GCC 4 я не вижу проблем с использованием стандартных контейнеров STL, и действительно, бинарная совместимость намного проще, в основном благодаря усилиям по стандартизации.

Но ваше изменение повлечет за собой новую, невысказанную зависимость

Предположим, что завтра появится новая структура данных, которая существенно превосходит красно-черные деревья, но не гарантирует наличие некоторых специализированных итераторов. Одной из таких реализаций, которая была очень популярна всего несколько лет назад, была список пропусков, который предлагал те же гарантии при, возможно, значительно меньшем объеме памяти. Список пропусков, похоже, не сработал, но другая структура данных вполне могла это сделать. Лично я предпочитаю использовать попытки, которые предлагают значительно лучшую производительность кэша и более надежную алгоритмическую производительность; их итераторы будут существенно отличаться от красно-черных деревьев, если кто-то в libstdc++ решит, что эти структуры обеспечивают лучшую общую производительность для большинства применений.

Строго следуя стандарту, обратная бинарная совместимость может поддерживаться даже при изменении структуры данных. Это хорошая вещь (TM) для библиотеки, предназначенной для динамического использования. Я бы и глазом не моргнул, если бы такая оптимизация была хорошо реализована и хорошо использовалась, если бы она использовалась статически, например, библиотека Boost Container.

Но для такой динамической библиотеки, как libstdc++, гораздо важнее обратная бинарная совместимость.