PLF Library - stack (original) (raw)

Home

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 and has the following averaged performance characteristics versus std::stack:

Averaged across total numbers of stored elements ranging between 10 and 1000000. The benchmark in question is total time taken to construct, push all elements, read and pop all elements, then destruct. See benchmarks for more info.

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()' 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 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.

Function Descriptions and syntax

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 ability to specify min/max memory block sizes 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, CopyAssignableand 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::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::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)Source stack has same status as an empty stack post-move.

Constructor usage examples

Member functions

Benchmarks

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.

Benchmark results for stack v1.52 under GCC 9.2 x64 on an Intel Xeon E3-1241 (Haswell) are here.

Old benchmark results for stack v1.04 v3.87 under GCC 5.1 x64 on an Intel E8500 (Core2) are here,
and for stack v1.05 under MSVC 2015 update 3 on haswell here.

Version history

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