cppdsa::forward_list

An educational, header-only C++17 implementation modeled after std::forward_list.

The project explores how a singly linked standard-library-style container is built: node ownership, sentinel nodes, forward iterators, allocator rebinding, exception safety, node transfer, and list-specific algorithms. The implementation is intentionally kept in one readable header and is accompanied by a GoogleTest suite and comparative Google Benchmark scenarios.

Note

This is a learning project, not a drop-in replacement for std::forward_list. It aims for a familiar C++17 interface, but does not yet satisfy every standard container requirement. See Known limitations.

Highlights

• Header-only C++17 implementation
• Generic cppdsa::forward_list<T, Allocator> container
• Sentinel-head design with before_begin() support
• Mutable and constant forward iterators
• Copy, move, count, range, and initializer-list construction
• Insertion, erasure, assignment, and resizing operations
• merge, splice_after, remove, remove_if, reverse, unique, and stable merge sort
• Relational operators, non-member swap, and range deduction guide
• Basic stateful-allocator propagation through std::allocator_traits
• 36 GoogleTest cases and paired benchmarks against std::forward_list

Project layout

forward_list/
├── include/
│   └── cppdsa/
│       └── forward_list.hpp
├── tests/
│   ├── CMakeLists.txt
│   ├── construction_test.cpp
│   ├── assignment_and_iterator_test.cpp
│   ├── modifiers_test.cpp
│   ├── operations_test.cpp
│   ├── interface_test.cpp
│   ├── safety_and_types_test.cpp
│   └── test_helpers.hpp
├── benchmarks/
│   ├── CMakeLists.txt
│   ├── forward_list_benchmark.cpp
│   ├── modifiers_benchmark.cpp
│   ├── operations_benchmark.cpp
│   └── benchmark_helpers.hpp
├── CMakeLists.txt
├── LICENSE
└── README.md

Requirements

Using the container requires only:

• A C++17-compatible compiler
• The include directory on the compiler's include path

The library itself has no third-party dependencies. Building the optional development targets additionally requires:

• CMake 3.20 or newer
• Git and network access during the first configuration, unless dependencies are already cached

CMake fetches GoogleTest 1.17.0 for the test target and Google Benchmark 1.9.5 for the benchmark target.

Using the library

Clone the repository:

git clone https://github.com/R3na7/forward_list.git
cd forward_list

Include the header:

#include <cppdsa/forward_list.hpp>

The library does not require a separate build or installation step. Compile your program with include on the include path:

g++ -std=c++17 -Wall -Wextra -Wpedantic \
    -Iinclude main.cpp -o forward_list_example

Quick start

#include <cppdsa/forward_list.hpp>

#include <iostream>

int main() {
    cppdsa::forward_list<int> values{4, 1, 3, 2, 2};

    values.sort();
    values.unique();
    values.push_front(0);

    for (const int value : values) {
        std::cout << value << ' ';
    }

    std::cout << '\n';
}

Output:

0 1 2 3 4

Inserting after a position

A singly linked list cannot efficiently insert directly before an arbitrary element. Like std::forward_list, this implementation exposes a special iterator representing the position before the first element:

cppdsa::forward_list<int> values;

auto position = values.before_begin();
position = values.insert_after(position, 10);
position = values.insert_after(position, 20);
position = values.insert_after(position, 30);

The resulting list contains 10, 20, 30.

Transferring nodes

merge and splice_after relink existing nodes instead of copying their stored values:

cppdsa::forward_list<int> left{1, 3, 5};
cppdsa::forward_list<int> right{2, 4, 6};

left.merge(right);

After the operation, left contains 1, 2, 3, 4, 5, 6, while right is empty. Both inputs must be sorted with the same ordering before merge.

Implemented interface

Area	Operations
Construction	Default, allocator, count, value, range, copy, move, and initializer-list constructors
Assignment	Copy, move, initializer-list assignment, and assign
Iterators	before_begin, cbefore_begin, begin, cbegin, end, cend
Element access	front
Capacity	empty, max_size
Modifiers	clear, insert_after, emplace_after, erase_after, push_front, emplace_front, pop_front, resize, swap
List operations	merge, splice_after, remove, remove_if, reverse, unique, sort
Non-member operations	Relational operators and swap
Other	get_allocator and range-constructor class template argument deduction

As with std::forward_list, there is no size() member. The container does not store an element count, so determining the size requires a linear traversal.

Testing

The GoogleTest suite currently contains 36 tests covering:

• Construction, assignment, iterator conversion, and element access
• Modifier overloads, empty ranges, resizing, and swapping
• Node transfer through merge and all splice_after forms
• Removal, reversal, uniqueness, custom predicates, and comparisons
• Default and custom sorting, sort stability, and throwing comparators
• Exception safety for range insertion
• Move-only value types and object lifetime
• Regression coverage for a value passed to remove that aliases an element of the same list

Build and run the tests through CTest:

cmake -S . -B build-tests \
    -DCMAKE_BUILD_TYPE=Debug \
    -DFORWARD_LIST_BUILD_TESTS=ON \
    -DFORWARD_LIST_BUILD_BENCHMARKS=OFF

cmake --build build-tests --target forward_list_test -j
ctest --test-dir build-tests -C Debug --output-on-failure --no-tests=error

Run a subset with a GoogleTest filter:

./build-tests/tests/forward_list_test \
    --gtest_filter='ForwardListOperations.*'

Benchmarks

The Google Benchmark suite runs identical templated workloads for cppdsa::forward_list<int> and std::forward_list<int>. It covers:

Category	Scenarios
Construction and access	Range construction, same-size range assignment, traversal, finding the last element
Modifiers	push_front, pop_front, range insertion, clear, growing and shrinking resize
Removal and reordering	remove_if with 0%, 50%, and 100% removal, unique, reverse
Algorithms	Sorting random and presorted data, merging interleaved sorted lists
Node transfer	Whole-list, range, and single-element splice_after

Most scenarios run with 64, 512, 4096, and 32768 elements. Input generation and state restoration are excluded from timed regions where appropriate. Linear operations report an O(N) fit, while sorting reports an O(N log N) fit.

Build benchmarks in Release mode:

cmake -S . -B build-bench \
    -DCMAKE_BUILD_TYPE=Release \
    -DFORWARD_LIST_BUILD_TESTS=OFF \
    -DFORWARD_LIST_BUILD_BENCHMARKS=ON

cmake --build build-bench --target forward_list_benchmarks -j
./build-bench/benchmarks/forward_list_benchmarks

List the registered cases or validate them with a short dry run:

./build-bench/benchmarks/forward_list_benchmarks --benchmark_list_tests
./build-bench/benchmarks/forward_list_benchmarks --benchmark_dry_run

Run selected scenarios:

./build-bench/benchmarks/forward_list_benchmarks \
    --benchmark_filter='BM_SortRandom|BM_MergeInterleaved'

Save repeated measurements as JSON:

./build-bench/benchmarks/forward_list_benchmarks \
    --benchmark_repetitions=5 \
    --benchmark_report_aggregates_only=true \
    --benchmark_out=benchmark-results.json \
    --benchmark_out_format=json

Compare matching CppdsaIntList and StdIntList rows at the same N. Performance results depend on the compiler, optimization settings, allocator, CPU state, and background load; they are not a claim that either implementation is universally faster.

Complexity overview

Operation	Complexity
front, empty	O(1)
push_front, pop_front	O(1)
Single-element insert_after, erase_after, splice_after	O(1)
Range construction, assignment, traversal, and clear	O(n)
remove, remove_if, reverse, unique	O(n)
Whole-list and range splice_after	Linear in the transferred range when its end must be located
merge	O(n + m)
sort	O(n log n)

Implementation notes

The list stores a sentinel head node. before_begin() refers to this sentinel, which makes insertion and erasure at the front use the same link manipulation as operations in the middle of the list.

Each value lives in a separately allocated node. Storage is obtained through an allocator rebound to the node type, and node lifetime is managed through std::allocator_traits.

Range-based insertion and assignment build temporary lists before changing the destination, which prevents partially inserted ranges when element construction throws.

remove_if first transfers matching nodes into a temporary list and destroys them after traversal. This keeps an aliased value passed to remove alive until it is no longer inspected.

Sorting is implemented as stable merge sort over links. Nodes are rearranged without copying their stored values, and recovery logic reconnects remaining chains when the comparison function throws.

Known limitations

• The implementation is not a complete standard-conformance suite or a production replacement for std::forward_list.
• emplace_front and emplace_after do not yet support constructing T from multiple independent arguments.
• Fancy-pointer allocators and allocator-aware construction of stored values are not fully supported; internal links currently use raw pointers.
• Some range-overload constraints do not yet match the standard container requirements exactly.
• merge is functionally covered by tests, but some inputs cause more comparisons than the standard comparison bound permits.
• The tests cover the main behavior and several safety regressions, but they are not an exhaustive standard-library conformance test suite.

Contributing

This repository is primarily educational, but focused bug reports, implementation suggestions, tests, benchmarks, and documentation improvements are welcome.

License

This project is licensed under the MIT License. See LICENSE.