Skip to content

Latest commit

 

History

History
102 lines (76 loc) · 3.39 KB

README.md

File metadata and controls

102 lines (76 loc) · 3.39 KB

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