1

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.

Prakhar Tomar
  • 23
  • 1
  • 5
selamba
  • 384
  • 4
  • 12
  • 1
    Almost always `std::vector` unless you can measure the difference. Watch https://channel9.msdn.com/Events/Build/2014/2-661 from 45:48 for why. – Richard Critten Nov 07 '21 at 12:44
  • @RichardCritten The container needs to be static constinit. There is no place in the code where I can call vector.reserve() without gnu::constructor or #pragma startup. – selamba Nov 07 '21 at 12:54

1 Answers1

3

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!

Homer512
  • 9,144
  • 2
  • 8
  • 25
  • https://en.cppreference.com/w/cpp/container/stack states that the template parameter "Container" is std::deque by default. Is the website wrong? – selamba Nov 07 '21 at 12:53
  • I read your example and I am even more inclined to use std::forward_list instead of vector – selamba Nov 07 '21 at 12:56
  • @selama: Regarding stack: You are right. This is a weird decision. stack with vector would work better but whatever. One more reason to just use vector. Regarding forward_list, what do you think makes it more useful for your case? – Homer512 Nov 07 '21 at 13:02
  • I do not care whatsoever about middle insertions. My only concerns are: fast insertion to front, fast pop from front. I do not need to know the size of the container or insert into the middle. Singly linked list just seems like a natural fit. Vector has more features and that makes me think that it also has some overhead required to support those extra features. – selamba Nov 07 '21 at 13:12
  • Ran a benchmark comparing vector and forward_list in conceptually identical use cases. Vector is 4.1 times faster. I have 0 clue why, but a benchmark is a benchmark. – selamba Nov 07 '21 at 13:47
  • @selamba Here is a two part explanation on how dynamic memory allocation works. Notice how complex it is. forward_list needs this for every single element. vector does is very rarely when it runs out of preallocated space. https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/ – Homer512 Nov 07 '21 at 13:51