Разумно ли выдумывать категорию итератора, если мой контейнер находится между двумя существующими значениями?

Question

У меня есть контейнер веревки, использующий самоуравновешивающееся дерево статистики заказов в качестве основного хранилища (каждый узел дерева содержит переменную, но в целом довольно много элементов веревки, например, если для хранения символов используются узлы дерева, вероятно,~ 4000 элементов).

Разумно ли назначать веревочным итераторам std :: random_access_iterator_tag iterator_category, даже если операции +, + =, -, - = и т. Д. На самом деле являются логарифмической сложностью (с точки зрения расстояния оттекущая позиция)? Если новая позиция находится в текущем узле дерева (что должно быть намного чаще, чем большие скачки), то операция фактически O (1), как того требует произвольный доступ, только когда нужно пройти по дереву, истинноеO (1) сложность потеряна. Однако во всех случаях это намного лучше, чем O (n), поскольку подразумевается использование двунаправленного текста.

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

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

Answer 1

Предположим, вы используете контейнер из библиотеки. В документации библиотеки утверждается, что итераторы контейнера удовлетворяют требованиям итератора произвольного доступа. В вашей программе есть проблемы с производительностью, которые вы проследили до того, что оператор приращения этих итераторов был O (lg n) вместо O (1). Будете ли вы чувствовать себя оправданным в жалобе / регистрации сообщения об ошибке? Возможно.

Хотите написать код, на который будут жаловаться другие? Возможно нет. Ваш пробег может варьироваться, но обычно лучше занижать производительность, чем завышать ее. Мало кто жалуется на слишком быстрые вычисления.