CD
Ну если компаратор транзитивный, так оно и есть. И если он транзитивный, то для map он не может вернуть более одного элемента (если сравнение по key_type).
Аргумент для equal_range transparent не компаратор, а специальный
Size: a a a
2021 February 03
DS
Аргумент для equal_range transparent не компаратор, а специальный
Там отдельные имплементации ж в любом случае, по произвольному ключу запрещено для не transparent. Ну и в libcxx соптимизировали по ключу для map.
DS
Аргумент для equal_range transparent не компаратор, а специальный
Так то можно например написать transparent comparator для пар который заодно сможет сравнивать по first. И через equal_range(FirstType) получать диапазоны с одинаковым key.first.
CD
Так то можно например написать transparent comparator для пар который заодно сможет сравнивать по first. И через equal_range(FirstType) получать диапазоны с одинаковым key.first.
Я понимаю, да
CD
Так то можно например написать transparent comparator для пар который заодно сможет сравнивать по first. И через equal_range(FirstType) получать диапазоны с одинаковым key.first.
Можно еще в этом случае компаратор, выдающий нетранзитивное равенство, использовать :)
CD
Так то можно например написать transparent comparator для пар который заодно сможет сравнивать по first. И через equal_range(FirstType) получать диапазоны с одинаковым key.first.
есть такая известная в узких кругах штука max(lhs.second, lhs.first + rhs.second) <=> max(rhs.second, rhs.first + lhs.second)
DS
Можно еще в этом случае компаратор, выдающий нетранзитивное равенство, использовать :)
Ну и вот поиск upper_bound итерацией это мне кажется баг:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
CD
Ну и вот поиск upper_bound итерацией это мне кажется баг:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
хм... а это не сломается уже на нормальном запросе transparent компаратора для мультимапы из одинаковых элементов?
CD
в любом случае крякает багом (должно быть в точности как в обычном случае)
DS
хм... а это не сломается уже на нормальном запросе transparent компаратора для мультимапы из одинаковых элементов?
Не, там по сравнениям то смысл тот же самый что и в upper_bound.
CD
Не, там по сравнениям то смысл тот же самый что и в upper_bound.
нельзя в мультимапе итерировать весь range, ответ может быть вся мапа
АФ
Прошу прощения)
А может вы подскажите чат, в котором можно выставлять данную информацию?
А может вы подскажите чат, в котором можно выставлять данную информацию?
SA
Я так понимаю, Вам следует обратить внимание на это:
Объявления о вакансиях и евенты - в лс @AlexFailsО местном чате по шарпу, увы, не слышал (подозреваю, впрочем, что такой есть).
АФ
Понял, спасибо)
АР
Ну и вот поиск upper_bound итерацией это мне кажется баг:
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h#L1407
Может я например разложил числа типа четные налево, нечетные направо и через equal_range получаю диапазоны чётный/нечётный. Это ж половину дерева придется обойти.
при этом по идее стандарт гарантирует ассимптотику операций )
АР
в этом то и заключается мой изначальный вопрос
АР
если упорядоченный контейнер отсортирован по Compare1, а мы делаем transparent операции по Compare2, где упорядоченность по Compare1 гарантирует упорядоченность по Compare2, но не наоборот, то сохраняются ли все наши гарантии?
АР
кажется что например гарантия "equal_range выполняется за log N" уже не работает для некоторых stl