Функция STLish lower_bound для Radix / Patricia Trie

В последнее время я изучаю попытки Патрисии и работаю с действительно хорошей реализацией C ++ , которую можно использовать в качестве сортированного ассоциативного контейнера STL. Патрисия пытается отличаться от обычных бинарных деревьев, потому что листовые узлы имеют обратные указатели, указывающие на внутренние узлы. Тем не менее, можно пройти дерево Патрисии в алфавитном порядке, выполнив обход по порядку, если вы только посещаете внутренние узлы с помощью обратных указателей листовых узлов.

Это подводит меня к вопросу: возможно ли реализовать функции STL lower_bound и upper_bound с помощью дерева Patricia? Реализация, которую я использую , на самом деле реализует эти функции, но они работают не так, как ожидалось.

Например:

typedef uxn::patl::trie_set trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");

trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;

Это выводит BLQ, тогда как я ожидал бы вывода HCDA. (Например, std :: set наверняка выведет здесь HCDA.)

Я написал разработчику, создавшему эту библиотеку, по электронной почте, но так и не получил ответа. Тем не менее, я чувствую, что довольно хорошо понимаю, как Патрисия пытается работать, и я не могу понять, как вообще возможно что-то вроде lower_bound. Проблема в том, что lower_bound, похоже, полагается на способность лексикографически сравнивать две строки. Поскольку "GG" не существует в дереве, мы d нужно выяснить, какой элемент> = GG. Но Radix / Patricia старается не использовать лексикографическое сравнение для перехода от узла к узлу; скорее, каждый узел хранит битовый индекс, который используется для выполнения битового сравнения ключа поиска. Результат битового сравнения подскажет, двигаться влево или вправо. Это позволяет легко найти конкретный префикс в дереве. Но если префикса не существует в дереве (как в случае моего поиска «GG»), похоже, нет никакого способа, кроме лексикографического сравнения, получить lower_bound.

Тот факт, что используемая мной реализация C ++, похоже, не реализует lower_bound должным образом, подтверждает мое подозрение, что это может быть невозможно. Тем не менее, тот факт, что вы можете перебирать дерево в алфавитном порядке, заставляет меня думать, что это может быть способ сделать это.

Кто-нибудь имеет опыт работы с этим или знает, можно ли реализовать функцию lower_bound с помощью Patricia Trie?