CODEWITHSUNDEEP
c++iteratorcontainers
Andrea Bocco
Andrea Bocco

Reputation: 972

sequential containers and iterators arithmetic

I'm studying the sequential containers library and something made me think.

I had given for granted that every container, except special cases, like forward_list, where it's not possible in one direction, fully supports iterator arithmetic. Instead I just found out that the generic container supports only a very specific set of operations: * and -> (for obvious reasons), pre and post-increment and decrement (not 100% sure about post) and equality/inequality relational operators. More complex arithmetic is reserved for vectors, string and deque.

I don't understand this constraint. What are the reasons we are prohibited from, for example, subtracting between two iterators or adding an int to an iterator? After all, if we have access to pre/post-increment/decrement we can easily, even though inefficiently, implement addition and subtraction by repeatedly iterating those operations with an integer counter.

Upvotes: 1

Views: 291

Answers (2)

eerorika
eerorika

Reputation: 238411

You've mentioned the reason within your question:

... even though inefficiently ...

It is a good design, to not perform computationally complex (usually linear or worse) operations in operators. This design allows the users of the API to assume that addition and subtraction operations have constant complexity without needing to know the specification of that operation. If such assumption were false, the programmer could easily end up writing programs that have worse asymptotic complexity than they intended.

Such linear operations exist in the form of std::next, std::distance etc. Programmers don't (or shouldn't) make assumptions about complexity of a function call without knowing the specification of that function.

If you disagree with the design of the standard library, you can write an iterator adaptor, which adds the missing operator overloads, and use that.

Upvotes: 2

Sneftel
Sneftel

Reputation: 41513

The missing inefficient operations you mentioned are in fact available, offered by std::distance and std::advance. (There's also std::prev and std::next, for more subtle reasons.)

The reason not to require all iterators, or at least all bidirectional iterators, to support things like operator+=, is to warn users that they're doing something that's not as efficient as they might expect it to be. It's easy to write something like *(iter+offset) in a loop, later change the container type from a std::vector to a std::set, and not notice that you've accidentally turned an O(n) operation into an O(n^2) one.

Upvotes: 6

Related Questions