UnrolledList

UnrolledList is a C++ template library providing an STL-compatible implementation of an Unrolled Linked List.

Unlike a standard doubly linked list where every element requires its own memory allocation and pointers, the UnrolledList stores a fixed-capacity array of elements within each node. This architecture significantly improves CPU cache performance and reduces memory fragmentation while maintaining O(1) insertions and deletions at the ends.

Key Features

• Hybrid Architecture: Combines the benefits of arrays (cache locality) and linked lists (fast splicing/insertion).
• STL Compatibility: Designed to behave like a standard C++ container.
  • Fully compliant with Container, ReversibleContainer, and AllocatorAwareContainer concepts.
  • Partially compliant with SequenceContainer.
• Custom Memory Management: Full support for std::allocator and custom allocators.
• Bidirectional Iterators: Supports standard traversal algorithms (e.g., std::find, std::reverse).
• Exception Safety: Provides Strong and Noexcept guarantees for critical operations.
• Zero Dependencies: Implemented without using standard library containers (std::vector, std::list, etc.) internally.

Technical Specifications

Template Parameters

The container is defined as:

template <
    typename T,
    std::size_t NodeCapacity,
    typename Allocator = std::allocator<T>
>
class UnrolledList;

• T: The type of element to be stored.
• NodeCapacity: The maximum number of elements stored in a single node before a new node is allocated.
• Allocator: The allocator to use for memory management.

Complexity & Exception Guarantees

The implementation focuses on rigorous exception safety and predictable algorithmic complexity:

Method	Complexity	Exception Guarantee
push_back	O(1)	Strong
push_front	O(1)	Strong
pop_back	O(1)	Noexcept
pop_front	O(1)	Noexcept
insert	O(1)*	Strong
erase	O(1)*	Noexcept
clear	O(N)	Noexcept

* Complexity for insert and erase is O(1) regarding the number of nodes, but O(M) regarding the shifting of elements within the specific node (where M <= NodeCapacity).

Integration

Requirements

• C++20 or higher
• Google Test (only required for running the test suite)

Usage Example

#include "UnrolledList.hpp"
#include <iostream>
#include <algorithm>

int main() {
    // Create a list of integers where each node holds up to 10 elements
    UnrolledList<int, 10> myList;

    // Fast push operations
    myList.push_back(10);
    myList.push_back(20);
    myList.push_front(5);

    // Iteration works just like std::list
    std::cout << "List contents: ";
    for (const auto& item : myList) {
        std::cout << item << " ";
    }
    std::cout << "\n";

    // STL Algorithm compatibility
    auto it = std::find(myList.begin(), myList.end(), 20);
    if (it != myList.end()) {
        myList.erase(it); // Remove 20
    }

    return 0;
}

Testing

The project uses the Google Test framework to ensure strict adherence to STL requirements and exception guarantees.

mkdir build && cd build
cmake ..
make
./tests