последовательные контейнеры и арифметика итераторов

Question

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

Я считал само собой разумеющимся, что каждый контейнер, кроме особых случаев, таких как forward_list, где это невозможно в одном направлении, полностью поддерживает итераторарифметика.Вместо этого я только что обнаружил, что универсальный контейнер поддерживает только очень специфический набор операций: * и -> (по понятным причинам), пре- и пост-инкремент и декремент (не уверены на 100% относительно post) и реляционные операторы равенства / неравенства.Более сложная арифметика зарезервирована для векторов, строк и deque.

Я не понимаю этого ограничения.По каким причинам нам запрещено, например, вычитать между двумя итераторами или добавлять int к итератору?В конце концов, если у нас есть доступ к пре / постинкременту / декременту, мы можем легко, хотя и неэффективно, реализовать сложение и вычитание, многократно повторяя эти операции с целочисленным счетчиком.

Answer 1

Вы упомянули причину в своем вопросе:

... хотя и неэффективно ...

Это хороший дизайн, чтобы не выполнять вычислительно сложные (обычно линейные или худшие) операции в операторах. Такая конструкция позволяет пользователям API предполагать, что операции сложения и вычитания имеют постоянную сложность, при этом не требуется знать спецификацию этой операции. Если бы такое предположение было ложным, программист мог бы легко написать программы, которые имели бы более асимптотическую сложность, чем предполагалось.

Такие линейные операции существуют в виде std::next, std::distance и т. Д. Программисты не делают (или не должны) делать предположения о сложности вызова функции, не зная спецификации этой функции.

---

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

Answer 2

Упомянутые вами неэффективные операции на самом деле доступны, предлагая std::distance и std::advance. (Есть также std::prev и std::next, по более тонким причинам.)

Причина, по которой не требуется, чтобы все итераторы, или, по крайней мере, все двунаправленные итераторы, поддерживали такие вещи, как operator+=, заключается в том, чтобы предупредить пользователей о том, что они делают что-то не настолько эффективное, как они этого ожидают. Легко написать что-то вроде *(iter+offset) в цикле, затем изменить тип контейнера с std::vector на std::set и не заметить, что вы случайно превратили операцию O(n) в операцию O(n^2).