plf:: library and this page Copyright (c) 2021, Matthew Bentley
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.
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.
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 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.
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, 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.
#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 type | Definition |
value_type |
T |
allocator_type |
Allocator |
size_type |
Allocator::size_type (pre-c++11) |
reference |
Allocator::reference (pre-c++11) |
const_reference |
Allocator::const_reference (pre-c++11) |
pointer |
Allocator::pointer (pre-c++11) |
const_pointer |
Allocator::const_pointer (pre-c++11) |
| default | explicit stack(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. |
stack<T> a_stack
Default constructor - default minimum group size is 8, default maximum
group size is std::numeric_limits<size_type>::max() / 2.
The reason for this maximum limitation is that each new group doubles the
number of existing elements in the stack. And since the maximum number of
elements that can be possibly held in a stack is
std::numeric_limits<size_type>::max(), the maximum group size must be
half that.
Example: plf::stack<int>
int_stack;
stack<T, custom_allocator<T> > a_stack
Using a custom allocator.
Example: plf::stack<int,
tbb::allocator<int> > int_stack;
Example2:
// Using an instance of an allocator as well as
it's type
tbb::allocator<int> alloc_instance;
plf::stack<int, tbb::allocator<int> >
int_stack(alloc_instance);
stack<T> a_stack(const size_type min_group_size)
This sets the minimum group size - for example, to 50 (unlike a vector,
these 50 elements are not constructed at this point). This may yield a
minor performance advantage if you know roughly how many elements are going
to be stored in your stack in advance. Minimum group size may not be lower
than 3.
Example: plf::stack<int>
int_stack(62);
stack<T> a_stack(const size_type min_group_size, const
size_type max_group_size)
This sets the minimum group size as above, as well as the maximum group
size - this can be useful if you want to limit memory usage. Minimum group
size may not be lower than 3. Maximum group size may not be larger than
std::numeric_limits<size_type>::max() / 2.
Example: plf::stack<int> int_stack(64,
512);
stack<T> a_stack(const stack &source)
Copies all contents from source. New minimum group size is the total
size of source, unless source's minimum group
size is larger than it's total size, in which case the new minimum group
size is the source's minimum group size. If source's total size is larger
than it's maximum group size, the new minimum group size is the same as the
source's maximum group size.
Example: plf::stack<int>
int_stack_2(int_stack_1);
stack<T> a_stack(stack && source) C++11 and
upwards
Moves all contents from source, does not alter any group sizes. Source
is now empty and can be used or destructed safely.
Example: plf::stack<int>
int_stack_2(std::move(int_stack_1));
void push(const the_type &element)
Push an element to the stack.
Example: object_stack.push(object1);
void push(the_type &&element) C++11 and
upwards
Move an element to the stack.
Example: object_stack.push(std::move(object1));
void emplace(Arguments ...parameters) C++11 and
upwards
Constructs an element directly on the stack using the the constructor
arguments specified.
Example: object_stack.emplace(10, 200,
"a");
void pop()
Pop the last push()'d element off the stack. In debug mode will test for
stack emptiness prior to operation via an assert. Calling pop() on an empty
stack in non-debug mode results in undefined behaviour.
Example: object_stack.pop();
the_type & top()
Return a reference to the last push()'d element on the stack. In debug
mode will test for stack emptiness prior to operation via an assert.
Calling top() on an empty stack in non-debug mode results in undefined
behaviour.
Example: object2 = object_stack.top();
size_type size()
Return the current number of elements stored on the stack.
Example: unsigned int j =
static_cast<unsigned int>(object_stack.size());
size_type max_size()
Returns the maximum number of elements that the allocator can store in
the container. This is an approximation as it does attempt to measure the
memory overhead of the container's internal memory structures. It is not
possible to measure the latter because a copy operation may change the
number of groups utilized for the same amount of elements, if the maximum
or minimum group sizes are different in the source container.
Example: std::cout << i_stack.max_size()
<< std::endl;
size_type capacity()
Returns total number of elements currently able to be stored in
container without expansion.
Example: std::cout << i_stack.capacity()
<< std::endl;
void reserve(size_type reserve_amount)
Preallocates memory space sufficient to store the number of elements
indicated by reserve_amount. Will not change minimum and
maximum group sizes. reserve_amount will be rounded up if it is lower than the minimum group size. By default the
maximum group size is the maximum number allowed by
size_type.
Example: i_stack.reserve(15);
void shrink_to_fit()
Reduces container capacity to the amount necessary to store all
currently stored elements. If the total number of elements is larger than
the maximum group size, the resultant capacity will be equal to
((total_elements / max_group_size) + 1) * max_group_size.
Invalidates all pointers, iterators and references to elements within the
container.
Example: i_stack.shrink_to_fit();
void trim()
Removes any trailing memory blocks within the container substructure, which may
be present in the scenario of many pushes followed by many pops. Unlike a
regular shrink_to_fit, does not shrink capacity to the size needed to
contain the currently-stored elements, simply frees up unused blocks.
Runtime cost is significantly lower than shrink_to_fit, but may not free as
much memory.
Example: i_stack.trim();
bool empty()
Returns a boolean indicating whether the stack is currently empty of
elements.
Example: if (object_stack.empty())
return;
void clear()
Empties the stack and removes all elements and groups.
Example: object_stack.clear();
void reshape(const size_type min_group_size, const
size_type max_group_size)
Changes the minimum and maximum internal group sizes, in terms of number
of elements stored per group. If the stack is not empty and either min_group_size is larger than the smallest group in the stack, or max_group_size is smaller than the largest group in the stack, the stack will be internally copy-constructed into a new stack which uses the new group sizes, invalidating all pointers/iterators/references.
Example: object_stack.reshape(1000,
10000);
void swap(stack &source)
Swaps the stack's contents with that of source.
Example: object_stack.swap(other_stack);
friend void swap(stack &A, stack &B)
External friend function, swaps the stack A's contents with that of
stack B (assumes both stacks have same element type).
Example: swap(object_stack,
other_stack);
stack & operator = (const stack &source)
Copy the elements from source stack to this stack, clearing this stack
of existing elements first.
Example: object_stack = object_stack2;
stack & operator = (const stack &&source) C++11 and
upwards
Move the elements from source stack to this stack, clearing this stack
of existing elements first. Source stack becomes empty and safely be reused or destructed.
Example: object_stack =
std::move(object_stack2);
bool operator == (const stack &source)
Compare contents of another stack to this stack. Returns a boolean to
indicate whether they are equal.
Example: if (object_stack == object_stack2)
return;
bool operator != (const stack &source)
Compare contents of another stack to this stack. Returns a boolean to
indicate whether they are not equal.
Example: if (object_stack != object_stack2)
return;
allocator_type get_allocator()
Returns a copy of the allocator used by this stack
void append(stack &source)
Optimized function for appending the source stack's elements to the top of the stack. The source stack becomes empty post-append. This is much faster than performing sequential pushes while popping from the source stack. Internally the source stacks' groups get moved directly. Pointers to elements in the source stack are not guaranteed to be valid after the append. Pointers to elements in the destination stack remain valid.
Example: object_stack.append(other_stack);
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.
Contact:
plf:: library and this page Copyright (c) 2021, Matthew Bentley