std::list
std::list is a doubly linked list. Unlike the previous containers, it does not store its elements contiguously. This means you lose out on the cache-friendliness but gain immense flexibility. Insertions and deletions, regardless of position, are a constant-time operation as long as you have an iterator to the position. However, access time is linear, making it less suited for tasks where random access is frequent. std::list is best suited for scenarios where the dataset experiences frequent insertions and deletions from both the middle and the ends, and direct access isn’t a priority.
Purpose and suitability
std::list is a doubly-linked list provided by the STL. Its strengths include the following:
- Facilitating constant-time insertions and deletions at any position (while sacrificing cache friendliness and fast searching)
- Preserving iterator validity during modifications (except when the element referred to by the iterator is removed)
It’...
