FlexStack

What is FlexStack?

FlexStack is a flexibly-sized stack similar to std::stack<T, std::vector>. Internally, it is implemented as a circular buffer deque, guaranteed to be stored in contiguous memory, thereby helping to avoid or minimize cache misses.

While we aim to create a high-performance data structure, our top priority is in giving the user easy control over the tradeoffs between CPU performance, memory, and cache misses.

Performance

FlexStack is slightly slower than the typical std::stack, but this is acceptable because of the inherent difference between Flex and std::deque; while Flex guarantees storage in contiguous memory, std::deque does not. As a result, we instead must compare against std::stack<T, std::vector>.

FlexStack is usually as fast as, or faster than, std::stack<T, std::vector>. Here’s how FlexStack ranks against the GCC implementation of std::stack, with std::vector as its underlying container…

  • Pushing (to back) is as fast.

  • Popping (from back) is faster.

  • Accessing is at least as fast.

If general performance is more important to you than contiguous memory, see SpeedStack.

Comparison to std::stack

FlexStack offers largely the same functionality as std::stack. However, it is not intended to feature-identical. Some functionality hasn’t been implemented yet, and we may not include some other features to leave room for future optimization and experimentation.

  • FlexStack does not offer iterators. This may be added in the future.

  • You cannot change the underlying data structure. Our base class is where most of the heavy lifting occurs.

  • Some advanced modifiers haven’t been implemented yet.

Technical Limitations

FlexStack can store a maximum of 4,294,967,294 objects. This is because it uses 32-bit unsigned integers for internal indexing, with the largest value reserved as INVALID_INDEX. The limit is calculated as follows.

2^{32} - 2 = 4,294,967,294

Using FlexStack

Including FlexStack

To include FlexStack, use the following:

#include "pawlib/flex_stack.hpp"

Creating a FlexStack

A FlexStack object is created by whatever means is convenient. It handles its own dynamic allocation for storing its elements.

When the FlexStack is first created, you must specify the type of its elements.

// Both of these methods are valid...
FlexStack<int> dish_sizes;

FlexStack<int>* dish_sizes = new FlexStack<int>;

Raw Copy

By default, FlexStack uses standard assignment for moving items when the internal data structure resizes. However, if you’re storing atomic data types, such as integers, additional performance gains may be achieved by having FlexStack use raw memory copying (memcpy) instead.

To switch to Raw Copy Mode, include true as the second template parameter (raw_copy).

FlexStack<int, true> i_use_rawcopy;

Resize Factor

When we run out of space in the data structure, we need to reallocate memory. To reduce the CPU cycles used on reallocation, we allocate more space than we immediately need. This resize factor is controllable.

By default, when the FlexStack resizes, it doubles its capacity (n * 2). This provides the best general performance. However, if you want to preserve memory at a small performance cost, you can switch to a resize factor of n * 1.5 (internally implemented as n + n / 2).

To switch to the 1.5 factor, include false as the third template parameter (factor_double).

FlexStack<int, true, false> i_resize_slower;

Reserve Size

We can specify the initial size (in elements) of the FlexStack in the constructor.

FlexStack<int>* temps_high = new FlexStack<int>(100);

Note

The FlexStack will always have minimum capacity of 2.

Adding Elements

Stacks are “Last-In-First-Out”; you insert to the end (or “back”), and remove from the back.

push()

We add new elements to the stack with a “push” to the back using the push() function. The alias push_back() is also provided for convenience. This function has a performance of O(1).

FlexStack<int> dish_sizes;
dish_sizes.push(22);
dish_sizes.push(18);
dish_sizes.push(18);
dish_sizes.push_back(12); // we can also use push_back()
// The FlexStack is now [22, 18, 18, 12]

Accessing Elements

at()

at() allows you to access the value at a given stack index.

FlexStack<string> albums;

// We'll push some values for our example
albums.push("End Of Silence");
albums.push("Comatose");
albums.push("Fireproof");

albums.at(1);
// This output yields "Comatose"

Alternatively, you can use the [] operator to access a value.

// Using the stack from above...

albums[2];
// This output yields "Fireproof"

peek()

peek() allows you to access the next element in the stack without modifying the data structure.

FlexStack<string> albums;

// We'll push some values for our example
albums.push("End Of Silence");
albums.push("Comatose");
albums.push("Fireproof");

albums.peek();

// This output yields "Fireproof"
// The stack remains ["End of Silence", "Comatose", "Fireproof"]

Removing Elements

In a stack, we typically remove and return elements from the end, or “back” of the stack. Imagine a stack of dishes - the last one added is the first one removed (ergo “last-in-first-out”).

clear()

clear() removes all the elements in the FlexStack.

FlexStack<int> pie_sizes;

pie_sizes.push(18);
pie_sizes.push(18);
pie_sizes.push(15);

// I ate everything...
pie_sizes.clear();

// The FlexStack is now empty.

This function always returns true, and will never throw an exception (no-throw guarantee).

erase()

erase() allows you to delete elements in a stack in a given range. Remaining values are shifted to fill in the empty slot. This function has a worst-case performance of O(n/2).

FlexStack<string> albums;

// We'll push some values for our example
albums.push("End Of Silence");
albums.push("Comatose");
albums.push("Fireproof");

// The stack is currently ["End of Silence", "Comatose", "Fireproof"]

albums.erase(0, 1);
// The first number in the function call is the lower bound
// The second number is the upper bound.
// The stack is now simply ["Fireproof"]

If any of the indices are too large, this function will return false. Otherwise, it will return true. It never throws exceptions (no-throw guarantee).

pop()

pop() returns the last value in an stack, and then removes it from the data set. The alias pop_back() is also provided. This function has a performance of O(1).

FlexStack<int> dish_sizes;

// We'll push some values for our example
dish_sizes.push(22);
dish_sizes.push(18);
dish_sizes.push(12);

// The stack is currently [22, 18, 12]

dish_sizes.pop();
// Returns 12. The stack is now [22, 18]

Warning

If the stack is empty, this function will throw the exception std::out_of_range.

Size and Capacity Functions

getCapacity()

getCapacity() returns the total number of elements that can be stored in the FlexStack without resizing.

FlexStack<int> short_term_memory;

short_term_memory.getCapacity();
// Returns 8, the default size.

length()

length() allows you to check how many elements are currently in the FlexStack.

FlexStack<string> albums;

// We'll push some values for our example
albums.push("End Of Silence");
albums.push("Comatose");
albums.push("Fireproof");

albums.length();
// The function will return 3

isEmpty()

isEmpty() returns true if the FlexStack is empty, and false if it contains values.

FlexStack<string> albums;

albums.isEmpty();
// The function will return true

// We'll push some values for our example
albums.push("End Of Silence");
albums.push("Comatose");
albums.push("Fireproof");

albums.isEmpty();
// The function will return false

isFull()

isFull() returns true if the FlexStack is full to the current capacity (before resizing), and false otherwise.

FlexStack<int> answers;

answers.isFull();
// The function will return false

// Push values until we are full, using the isFull() function to check.
while(!answers.isFull())
{
    answers.push(42);
}

reserve()

You can use reserve() to resize the FlexStack to be able to store the given number of elements. If the data structure is already equal to or larger than the requested capacity, nothing will happen, and the function will return false.

FlexStack<std::string> labors_of_hercules;

// Reserve space for all the elements we plan on storing.
labors_of_hercules.reserve(12);

labors_of_hercules.getCapacity();
// Returns 12, the requested capacity.

After reserving space in an existing FlexStack, it can continue to resize.

This function is effectively identical to specifying a size at instantiation.

shrink()

You can use shrink() function to resize the FlexStack to only be large enough to store the current number of elements in it. If the shrink is successful, it wil return true, otherwise it will return false.

FlexStack<int> plate_collection;

for(int i = 0; i < 100; ++i)
{
    plate_collection.push(i);
}

plate_collection.getCapacity();
// Returns 128, because FlexStack is leaving room for more elements.

// Shrink to only hold the current number of elements.
plate_collection.shrink();

plate_collection.getCapacity();
// Returns 100, the same as the number of elements.

After shrinking, we can continue to resize as new elements are added.

Note

It is not possible to shrink below a capacity of 2.