寻求支持常数时间拼接的STL风格C++双向链表实现

Absolutely! You can build a C++ doubly linked list that matches STL conventions and guarantees constant-time performance for all three splice overloads—including the range-based one—by simply skipping the cached size member. Since you’re okay with size() being linear time, this approach fits your needs perfectly.

Core Idea #

The standard std::list maintains a cached size value, which forces the range-based splice (transferring elements from first to last) to traverse the range to update size counts for both containers—turning it into linear time. By ditching the cached size, all splice operations only require adjusting a handful of pointers, keeping them strictly O(1) no matter which overload you use.

Key Implementation Details (STL-Aligned) #

To keep things familiar for STL users, structure the container with:

• A standard doubly linked node structure (prev/next pointers + data)
• Bidirectional iterators that support all standard operations (++, --, *, ->, etc.)
• A core interface mirroring std::list (with the only caveat being linear-time size())

Sample Implementation #

#include <iterator>
#include <utility>

// Doubly linked node structure
template <typename T>
struct ListNode {
    T data;
    ListNode* prev;
    ListNode* next;

    explicit ListNode(T&& val) : data(std::move(val)), prev(nullptr), next(nullptr) {}
    explicit ListNode(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

// STL-style list with constant-time splice for all overloads
template <typename T>
class SpliceFastList {
public:
    // Bidirectional iterator type
    class iterator {
    public:
        using value_type = T;
        using reference = T&;
        using pointer = T*;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::bidirectional_iterator_tag;

        iterator() : node(nullptr) {}
        explicit iterator(ListNode<T>* n) : node(n) {}

        reference operator*() const { return node->data; }
        pointer operator->() const { return &node->data; }

        iterator& operator++() {
            node = node->next;
            return *this;
        }
        iterator operator++(int) {
            iterator temp = *this;
            node = node->next;
            return temp;
        }

        iterator& operator--() {
            node = node->prev;
            return *this;
        }
        iterator operator--(int) {
            iterator temp = *this;
            node = node->prev;
            return temp;
        }

        bool operator==(const iterator& other) const { return node == other.node; }
        bool operator!=(const iterator& other) const { return node != other.node; }

        ListNode<T>* get_node() const { return node; }

    private:
        ListNode<T>* node;
    };

    // Default constructor
    SpliceFastList() : head(nullptr), tail(nullptr) {}

    // Rule of five (simplified)
    ~SpliceFastList() { clear(); }

    SpliceFastList(const SpliceFastList&) = delete;
    SpliceFastList& operator=(const SpliceFastList&) = delete;

    SpliceFastList(SpliceFastList&& other) noexcept : head(other.head), tail(other.tail) {
        other.head = other.tail = nullptr;
    }
    SpliceFastList& operator=(SpliceFastList&& other) noexcept {
        if (this != &other) {
            clear();
            head = other.head;
            tail = other.tail;
            other.head = other.tail = nullptr;
        }
        return *this;
    }

    // Basic container methods
    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }

    bool empty() const { return head == nullptr; }

    size_t size() const {
        size_t count = 0;
        for (ListNode<T>* curr = head; curr != nullptr; curr = curr->next) {
            ++count;
        }
        return count;
    }

    void clear() {
        while (head != nullptr) {
            ListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
        tail = nullptr;
    }

    void push_back(const T& val) {
        auto new_node = new ListNode<T>(val);
        insert_end(new_node);
    }

    void push_back(T&& val) {
        auto new_node = new ListNode<T>(std::move(val));
        insert_end(new_node);
    }

    // 1. Transfer entire source list
    void splice(iterator pos, SpliceFastList& other) {
        if (other.empty()) return;

        insert_range_before(pos, other.head, other.tail);
        other.head = other.tail = nullptr;
    }

    // 2. Transfer single element
    void splice(iterator pos, SpliceFastList& other, iterator it) {
        if (it == other.end()) return;

        ListNode<T>* moved_node = it.get_node();
        // Remove from source
        unlink_node(moved_node, other);
        // Insert into target
        insert_before(pos, moved_node);
    }

    // 3. Transfer range [first, last) - CONSTANT TIME!
    void splice(iterator pos, SpliceFastList& other, iterator first, iterator last) {
        if (first == last) return;

        ListNode<T>* first_node = first.get_node();
        ListNode<T>* last_node = last.get_node();
        ListNode<T>* range_tail = (last_node == nullptr) ? other.tail : last_node->prev;

        // Remove range from source
        if (first_node->prev != nullptr) {
            first_node->prev->next = last_node;
        } else {
            other.head = last_node;
        }
        if (last_node != nullptr) {
            last_node->prev = first_node->prev;
        } else {
            other.tail = first_node->prev;
        }

        // Insert range into target
        insert_range_before(pos, first_node, range_tail);
    }

private:
    ListNode<T>* head;
    ListNode<T>* tail;

    // Helper: Insert a single node before position
    void insert_before(iterator pos, ListNode<T>* node) {
        if (pos == begin()) {
            node->next = head;
            if (head != nullptr) head->prev = node;
            head = node;
            node->prev = nullptr;
            if (tail == nullptr) tail = node;
        } else if (pos == end()) {
            insert_end(node);
        } else {
            ListNode<T>* pos_node = pos.get_node();
            node->prev = pos_node->prev;
            node->next = pos_node;
            pos_node->prev->next = node;
            pos_node->prev = node;
        }
    }

    // Helper: Insert a node at the end
    void insert_end(ListNode<T>* node) {
        if (empty()) {
            head = tail = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
    }

    // Helper: Insert a range [start, end] before position
    void insert_range_before(iterator pos, ListNode<T>* start, ListNode<T>* end) {
        if (pos == begin()) {
            end->next = head;
            if (head != nullptr) head->prev = end;
            head = start;
            start->prev = nullptr;
            if (tail == nullptr) tail = end;
        } else if (pos == end()) {
            tail->next = start;
            start->prev = tail;
            tail = end;
            end->next = nullptr;
        } else {
            ListNode<T>* pos_node = pos.get_node();
            start->prev = pos_node->prev;
            end->next = pos_node;
            pos_node->prev->next = start;
            pos_node->prev = end;
        }
    }

    // Helper: Unlink a node from its container
    void unlink_node(ListNode<T>* node, SpliceFastList& container) {
        if (node->prev != nullptr) {
            node->prev->next = node->next;
        } else {
            container.head = node->next;
        }
        if (node->next != nullptr) {
            node->next->prev = node->prev;
        } else {
            container.tail = node->prev;
        }
        node->prev = node->next = nullptr;
    }
};

Important Notes #

• Iterator Validity: Just like std::list, iterators to elements remain valid after splice operations—only iterators pointing to the source container’s end() become invalid (if you transferred the entire list).
• Size() Caveat: Since size() traverses the entire list, avoid frequent calls if that path is performance-sensitive.
• STL Compatibility: This container’s interface mirrors std::list closely, so you can drop it into code expecting basic list operations without major changes (as long as you don’t rely on O(1) size()).

内容的提问来源于stack exchange，提问作者Ashley Cooster