I have a use case where I need to store some amount of uint16_t variables in no particular order (although the actual type of variables is not relevant). I have decided to turn to the STL to look for a container that best suits my needs.

The objects in the container may get taken out of it to be used and put back into the container. Sort of how mechanics might have a single box of screwdrivers instead of putting screwdrivers in their pockets. The container need not perform any sorting on the stored objects and it does not matter what was taken out - the only requirement is to know whether there is anything left in the container.

My eyes turn to std::stack and std::forward_list. They both provide O(1) insertion (just alter the front element) and O(1) pop operation (again, just alter the front element and return the previous front). Problem is - I have no idea how they differ from each other conceptually.

I know that std::stack is an adapter that just wraps an actual STL container (std::deque by default), thus it might have some unintended overhead, depending on the container being wrapped.

I am inclined to use std::forward_list, but I'm looking for input from colleagues. If you have thoughts on the matter, please share them.

CodePudding user response：

TLDR: If you only need to add / remove the last element, use vector or stack. This is the fastest option and has the lowest overhead.

Long version: Look up comparisons between linked list and dynamic arrays, for example here: vector vs. list in STL

Most of the discussion will be about std::list but the same principles apply to forward_list

Short explanation on overhead and operation

Vector data structure:

• 1 dynamically allocated array
• 1 integer giving the number of used elements
• 1 integer giving the number of available elements (preallocated size)

(footnote: Actually not counters but pointers. Let's not worry about that).

Appending an element to the end of the vector:

1. Check if there is space available. If not, reallocate an array twice the current size. Because the vector grows to twice its size (exponential growth), this is very rare and does not affect performance much.
2. Copy element to the index in the array
3. Increment the counter

Removing an element from the end of the vector:

1. Decrement the counter. That's it (unless you have destructors)

Memory overhead: 24 bytes for the pointer and counters. 8 byte for the dynamic allocation of the array. Worst case 50% unused elements.

Forward list data structure:

• 1 pointer to first element
• 1 pointer to the last element
• In each element, 1 pointer to the next element

Forward list insertion:

1. Dynamically allocate a new element (expensive)
2. Set pointers (cheap)

Remove first element:

1. Change pointer from first to second element
2. Deallocate the element (expensive)

The computational overhead of the dynamic allocation is much higher than anything vector uses.

Memory overhead:

• 16 bytes for the two pointers in the base structure
• Per element 8 byte for the dynamic allocation, 8 byte for the pointer to the next element, 6 byte padding because allocators only work with multiples of 8 byte

For every 2 bytes used payload, there are 22 byte overhead compared to the 2-for-2 worst case in vector!