list.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_LIST_HPP__
#define NEFORCE_CORE_CONTAINER_LIST_HPP__

 
#include "NeForce/core/algorithm/compare.hpp"
#include "NeForce/core/interface/icollector.hpp"
#include "NeForce/core/interface/iiterator.hpp"
#include "NeForce/core/memory/standard_allocator.hpp"
#include "NeForce/core/utility/compressed_pair.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <typename T>
struct list_node {
    T data;                    
    list_node* prev = nullptr; 
    list_node* next = nullptr; 

    list_node() noexcept(is_nothrow_default_constructible_v<T>) :
    data() {}

    template <typename... Args>
    explicit list_node(Args&&... args) noexcept(is_nothrow_constructible_v<T, Args...>) :
    data(_NEFORCE forward<Args>(args)...) {}
};
 

template <bool IsConst, typename List>
struct list_iterator : iiterator<list_iterator<IsConst, List>> {
public:
    using container_type = List;                                      
    using value_type = typename container_type::value_type;           
    using size_type = typename container_type::size_type;             
    using difference_type = typename container_type::difference_type; 
    using iterator_category = bidirectional_iterator_tag;             
    using reference = conditional_t<IsConst, typename container_type::const_reference,
                                    typename container_type::reference>; 
    using pointer = conditional_t<IsConst, typename container_type::const_pointer,
                                  typename container_type::pointer>; 
 
private:
    using node_type = list_node<value_type>; 
 
    node_type* current_ = nullptr;              
    const container_type* container_ = nullptr; 
 
public:
    list_iterator() noexcept = default;
    ~list_iterator() = default;
 
    list_iterator(const list_iterator&) noexcept = default;
    list_iterator& operator=(const list_iterator&) noexcept = default;
    list_iterator(list_iterator&&) noexcept = default;
    list_iterator& operator=(list_iterator&&) noexcept = default;

    list_iterator(node_type* ptr, const container_type* list) noexcept :
    current_(ptr),
    container_(list) {}

    NEFORCE_NODISCARD reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to dereference on a null pointer");
        NEFORCE_DEBUG_VERIFY(current_ != container_->head_, "Attempting to dereference out of boundary");
        return current_->data;
    }

    void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to increment a null pointer");
        NEFORCE_DEBUG_VERIFY(current_ != container_->head_, "Attempting to increment out of boundary");
        current_ = current_->next;
    }

    void decrement() noexcept {
        NEFORCE_DEBUG_VERIFY(current_ && container_, "Attempting to decrement a null pointer");
        NEFORCE_DEBUG_VERIFY(current_->prev != container_->head_, "Attempting to decrement out of boundary");
        current_ = current_->prev;
    }

    NEFORCE_NODISCARD bool equal(const list_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to equal to a different container");
        return current_ == rhs.current_;
    }

    NEFORCE_NODISCARD node_type* base() const noexcept { return current_; }

    NEFORCE_NODISCARD const container_type* container() const noexcept { return container_; }
};
 

template <typename T, typename Alloc = allocator<list_node<T>>>
class list : public icollector<list<T, Alloc>> {
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
    static_assert(is_same_v<list_node<T>, typename Alloc::value_type>, "allocator type mismatch.");
    static_assert(is_object_v<T>, "list only contains object types.");
 
public:
    using pointer = T*;                                                       
    using reference = T&;                                                     
    using const_pointer = const T*;                                           
    using const_reference = const T&;                                         
    using value_type = T;                                                     
    using size_type = size_t;                                                 
    using difference_type = ptrdiff_t;                                        
    using iterator = list_iterator<false, list>;                              
    using const_iterator = list_iterator<true, list>;                         
    using reverse_iterator = _NEFORCE reverse_iterator<iterator>;             
    using const_reverse_iterator = _NEFORCE reverse_iterator<const_iterator>; 
    using allocator_type = Alloc;                                             
 
private:
    using node_type = list_node<T>; 
    using link_type = node_type*;   
 
    link_type head_ = nullptr;                                                    
    compressed_pair<allocator_type, size_type> pair_{default_construct_tag{}, 0}; 
 
    template <bool, typename>
    friend struct list_iterator;
 
private:
    template <typename... Args>
    link_type create_node(Args&&... args) {
        link_type p = pair_.get_base().allocate();
        try {
            _NEFORCE construct(&p->data, _NEFORCE forward<Args>(args)...);
        } catch (...) {
            pair_.get_base().deallocate(p);
            throw;
        }
        return p;
    }

    void destroy_node(link_type p) noexcept(is_nothrow_destructible_v<node_type>) {
        _NEFORCE destroy(p);
        pair_.get_base().deallocate(p);
    }

    void init_header() {
        head_ = pair_.get_base().allocate();
        try {
            _NEFORCE construct(head_);
        } catch (...) {
            pair_.get_base().deallocate(head_);
            throw;
        }
        head_->prev = head_->next = head_;
    }
 
public:
    list() { list::init_header(); }

    explicit list(size_type n) :
    list(n, _NEFORCE initialize<T>()) {}

    list(size_type n, T&& value) {
        list::init_header();
        iterator pos = end();
        try {
            while (n--) {
                pos = list::emplace(pos, _NEFORCE forward<T>(value));
            }
        } catch (...) {
            clear();
            throw;
        }
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    list(Iterator first, Iterator last) {
        list::init_header();
        iterator pos = end();
        try {
            while (first != last) {
                pos = list::emplace(pos, *first);
                ++first;
            }
        } catch (...) {
            clear();
            throw;
        }
    }

    list(std::initializer_list<T> ilist) :
    list(ilist.begin(), ilist.end()) {}

    list& operator=(std::initializer_list<T> ilist) {
        clear();
        list::insert(begin(), ilist.begin(), ilist.end());
        return *this;
    }

    list(const list& other) :
    list(other.begin(), other.end()) {}

    list& operator=(const list& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        list tmp(other);
        list::swap(tmp);
        return *this;
    }

    list(list&& other) noexcept(is_nothrow_swappable_v<compressed_pair<allocator_type, size_type>>) {
        init_header();
        list::swap(other);
    }

    list& operator=(list&& other) noexcept(is_nothrow_swappable_v<compressed_pair<allocator_type, size_type>> &&
                                           is_nothrow_destructible_v<node_type>) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        clear();
        list::swap(other);
        return *this;
    }

    ~list() {
        link_type p = head_->next;
        while (p != head_) {
            link_type q = p;
            p = p->next;
            list::destroy_node(q);
        }
        list::destroy_node(head_);
    }

    NEFORCE_NODISCARD iterator begin() noexcept { return iterator{head_->next, this}; }

    NEFORCE_NODISCARD iterator end() noexcept { return iterator{head_, this}; }

    NEFORCE_NODISCARD const_iterator begin() const noexcept { return cbegin(); }

    NEFORCE_NODISCARD const_iterator end() const noexcept { return cend(); }

    NEFORCE_NODISCARD reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }

    NEFORCE_NODISCARD reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

    NEFORCE_NODISCARD const_reverse_iterator rbegin() const noexcept { return crbegin(); }

    NEFORCE_NODISCARD const_reverse_iterator rend() const noexcept { return crend(); }

    NEFORCE_NODISCARD const_iterator cbegin() const noexcept { return const_iterator{head_->next, this}; }

    NEFORCE_NODISCARD const_iterator cend() const noexcept { return const_iterator{head_, this}; }

    NEFORCE_NODISCARD const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }

    NEFORCE_NODISCARD const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }

    NEFORCE_NODISCARD size_type size() const noexcept { return pair_.value; }

    NEFORCE_NODISCARD size_type max_size() const noexcept { return static_cast<size_type>(-1); }

    NEFORCE_NODISCARD bool empty() const noexcept { return head_->next == head_; }

    NEFORCE_NODISCARD reference front() noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "front called on empty list");
        return head_->next->data;
    }

    NEFORCE_NODISCARD const_reference front() const noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "front called on empty list");
        return head_->next->data;
    }

    NEFORCE_NODISCARD reference back() noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "back called on empty list");
        return head_->prev->data;
    }

    NEFORCE_NODISCARD const_reference back() const noexcept {
        NEFORCE_DEBUG_VERIFY(!empty(), "back called on empty list");
        return head_->prev->data;
    }

    template <typename... Args>
    iterator emplace(iterator position, Args&&... args) {
        link_type temp = list::create_node(_NEFORCE forward<Args>(args)...);
        temp->next = position.base();
        temp->prev = position.base()->prev;
        position.base()->prev->next = temp;
        position.base()->prev = temp;
        ++pair_.value;
        return {temp, this};
    }

    template <typename... Args>
    iterator emplace_back(Args&&... args) {
        return list::emplace(end(), _NEFORCE forward<Args>(args)...);
    }

    template <typename... Args>
    iterator emplace_front(Args&&... args) {
        return list::emplace(begin(), _NEFORCE forward<Args>(args)...);
    }

    void push_front(const T& value) { list::insert(begin(), value); }

    void push_front(T&& value) { list::insert(begin(), _NEFORCE forward<T>(value)); }

    void push_back(const T& value) { list::insert(end(), value); }

    void push_back(T&& value) { list::insert(end(), _NEFORCE forward<T>(value)); }

    void pop_front() noexcept { list::erase(begin()); }

    void pop_back() noexcept { list::erase({head_->prev, this}); }

    void assign(const size_type n, const T& value) {
        clear();
        list::insert(begin(), n, value);
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void assign(Iterator first, Iterator last) {
        clear();
        list::insert(begin(), first, last);
    }

    void assign(std::initializer_list<T> ilist) { list::assign(ilist.begin(), ilist.end()); }

    iterator insert(iterator position, const T& value) { return list::emplace(position, value); }

    iterator insert(iterator position, T&& value) { return list::emplace(position, _NEFORCE move(value)); }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void insert(iterator position, Iterator first, Iterator last) {
        if (first == last) {
            return;
        }
 
        link_type original_prev = position.base()->prev;
        link_type current_prev = original_prev;
        link_type first_inserted = nullptr;
 
        try {
            while (first != last) {
                link_type temp = list::create_node(*first);
                temp->prev = current_prev;
                temp->next = position.base();
                current_prev->next = temp;
                position.base()->prev = temp;
                if (first_inserted == nullptr) {
                    first_inserted = temp;
                }
                current_prev = temp;
                ++pair_.value;
                ++first;
            }
        } catch (...) {
            if (first_inserted != nullptr) {
                link_type to_delete = first_inserted;
                while (to_delete != position.base()) {
                    link_type next = to_delete->next;
                    list::destroy_node(to_delete);
                    --pair_.value;
                    to_delete = next;
                }
                original_prev->next = position.base();
                position.base()->prev = original_prev;
            }
            throw;
        }
    }

    void insert(iterator position, std::initializer_list<T> ilist) {
        list::insert(position, ilist.begin(), ilist.end());
    }

    void insert(iterator position, size_type n, const T& value) {
        if (n == 0) {
            return;
        }
 
        link_type original_prev = position.base()->prev;
        link_type current_prev = original_prev;
        link_type first_inserted = nullptr;
 
        try {
            while (n--) {
                link_type temp = list::create_node(value);
                temp->prev = current_prev;
                temp->next = position.base();
                current_prev->next = temp;
                position.base()->prev = temp;
                if (first_inserted == nullptr) {
                    first_inserted = temp;
                }
                current_prev = temp;
                ++pair_.value;
            }
        } catch (...) {
            if (first_inserted != nullptr) {
                link_type to_delete = first_inserted;
                while (to_delete != position.base()) {
                    link_type next = to_delete->next;
                    list::destroy_node(to_delete);
                    --pair_.value;
                    to_delete = next;
                }
                original_prev->next = position.base();
                position.base()->prev = original_prev;
            }
            throw;
        }
    }

    iterator erase(iterator position) noexcept(is_nothrow_destructible_v<node_type>) {
        if (empty()) {
            return end();
        }
        link_type ret = position.base()->next;
        position.base()->prev->next = position.base()->next;
        position.base()->next->prev = position.base()->prev;
        list::destroy_node(position.base());
        --pair_.value;
        return iterator{ret, this};
    }

    iterator erase(iterator first, iterator last) noexcept(is_nothrow_destructible_v<node_type>) {
        while (first != last) {
            first = list::erase(first);
        }
        return first;
    }

    void clear() noexcept(is_nothrow_destructible_v<node_type>) {
        link_type cur = head_->next;
        while (cur != head_) {
            link_type temp = cur;
            cur = cur->next;
            list::destroy_node(temp);
            --pair_.value;
        }
        head_->prev = head_;
        head_->next = head_;
    }

    void swap(list& other) noexcept(is_nothrow_swappable_v<allocator_type>) {
        _NEFORCE swap(head_, other.head_);
        _NEFORCE swap(pair_, other.pair_);
    }

    void transfer(iterator position, iterator first, iterator last) {
        if (position == last) {
            return;
        }
        last.base()->prev->next = position.base();
        first.base()->prev->next = last.base();
        position.base()->prev->next = first.base();
        link_type tmp = position.base()->prev;
        position.base()->prev = last.base()->prev;
        last.base()->prev = first.base()->prev;
        first.base()->prev = tmp;
    }

    template <typename Pred>
    void remove_if(Pred pred) {
        iterator iter = begin(), last = end();
        while (iter != last) {
            if (pred(*iter)) {
                iter = list::erase(iter);
            } else {
                ++iter;
            }
        }
    }

    void remove(const T& value) {
        return list::remove_if([&](const T& other) -> bool { return other == value; });
    }

    void splice(iterator position, list& other) {
        if (!other.empty()) {
            size_type n = other.pair_.value;
            list::transfer(position, other.begin(), other.end());
            pair_.value += n;
            other.pair_.value = 0;
        }
    }

    void splice(iterator position, list& other, iterator iter) {
        iterator j = iter;
        ++j;
        if (iter == position || j == position) {
            return;
        }
        list::transfer(position, iter, j);
        ++pair_.value;
        --other.pair_.value;
    }

    void splice(iterator position, list& other, iterator first, iterator last) {
        if (first == last) {
            return;
        }
        size_type n = 0;
        for (iterator it = first; it != last; ++it) {
            ++n;
        }
        list::transfer(position, first, last);
        pair_.value += n;
        other.pair_.value -= n;
    }

    template <typename Pred>
    void merge_if(list& other, Pred pred) {
        iterator first1 = begin(), first2 = other.begin();
        iterator last1 = end(), last2 = other.end();
 
        while (first1 != last1 && first2 != last2) {
            if (!pred(*first2, *first1)) {
                ++first1;
            } else {
                iterator temp = first2;
                ++temp;
                list::transfer(first1, first2, temp);
                first2 = temp;
                ++pair_.value;
                --other.pair_.value;
            }
        }
 
        if (first2 != last2) {
            size_type n = other.pair_.value;
            list::transfer(last1, first2, last2);
            pair_.value += n;
            other.pair_.value = 0;
        }
    }

    void merge(list& other) { list::merge_if(other, _NEFORCE less<T>()); }

    void reverse() noexcept {
        if (empty()) {
            return;
        }
        link_type current = head_;
        do {
            _NEFORCE swap(current->prev, current->next);
            current = current->prev;
        } while (current != head_);
    }

    template <typename Pred>
    void unique_if(Pred pred) noexcept {
        if (empty()) {
            return;
        }
        iterator current = begin();
        iterator next = current;
        while (++next != end()) {
            if (pred(*current, *next)) {
                list::erase(next);
                next = current;
            } else {
                current = next;
            }
        }
    }

    void unique() noexcept { list::unique_if(_NEFORCE equal_to<T>()); }

    template <typename Pred>
    void sort_if(Pred pred) {
        if (empty()) {
            return;
        }
        link_type p = head_->next->next;
        while (p != head_) {
            T temp = p->data;
            link_type prev = p->prev;
            while (prev != head_ && pred(temp, prev->data)) {
                prev->next->data = prev->data;
                prev = prev->prev;
            }
            prev->next->data = temp;
            p = p->next;
        }
    }

    void sort() { list::sort_if(_NEFORCE less<T>()); }

    NEFORCE_NODISCARD const_reference at(size_type position) const {
        const_iterator iter = cbegin();
        while (position--) {
            ++iter;
        }
        return iter.base()->data;
    }

    NEFORCE_NODISCARD reference at(size_type position) {
        const_iterator iter = cbegin();
        while (position--) {
            ++iter;
        }
        return iter.base()->data;
    }

    NEFORCE_NODISCARD const_reference operator[](const size_type position) const { return at(position); }

    NEFORCE_NODISCARD reference operator[](const size_type position) { return at(position); }

    NEFORCE_NODISCARD bool operator==(const list& rhs) const
            noexcept(noexcept(_NEFORCE equal(cbegin(), cend(), rhs.cbegin()))) {
        return size() == rhs.size() && _NEFORCE equal(cbegin(), cend(), rhs.cbegin());
    }

    NEFORCE_NODISCARD bool operator<(const list& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend()))) {
        return _NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend());
    }
};
 
#ifdef NEFORCE_STANDARD_17
template <typename Iterator, typename Alloc>
list(Iterator, Iterator, Alloc = Alloc()) -> list<iter_value_t<Iterator>, Alloc>;
#endif
 // Container
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_LIST_HPP__