sparse_vector.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_CONTAINER_SPARSE_VECTOR_HPP__
#define NEFORCE_CORE_CONTAINER_SPARSE_VECTOR_HPP__

 
#include "NeForce/core/algorithm/compare.hpp"
#include "NeForce/core/interface/icollector.hpp"
#include "NeForce/core/interface/iiterator.hpp"
#include "NeForce/core/memory/construct.hpp"
#include "NeForce/core/memory/standard_allocator.hpp"
#include "NeForce/core/utility/pair.hpp"
#include "NeForce/core/container/vector.hpp"
NEFORCE_BEGIN_NAMESPACE__


template <bool IsConst, typename SparseVector>
struct sparse_vector_iterator : iiterator<sparse_vector_iterator<IsConst, SparseVector>> {
public:
    using container_type = SparseVector;                              
    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 = random_access_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:
    const container_type* container_ = nullptr; 
    size_type index_ = 0;                       
 
    template <typename, typename, typename, typename, typename>
    friend class sparse_vector;
 
public:
    sparse_vector_iterator() noexcept = default;
    ~sparse_vector_iterator() = default;
 
    sparse_vector_iterator(const sparse_vector_iterator&) noexcept = default;
    sparse_vector_iterator& operator=(const sparse_vector_iterator&) noexcept = default;
    sparse_vector_iterator(sparse_vector_iterator&&) noexcept = default;
    sparse_vector_iterator& operator=(sparse_vector_iterator&&) noexcept = default;

    sparse_vector_iterator(size_type index, const container_type* container) noexcept :
    container_(container),
    index_(index) {}

    NEFORCE_NODISCARD reference dereference() const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "Attempting to dereference on null container");
        NEFORCE_DEBUG_VERIFY(index_ < container_->size(), "Attempting to dereference out of boundary");
        return const_cast<container_type*>(container_)->data_[index_];
    }

    NEFORCE_CONSTEXPR20 void increment() noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "Attempting to increment null container");
        NEFORCE_DEBUG_VERIFY(index_ <= container_->size(), "Attempting to increment out of boundary");
        ++index_;
    }

    NEFORCE_CONSTEXPR20 void decrement() noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "Attempting to decrement null container");
        NEFORCE_DEBUG_VERIFY(index_ > 0, "Attempting to decrement before begin");
        --index_;
    }

    void advance(difference_type n) noexcept {
        NEFORCE_DEBUG_VERIFY(container_ != nullptr, "Attempting to advance null container");
        index_ = static_cast<size_type>(static_cast<difference_type>(index_) + n);
    }

    NEFORCE_NODISCARD difference_type distance_to(const sparse_vector_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to distance different container");
        return static_cast<difference_type>(rhs.index_) - static_cast<difference_type>(index_);
    }

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

    NEFORCE_NODISCARD bool less_than(const sparse_vector_iterator& rhs) const noexcept {
        NEFORCE_DEBUG_VERIFY(container_ == rhs.container_, "Attempting to less than a different container");
        return index_ < rhs.index_;
    }

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

    NEFORCE_NODISCARD size_type index() const noexcept { return index_; }
};
 

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc = allocator<Value>>
class sparse_vector : icollector<sparse_vector<Key, Value, KeyOfValue, Compare, Alloc>> {
    static_assert(is_allocator_v<Alloc>, "Alloc type is not a standard allocator type.");
    static_assert(is_same_v<Value, typename Alloc::value_type>, "allocator type mismatch.");
    static_assert(is_object_v<Value>, "sparse_vector only contains object types.");
 
public:
    using key_type = Key; 
 
    using value_type = Value;             
    using pointer = Value*;               
    using reference = Value&;             
    using const_pointer = const Value*;   
    using const_reference = const Value&; 
    using size_type = size_t;             
    using difference_type = ptrdiff_t;    
    using compare_type = Compare;         
 
    using iterator = sparse_vector_iterator<false, sparse_vector>;            
    using const_iterator = sparse_vector_iterator<true, sparse_vector>;       
    using reverse_iterator = _NEFORCE reverse_iterator<iterator>;             
    using const_reverse_iterator = _NEFORCE reverse_iterator<const_iterator>; 
    using allocator_type = Alloc;                                             
 
private:
    using container_type = vector<Value, Alloc>; 
 
    container_type data_;    
    Compare key_compare_{};  
    KeyOfValue extracter_{}; 
 
    template <bool, typename>
    friend struct sparse_vector_iterator;

    NEFORCE_NODISCARD const Key& key_of(const value_type& value) const noexcept { return extracter_(value); }

    NEFORCE_NODISCARD size_type lower_bound_index(const key_type& key) const {
        size_type lo = 0;
        size_type hi = data_.size();
        while (lo < hi) {
            size_type mid = lo + (hi - lo) / 2;
            if (key_compare_(key_of(data_[mid]), key)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    NEFORCE_NODISCARD size_type upper_bound_index(const key_type& key) const {
        size_type lo = 0;
        size_type hi = data_.size();
        while (lo < hi) {
            size_type mid = lo + (hi - lo) / 2;
            if (key_compare_(key, key_of(data_[mid]))) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    iterator insert_at(size_type pos, value_type&& value) {
        data_.emplace(data_.begin() + static_cast<difference_type>(pos), _NEFORCE move(value));
        return iterator(pos, this);
    }

    iterator insert_at(size_type pos, const value_type& value) {
        data_.emplace(data_.begin() + static_cast<difference_type>(pos), value);
        return iterator(pos, this);
    }
 
public:
    sparse_vector() = default;

    explicit sparse_vector(const Compare& comp) :
    key_compare_(comp) {}

    sparse_vector(const sparse_vector& other) :
    data_(other.data_),
    key_compare_(other.key_compare_),
    extracter_(other.extracter_) {}

    sparse_vector& operator=(const sparse_vector& other) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        data_ = other.data_;
        key_compare_ = other.key_compare_;
        extracter_ = other.extracter_;
        return *this;
    }

    sparse_vector(sparse_vector&& other) noexcept(is_nothrow_move_constructible_v<container_type> &&
                                                  is_nothrow_move_constructible_v<Compare> &&
                                                  is_nothrow_move_constructible_v<KeyOfValue>) :
    data_(_NEFORCE move(other.data_)),
    key_compare_(_NEFORCE move(other.key_compare_)),
    extracter_(_NEFORCE move(other.extracter_)) {}

    sparse_vector& operator=(sparse_vector&& other) noexcept(is_nothrow_move_assignable_v<container_type>) {
        if (_NEFORCE addressof(other) == this) {
            return *this;
        }
        data_ = _NEFORCE move(other.data_);
        key_compare_ = _NEFORCE move(other.key_compare_);
        extracter_ = _NEFORCE move(other.extracter_);
        return *this;
    }

    ~sparse_vector() = default;

    NEFORCE_NODISCARD iterator begin() noexcept { return iterator(0, this); }

    NEFORCE_NODISCARD iterator end() noexcept { return iterator(data_.size(), this); }

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

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

    NEFORCE_NODISCARD const_iterator cbegin() const noexcept { return const_iterator(0, this); }

    NEFORCE_NODISCARD const_iterator cend() const noexcept { return const_iterator(data_.size(), this); }

    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_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 data_.size(); }

    NEFORCE_NODISCARD size_type max_size() const noexcept { return data_.max_size(); }

    NEFORCE_NODISCARD bool empty() const noexcept { return data_.empty(); }

    NEFORCE_NODISCARD Compare key_compare() const noexcept(is_nothrow_copy_constructible_v<Compare>) {
        return key_compare_;
    }

    template <typename... Args>
    pair<iterator, bool> emplace_unique(Args&&... args) {
        value_type tmp(_NEFORCE forward<Args>(args)...);
        size_type pos = lower_bound_index(key_of(tmp));
        if (pos < data_.size() && !key_compare_(key_of(tmp), key_of(data_[pos]))) {
            return pair<iterator, bool>(iterator(pos, this), false);
        }
        return pair<iterator, bool>(insert_at(pos, _NEFORCE move(tmp)), true);
    }

    pair<iterator, bool> insert_unique(const value_type& value) { return emplace_unique(value); }

    pair<iterator, bool> insert_unique(value_type&& value) { return emplace_unique(_NEFORCE move(value)); }

    template <typename... Args>
    iterator emplace_unique_hint(iterator position, Args&&... args) {
        value_type tmp(_NEFORCE forward<Args>(args)...);
        const key_type& k = key_of(tmp);
 
        if (position != end() && position != begin()) {
            iterator before = position;
            --before;
            if (key_compare_(key_of(*before), k) && key_compare_(k, key_of(*position))) {
                return insert_at(position.index(), _NEFORCE move(tmp));
            }
        }
        if (position == begin() && !data_.empty()) {
            if (key_compare_(k, key_of(data_.front()))) {
                return insert_at(0, _NEFORCE move(tmp));
            }
            if (!key_compare_(key_of(data_.front()), k)) {
                return iterator(0, this);
            }
        }
        if (position == end() && !data_.empty()) {
            if (key_compare_(key_of(data_.back()), k)) {
                return insert_at(data_.size(), _NEFORCE move(tmp));
            }
            if (!key_compare_(k, key_of(data_.back()))) {
                return iterator(data_.size() - 1, this);
            }
        }
 
        return emplace_unique(_NEFORCE move(tmp)).first;
    }

    iterator insert_unique(iterator position, const value_type& value) { return emplace_unique_hint(position, value); }

    iterator insert_unique(iterator position, value_type&& value) {
        return emplace_unique_hint(position, _NEFORCE move(value));
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void insert_unique(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            insert_unique(*first);
        }
    }

    template <typename... Args>
    iterator emplace_equal(Args&&... args) {
        value_type tmp(_NEFORCE forward<Args>(args)...);
        size_type pos = upper_bound_index(key_of(tmp));
        return insert_at(pos, _NEFORCE move(tmp));
    }

    iterator insert_equal(const value_type& value) { return emplace_equal(value); }

    iterator insert_equal(value_type&& value) { return emplace_equal(_NEFORCE move(value)); }

    template <typename... Args>
    iterator emplace_equal_hint(iterator position, Args&&... args) {
        value_type tmp(_NEFORCE forward<Args>(args)...);
        const key_type& k = key_of(tmp);
 
        if (position != end() && position != begin()) {
            iterator before = position;
            --before;
            if (key_compare_(key_of(*before), k) && key_compare_(k, key_of(*position))) {
                return insert_at(position.index(), _NEFORCE move(tmp));
            }
        }
        if (position == begin() && !data_.empty()) {
            if (key_compare_(k, key_of(data_.front()))) {
                return insert_at(0, _NEFORCE move(tmp));
            }
        }
        if (position == end() && !data_.empty()) {
            if (!key_compare_(k, key_of(data_.back()))) {
                return insert_at(data_.size(), _NEFORCE move(tmp));
            }
        }
 
        return emplace_equal(_NEFORCE move(tmp));
    }

    iterator insert_equal(iterator position, const value_type& value) { return emplace_equal_hint(position, value); }

    iterator insert_equal(iterator position, value_type&& value) {
        return emplace_equal_hint(position, _NEFORCE move(value));
    }

    template <typename Iterator, enable_if_t<is_iter_v<Iterator>, int> = 0>
    void insert_equal(Iterator first, Iterator last) {
        for (; first != last; ++first) {
            insert_equal(*first);
        }
    }

    size_type erase(const key_type& key) {
        size_type lo = lower_bound_index(key);
        size_type hi = upper_bound_index(key);
        size_type n = hi - lo;
        if (n > 0) {
            data_.erase(data_.begin() + static_cast<difference_type>(lo),
                        data_.begin() + static_cast<difference_type>(hi));
        }
        return n;
    }

    void erase(iterator position) {
        NEFORCE_DEBUG_VERIFY(position.container() == this, "Attempting to erase from different container");
        NEFORCE_DEBUG_VERIFY(position.index() < data_.size(), "Attempting to erase out of boundary");
        data_.erase(data_.begin() + static_cast<difference_type>(position.index()));
    }

    void erase(iterator first, iterator last) {
        NEFORCE_DEBUG_VERIFY(first.container() == this && last.container() == this,
                             "Attempting to erase from different container");
        if (first == begin() && last == end()) {
            clear();
        } else {
            data_.erase(data_.begin() + static_cast<difference_type>(first.index()),
                        data_.begin() + static_cast<difference_type>(last.index()));
        }
    }

    void clear() { data_.clear(); }

    NEFORCE_NODISCARD iterator find(const key_type& key) {
        size_type pos = lower_bound_index(key);
        if (pos < data_.size() && !key_compare_(key, key_of(data_[pos]))) {
            return iterator(pos, this);
        }
        return end();
    }

    NEFORCE_NODISCARD const_iterator find(const key_type& key) const {
        size_type pos = lower_bound_index(key);
        if (pos < data_.size() && !key_compare_(key, key_of(data_[pos]))) {
            return const_iterator(pos, this);
        }
        return cend();
    }

    NEFORCE_NODISCARD size_type count(const key_type& key) const {
        return upper_bound_index(key) - lower_bound_index(key);
    }

    NEFORCE_NODISCARD iterator lower_bound(const key_type& key) { return iterator(lower_bound_index(key), this); }

    NEFORCE_NODISCARD const_iterator lower_bound(const key_type& key) const {
        return const_iterator(lower_bound_index(key), this);
    }

    NEFORCE_NODISCARD iterator upper_bound(const key_type& key) { return iterator(upper_bound_index(key), this); }

    NEFORCE_NODISCARD const_iterator upper_bound(const key_type& key) const {
        return const_iterator(upper_bound_index(key), this);
    }

    NEFORCE_NODISCARD pair<iterator, iterator> equal_range(const key_type& key) {
        return pair<iterator, iterator>(lower_bound(key), upper_bound(key));
    }

    NEFORCE_NODISCARD pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
        return pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
    }

    void reserve(size_type n) { data_.reserve(n); }

    NEFORCE_NODISCARD size_type capacity() const noexcept { return data_.capacity(); }

    void shrink_to_fit() { data_.shrink_to_fit(); }

    void swap(sparse_vector& other) noexcept(is_nothrow_swappable_v<container_type> &&
                                             is_nothrow_swappable_v<Compare> && is_nothrow_swappable_v<KeyOfValue>) {
        data_.swap(other.data_);
        _NEFORCE swap(key_compare_, other.key_compare_);
        _NEFORCE swap(extracter_, other.extracter_);
    }

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

    NEFORCE_NODISCARD bool less_than(const sparse_vector& rhs) const
            noexcept(noexcept(_NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend()))) {
        return _NEFORCE lexicographical_compare(cbegin(), cend(), rhs.cbegin(), rhs.cend());
    }
};
 // SparseVector
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_CONTAINER_SPARSE_VECTOR_HPP__