Quote: users and programs make assumptions about operator complexity; e.g., push and pop should be amortized constant time, string copy should be linear

Quotation Skeleton

Users (and algorithms) make basic assumptions about operator … assumptions. Consider some examples: --We expect the push … This means that a stack implementation which does … an unacceptable implementation. --We expect an implementation of … A well-known C++ standard library implementation contains a … Obviously, such an implementation is unusable for large … random access iterator interface … . However, it is important to keep them … bidirectional and random access iterators.   Google-1   Google-2

Copyright clearance needed for quotation.

Additional Titles

Quote: keep bidirectional iterators separate from random access iterators; e.g., different algorithms for rotate and random shuffle using these iterators

Related Topics

Topic: algorithmic complexity analysis (10 items)
Topic: efficiency (96 items)
Topic: data type as a set of operations (38 items)
Topic: iterator (13 items)
Topic: lists (7 items)