C++ STL: Sequence Containers and Use cases

This write-up will explain different Sequence containers, their respective features and mainly their appropriate use-cases.

Array

(C++11) (Sequence)
Features:
- Contiguous memory - allows Constant time Random access to elements.
- Strict Ordered Linear Sequence.
- Fixed-size Sequence container: they hold a specific number of elements ordered in a strict linear sequence. The container uses Implicit Constructors and Destructors to allocate the required space Statically.
- Its size is *Compile-time constant.
- No memory or time overhead.
- This Array class merely adds a layer of member and global functions to it, so that arrays can be used as standard containers.
- cannot be expanded or contracted dynamically.
- Zero-sized arrays are valid, but they should not be dereferenced.
- Swapping two array containers is a Linear and considerably less efficient operation, as it involves swapping of all members individually.
- Another unique feature of array containers is that they can be treated as ‘tuple’(C++11) objects.

Advantages over traditional C/C++ Arrays

std::array classes knows its own Size, whereas C-style arrays lack this property.
- So when passing to functions, we don’t need to pass Size of Array as a separate parameter.
With C-style array there is more risk of array being Decayed into a pointer.
- std::array classes don’t decay into pointers.
- See: Array_Decay_Avoiding.cpp
std::array classes are generally more efficient, light-weight and reliable than C-style arrays.
Arrays are Fixed-Size Sequence Containers:
- they hold a specific number of elements Ordered in a strict Linear Sequence.
std::array class internally DOES NOT contain any Data other than Elements it hold.(not even its Size)
- std::array class merely adds a layer of member and global functions to it, so that arrays can be used as standard containers.
Unlike the other standard containers, Arrays have a Fixed Size and they CANNOT be expanded or contracted dynamically.
Zero-sized arrays are valid, but they should not be dereferenced.
Unlike with the other containers in the Standard Library, Swapping two array containers is a Linear Operation that involves Swapping All the Elements in the ranges Individually, which generally is a considerably Less Efficient operation. On the other side, this allows the iterators to elements in both containers to keep their original container association.
- Another unique feature of std::array containers is that they can be treated as tuple objects:
- The std::array header overloads the get<> function to access the elements of the array as if it was a tuple, as well as specialized tuple_size and tuple_element types.

References:

Deque

Double-Ended queue
Sequence Container - Ordered in a strict Linear Sequence
Dynamic Size: Expanded/Contracted on both ends(front/back)
Random Access Iterators - Access to individual elements - in Constant Time
similar to vectors, but with efficient insertion/deletion of elements not only at the end, but at front/mid-positions also.
DOES NOT guaranteed to store all its elements in Contiguous Storage locations:
- elements of deque can be scattered in different chunks of storage, container keeps track of it for Random access.\
- Accessing elements in a deque by offsetting a pointer to another element causes undefined behavior.
- DO NOT access elements with pointer+offset.
deques perform worse for operations that involve frequent insertion/deletion of elements at positions other than the beginning or the end
- i.e. deque should NOT be used for insertion/deletion at mid-positions.

vector vs deque:

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways:
- vectors - use a contiguous storage locations that needs to be occasionally reallocated for growth,
- deque - Elements can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators).
Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.
deques are efficient with insertion and deletion of elements also at the beginning & end of the sequence.
vectors are efficient with insertion and deletion of elements ONLY at the end of the sequence.

Deque Decision Criteria

Size varies widely - Dynamic
Need to find Nth element - Random Access
Insert/Erase at the Front/Back
Insert/Erase at Mid-positions
Key:Value pair
Order is Important

References

Vector

Sequence
Ordered
Random Access
Insert/Erase at the End
Features:
- A vector is a Sequence
  - Sequence Container - Ordered in a strict Linear Sequence
- Random Access to elements - in Constant time
- Contiguous Memory.
  - which means that their elements can also be accessed using offsets on regular pointers to its elements.
- Insertion/Deletion:
  - Constant time - AT the END
  - Linear time - at the beginning/mid-positions
- Dynamic Size - An Advantage over Arrays. - Arrays that can change Size.
- Reallocation:
  - vectors internally use dynamically allocated arrays
  - To modify size dynamically, arrays needs to reallocated, and all elements needs to be moved, this is a less efficient, costly operation to perform frequently.
  - so, vectors allocate some extra memory for accommodation.
  - so, actual 'capacity' of vectors is greater than 'size' of vectors.
  - Vectors consume more memory than Arrays, due to above reasons.
  - When it is necessary to increase capacity(), vector usually increases it by a factor of two.
  - Reallocation INVALIDATES any iterators that point into the vector.
  - reserve() causes a reallocation manually.
    - The main reason for using reserve() is efficiency.
    - using reserve(), you can control the INVALIDATION of iterators.
  - Inserting or Deleting an element in the middle of a vector INVALIDATES all iterators.
  - Insertion/Deletion at the end of the vector, prevents vector iterators from being invalidated.
    - i.e. vectors are designed to be expanded at ‘END’
- Vectors more efficient in accessing Random elements, than deque / lists / forward_lists

Time Complexity Vector Operations

Operation	Time Complexity
Insert at Head	*O(n)*
Insert at Index	*O(n)*
Insert at Tail	*O(1)*
Remove at Head	*O(n)*
Remove at Index	*O(n)*
Remove at Tail	*O(1)*
Find Index	*O(1)*
Find/Search Object	*O(n)*

Vector Decision Criteria

Insert/Erase at the End
when Nth element is to be found - Random Access
when Order is important
Key:Value pair required
When there’s need of Insert/Erase in Middle/Front, as it invalidates iterators.
when Size will vary widely, as it causes Reallocation, which in turn invalidates iterators.

References

std::vector

Lists

Sequence
Insert/Erase at the Front/Back/Mid
NO Random Access
Iterate => Forward/Backward
Features:
- Sequence container
- Doubly Linked List. – Bidirectional Iterators.
- Iterate/Traverse in Both Forward/Backward.
- Insertion/Deletion:
  - Constant time - at the Beginning/End/Mid-position i.e. ANYWHERE.
    - i.e. We can 8insert(iterator pos, const T& x)* at a specific position
    - and erase(iterator pos) at the specific position.
- Lists have the important property that Insertion and Splicing DO NOT invalidate iterators to list elements
  - i.e. same iterators can be used, they get themselves aligned to updated list.
- Memory allocation is NOT Contagious.
- forward_list performs better than arrays/vectors/deque in actions as Inserting/Deleting/Extracting/Moving elements within the container.
- forward_list and list Do NOT have Direct/Random Access to elements.
  - Forward_list & List has to Iterate element by element to desired element.
  - i.e. Linear Time

Time Complexity List Operations

Operation	Time Complexity
Insert at Head	*O(1)*
Insert at Index	*O(n)*
Insert at Tail	*O(1)*
Remove at Head	*O(1)*
Remove at Index	*O(n)*
Remove at Tail	*O(1)*
Find Index	*O(1)*
Find/Search Object	*O(n)*

List Decision Criteria

If Insert/Erase is required in middle/front/end i.e. ANYWHERE.
Forward and Backward Traversal is required.
If required to merge collections. –> Study more.
Random Access is required.
If Order is important.
Key:Value pair required.

Reference

std::list

Forward List

Sequence - Singly Linked List
Iterate => Forward
Insert/Erase => Front/Back/Mid
Features:
- Singly Linked List: a list where each element is linked to the next element, but not to the previous element. – Forward Iterators
  - Singly Linked Lists are smaller and faster than double linked lists.
  - It is a Sequence that supports forward but not backward traversal.
- Insertion/Deletion
  - Constant time - at the Beginning or the End, or in the Middle.
    - i.e. We can insert/insert_after(iterator pos, const T& x) at a specific position
    - and erase/erase_after(iterator pos) at the specific position.
- like std::list, std::forward_list also has the important property that Insertion and Splicing DO NOT Invalidate iterators to list elements.
  - i.e. same iterators can be used, they get themselves alligned to updated list.
- This is the only container, that DO NOT have size() member function, because:
  - for efficiency considerations:
  - Being a Linked List, for having a size() member that takes constant time would require it to keep an internal counter for its size (as std::list does).
  - This would consume some extra storage and make insertion and removal operations slightly less efficient.

Important Functionality Difference between std::list & std::forward_list:

insert() & erase():
- Using these member functions carelessly, can result in disastrously slow programs.
- The problem is that insert() inserts the new element(s) before pos.
- This means that insert must find the iterator just before pos; this is a constant-time operation for std::list, since it is bidirectional.
- but for std::forward_list it must find that iterator by traversing the list from the beginning up to pos.
- In other words: insert() and erase() are slow operations anywhere but near the beginning of the std::forward_list.
insert_after() & erase_after():
- insert_after() and erase_after() are constant time operations:
  - you should always use insert_after() and erase_after() whenever possible.
  - If you find that insert_after() and erase_after() aren’t adequate for your needs, and that you often need to use insert() and erase() in the middle of the list, then you should probably use std::list instead of std::forward_list.
std::forward_list is more efficient than std::list
- As std::list consumes additional storage per element
- std::list has with a slight higher time overhead inserting and removing elements, as it has to fill both the pointers correctly.

Forward List Decision Criteria

If Insert/Erase is required in middle/front/end i.e. ANYWHERE.
If required to merge collections. –> Study more.
Backward Traversal is required.
Random Access is required.
If Order is important.
Key:Value pair required.

Reference

std::forward_list

PREVIOUSC++ STL Containers Selection Criteria

NEXTC, C++ Pointers: Reading & declaring the Pointer declarations the right way