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

Ответ 1

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

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

Добавим новую категорию Итератора, SkipableIterator. Это подтип BiDirectionalIterator и супертип RandomAccessIterator.

SkipableIterator гарантируют, что функция 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. Это может быть даже такая же реализация, как и версия произвольного доступа!

Ответ 2

Существует несколько причин:

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

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

Ответ 3

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

Я думаю, что можно предоставить предикат, который не эквивалентен тому, который был отправлен на 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]

Ответ 4

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

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

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

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

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

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

Рассмотрим, что:

• Дерево должно оставаться самобалансирующимся.
• Сохранение сбалансированного дерева требует просмотра родительского node при каждой модификации.

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

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

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

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

Ответ 5

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

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

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

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

Но ваше изменение введет новую, невысказанную, зависимость

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

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

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