The internal structure of a list is totally different from a vector or a deque. Thus, a list differs in several major ways compared with vectors and deques:
- A list does not provide random access. For example, to access the fifth element, you must navigate the first four elements following the chain of links. Thus, accessing an arbitrary element using a list is slow.
- Inserting and removing elements is fast at each position, and not only at one or both ends. You can always insert and delete an element in constant time because no other elements have to be moved. Internally, only some pointer values are manipulated.
- Inserting and deleting elements does not invalidate pointers, references, and iterators to other elements.
- A list supports exception handling in such a way that almost every operation succeeds or is a no-op. Thus, you can't get into an intermediate state in which only half of the operation is complete.
The member functions provided for lists reflect these differences compared with vectors and deques as follows:
- Lists provide neither a subscript operator nor at() because no random access is provided.
- Lists don't provide operations for capacity or reallocation because neither is needed. Each element has its own memory that stays valid until the element is deleted.
- Lists provide many special member functions for moving elements.
These member functions are faster versions of general algorithms that have the same names. They are faster because they only redirect pointers rather than copy and move the values.
Post a Comment