Home

PLF C++ Library - plf::stack

Intro

plf::stack is a container that gives the programmer the functionality of a FILO (first-in, last-out) stack. It is a more efficient drop-in replacement for std::stack, and faster than all std:: containers in the context of a stack. Like plf::colony it never invalidates references/pointers to non-popped elements, making it at least potentially useful for programming with containers of inter-related data structures. It supports C++11 move and emplace semantics and operations.

Implementation

plf::stack uses the same chained-group memory allocation pattern as plf::colony ie. it is made up of a linked chain of 'groups', structs containing a memory block and metadata, with a growth factor of 2 for the memory blocks. The metadata within the groups - 'elements' (pointer to the memory block), previous_group (pointer or NULL), next_group (pointer or NULL), and 'end' (pointer to last element in memory block) - aid respectively in the identification of when when a pop reaches the start of the memory block, iterating backwards to the previous group, iterating forwards to the next group, and identifying when a push reaches the capacity of any given memory block.

When capacity of the current memory block is reached, a new group is created and linked to via the next_group pointer. plf::stack does not release memory blocks to the OS when the beginning of a group is reached via pop() and navigation to a previous group completed (this is deferred to the 'trim_trailing_groups' function, to be called by the programmer when convenient to the use-case). This avoids a deallocation/reallocation cost which could occur if the stack was pushed/popped repeatedly and group-boundaries crossed repeatedly in the process.

License

plf::stack is under a permissive zlib license. This means: Software is used on 'as-is' basis. It can be modified and used in commercial software. Authors are not liable for any damages arising from its use. The distribution of a modified version of the software is subject to the following restrictions:

Download

Download here (9kb zip file) or view the repository.
plf::stack is a simple .h header-only library, to be used with an #include command.

If you are interested in benchmarking you can also download the plf benchmark suite (44kb zip file), which includes plf::nanotimer.

Function Descriptions and syntax

plf::stack meets the requirements of the C++ Container and AllocatorAwareContainer concepts.

For the most part the syntax and semantics of plf::stack functions are the same as std::stack. However there are a few key differences, such as the meaning of using a number in the constructor. Formal description is as follows:

template <class T, class Allocator = std::allocator <T> > class stack

T - the element type. In general T must meet the requirements of Erasable, CopyAssignable and CopyConstructible.
However, if emplace is utilized to insert elements into the stack, and no functions which involve copying or moving are utilized, T is only required to meet the requirements of Erasable.
If move-insert is utilized instead of emplace, T must also meet the requirements of MoveConstructible .
Allocator - an allocator that is used to acquire memory to store the elements. The type must meet the requirements of Allocator. The behavior is undefined if Allocator::value_type is not the same as T.

Basic example of usage

#include <iostream>
#include "plf_stack.h"

int main(int argc, char **argv)
{
  plf::stack<int> i_stack;

  // Insert 100 ints:
  for (int i = 0; i != 100; ++i)
  {
    i_stack.push(i);
  }

  // Total the ints:
  int total = 0;

  while (!i_stack.empty())
  {
    total += i_stack.top();
    i_stack.pop();
  }

  std::cout << "Total: " << total << std::endl;
  std::cin.get();
  return 0;
} 

Member types

Member type Definition
value_type T
allocator_type Allocator
size_type Allocator::size_type (pre-c++11)
std::allocator_traits<Allocator>::size_type (post-c++11)
reference Allocator::reference (pre-c++11)
value_type & (post-c++11)
const_reference Allocator::const_reference (pre-c++11)
const value_type & (post-c++11)
pointer Allocator::pointer (pre-c++11)
value_type & (post-c++11)
const_pointer Allocator::const_pointer (pre-c++11)
std::allocator_traits<Allocator>::const_pointer (post-c++11)

Constructors

default explicit stack(const allocator_type &alloc = allocator_type())
explicit stack(const size_type min_group_size, const size_type max_group_size = std::numeric_limits<size_type>::max() / 2, const allocator_type &alloc = allocator_type())
copy stack(const stack &source)
move stack(const stack &&source) noexcept (C++11 and upwards)

Constructor usage examples

Member functions

Benchmarks

Last updated 17-11-2016 v1.04

The test setup is an E8500 (Core2Duo) on an Intel motherboard, 8GB ram, running GCC 5.1 x64 as compiler. Build settings are "-O2;-march=native;-std=c++11;-fomit-frame-pointer". Results for Microsoft Visual Studio 2015 Update 3 under a Haswell core CPU can be found here. Tests are based on a sliding scale of number of runs vs number of elements, so a test with only 10 elements in a container may average 100000 runs, whereas a test with 100000 elements may only average 10 runs. This tends to give adequate results without overly lengthening test times.

Tests are carried out on the following types: (a) a 8-bit type ie. char, (b) a 32-bit type ie. int, (c) a 64-bit type ie. double, (d) a small struct containing two pointers and four scalar types, and (e) a large struct containing 2 pointers, 4 scalar types, a large array of ints and a small array of chars. In order to better facilitate accurate time-keeping for short tests, both container construction and destruction times are included in the tests. The sequence is as follows: construction, push N elements, read (back) + pop all elements, destruction. Because unlike a regular container, a stack must be pushed for every pop, and popped for every read, it most sense to combine these two timings and compare on that basis, as what is most important is the overall time taken. For that reason both separate and combined ("total time") benchmarks are presented below.

Construction + Push

Click images or hover over to see results at linear scale instead

test result graph
test result graph
test result graph
test result graph
test result graph

Back + Pop + Destruction

Click images or hover over to see results at linear scale instead

test result graph
test result graph
test result graph
test result graph
test result graph

Total Time

Click images or hover over to see results at linear scale instead

test result graph
test result graph
test result graph
test result graph
test result graph

Conclusion

Simply put, plf::stack out-performs both std::stack (std::deque) and std::vector once you take into account both push and pop time, and we can see that the larger the stored type is, the greater the performance advantage is.

Version history

Contact: footer
plf:: library and this page Copyright (c) 2017, Matthew Bentley