ne_stl_continuous_container.h

浏览该文件的文档.

#ifndef NE_STL_INCLUDENE_STL_CONTINUOUS_CONTAINER_
#define NE_STL_INCLUDENE_STL_CONTINUOUS_CONTAINER_
#include <algorithm>
#include <stdexcept>
#include <vector>
#include "ne_stl_build.h"
#include "ne_stl_iterator.h"
#include "ne_stl_memory.h"
 
namespace nstd {
 
template <class TElement,
    element_malloc_fun_t<TElement> _malloc = memory::safe_malloc_container_element<TElement>,
    element_delete_fun_t<TElement> _delete = memory::safe_delete_container_element<TElement>>
class _continuous_container {
public:
    using size_type = std::size_t;
    using value_type = TElement;
    using pointer = TElement*;
 
public:
    _continuous_container()
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        static_assert(std::is_standard_layout<TElement>::value, "TElement should standard layout");
        _set_capacity(0);
        _set_length(0);
    }
    _continuous_container(const _continuous_container& other)
        : data_(nullptr)
        , malloc_fun_(other.malloc_fun_)
        , delete_fun_(other.delete_fun_)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        static_assert(std::is_standard_layout<TElement>::value, "TElement should standard layout");
        _append(other.data_, other.length_);
    }
    _continuous_container(_continuous_container&& other) {
        data_ = other.data_;
        malloc_fun_ = other.malloc_fun_;
        delete_fun_ = other.delete_fun_;
        length_ = other.length_;
        cap_length_ = other.cap_length_;
        increase_step_length_ = other.increase_step_length_;
        other.data_ = nullptr;
        other.malloc_fun_ = nullptr;  // not set to _malloc because the implementation may be different across modules
        other.delete_fun_ = nullptr;  // same as above
        other.length_ = 0;
        other.cap_length_ = 0;
        other.increase_step_length_ = container_increase_step::value;
    }
    _continuous_container(const _continuous_container& other, std::size_t pos, std::size_t len = container_npos::value)
        : data_(nullptr)
        , malloc_fun_(other.malloc_fun_)
        , delete_fun_(other.delete_fun_)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        static_assert(std::is_standard_layout<TElement>::value, "TElement should standard layout");
        append(other.data_, pos, len);
    }
    _continuous_container(const TElement* s, std::size_t n)
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        static_assert(std::is_standard_layout<TElement>::value, "TElement should standard layout");
        _append(n, s);
    }
    _continuous_container(std::size_t n, const TElement& s) { append(n, s); }
    _continuous_container(const nstd::const_iterator<TElement> first, const nstd::const_iterator<TElement> second)
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        static_assert(std::is_standard_layout<TElement>::value, "TElement should standard layout");
        append(first, second);
    }
    template <typename T>
    _continuous_container(const std::vector<T>& other)
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        for (auto it : other) {
            this->push_back(it);
        }
    }
    _continuous_container(const std::vector<TElement>& other)
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        for (auto it : other) {
            this->push_back(it);
        }
    }
    _continuous_container(std::initializer_list<TElement> init)
        : data_(nullptr)
        , malloc_fun_(_malloc)
        , delete_fun_(_delete)
        , length_(0)
        , cap_length_(0)
        , increase_step_length_(container_increase_step::value) {
        for (auto it : init) {
            this->push_back(it);
        }
    }
 
public:
    nstd::iterator<TElement> begin() { return _ibegin(); }
    nstd::const_iterator<TElement> begin() const { return _ibegin(); }
    nstd::iterator<TElement> end() { return _end(); }
    nstd::const_iterator<TElement> end() const { return _end(); }
    nstd::const_iterator<TElement> cbegin() const { return _ibegin(); }
    nstd::const_iterator<TElement> cend() const { return _end(); }
 
    nstd::reverse_iterator<TElement> rbegin() { return _rbegin(); }
    nstd::const_reverse_iterator<TElement> rbegin() const { return _rbegin(); }
    nstd::reverse_iterator<TElement> rend() { return _end(); }
    nstd::const_reverse_iterator<TElement> rend() const { return _end(); }
    nstd::const_reverse_iterator<TElement> crbegin() const { return _rbegin(); }
    nstd::const_reverse_iterator<TElement> crend() const { return _end(); }
 
    using iterator = nstd::iterator<TElement>;
    using reverse_iterator = nstd::reverse_iterator<TElement>;
    using const_iterator = nstd::const_iterator<TElement>;
 
private:
    inline nstd::iterator_type<TElement> _ibegin() const { return nstd::iterator_type<TElement>(data_, &length_, 0); }
    inline nstd::iterator_type<TElement> _rbegin() const { return nstd::iterator_type<TElement>(data_, &length_, length_ - 1); }
    inline nstd::iterator_type<TElement> _end() const { return nstd::iterator_type<TElement>(data_, &length_, length_); }
    std::size_t _getLength(const nstd::const_iterator<TElement> first, const nstd::const_iterator<TElement> second) {
        if (first.current().first_ != second.current().first_) {
            throw;
        }
        if (first.current().pos_ > second.current().pos_) {
            throw;
        }
        return second.current().pos_ - first.current().pos_;
    }
 
public:
    _continuous_container& operator=(const _continuous_container& other) {
        if (this != &other) {
            _set_length(0);
            _append(other.data_, other.length_);
        }
        return *this;
    }
    _continuous_container& operator=(_continuous_container&& other) {
        if (this != &other) {
            _delete_data(data_);
            data_ = other.data_;
            length_ = other.length_;
            cap_length_ = other.cap_length_;
            other.data_ = nullptr;
            other.length_ = 0;
            other.cap_length_ = 0;
        }
        return *this;
    }
 
    template <typename T>
    _continuous_container& operator=(const std::vector<T>& other) {
        _continuous_container templateContainer;
        for (auto it : other) {
            templateContainer.push_back(it);
        }
        *this = templateContainer;
        return *this;
    }
    operator std::vector<TElement>() {
        std::vector<TElement> ret;
        for (auto it : *this) {
            ret.emplace_back(it);
        }
        return ret;
    }
    operator std::vector<TElement>() const {
        std::vector<TElement> ret;
        for (auto it : *this) {
            ret.emplace_back(it);
        }
        return ret;
    }
    template <class TSTDVectorItem>
    operator std::vector<TSTDVectorItem>() {
        std::vector<TSTDVectorItem> ret;
        for (auto it : *this) {
            ret.emplace_back(it);
        }
        return ret;
    }
    template <class TSTDVectorItem>
    operator std::vector<TSTDVectorItem>() const {
        std::vector<TSTDVectorItem> ret;
        for (auto it : *this) {
            ret.emplace_back(it);
        }
        return ret;
    }
 
    std::string to_string() const {
        if (length_ == 0)
            return "";
        std::string ret;
        for (auto iter : *this) {
            ret += iter;
            ret += ',';
        }
        ret.pop_back();
        return ret;
    }
 
    bool element_equal(const _continuous_container& other) const {
        if (length_ != other.length_)
            return false;
        for (std::size_t index = 0; index < length_; ++index) {
            if (find(other[index]) == end()) {
                return false;
            }
        }
        return true;
    }
 
public:
    ~_continuous_container() {
        _delete_data(data_);
        length_ = 0;
        cap_length_ = 0;
        increase_step_length_ = container_increase_step::value;
    }
 
public:
    const TElement& operator[](std::size_t i) const { return *(data_ + i); }
    TElement& operator[](std::size_t i) { return *(data_ + i); }
    const TElement& at(std::size_t i) const {
        if (i < 0 || length_ <= i)
            throw;
        return operator[](i);
    }
    TElement& at(std::size_t i) {
        if (i < 0 || length_ <= i)
            throw;
        return operator[](i);
    }
    const TElement& front() const { return operator[](0); }
    TElement& front() { return operator[](0); }
    const TElement& back() const { return operator[](length_ - 1); }
    TElement& back() { return operator[](length_ - 1); }
 
public:
    _continuous_container& operator+=(const _continuous_container& other) {
        _append(other.data_, other.length_);
        return *this;
    }
    _continuous_container& operator+=(TElement element) {
        _append(&element, 1);
        return *this;
    }
    _continuous_container& append(const _continuous_container& other) {
        _append(other.data_, other.length_);
        return *this;
    }
    _continuous_container& append(const _continuous_container& other, std::size_t subpos, std::size_t sublen = container_npos::value) {
        sublen = _getLength(other, subpos, sublen);
        TElement* buffer = nullptr;
        _substr(buffer, other.data_, subpos, sublen);
        _append(buffer, sublen);
        _delete_data(buffer);
        return *this;
    }
    _continuous_container& append(const TElement elements) {
        _append(&elements, 1);
        return *this;
    }
    _continuous_container& append(std::size_t n, TElement element) {
        TElement* buffer = nullptr;
        _alloc_buffer(buffer, n, element);
        _append(buffer, n);
        _delete_data(buffer);
        return *this;
    }
    _continuous_container& append(const nstd::const_iterator<TElement> first, const nstd::const_iterator<TElement> second) {
        const std::size_t n = _getLength(first, second);
        if (n != 0) {
            TElement* buffer = nullptr;
            _alloc_buffer(buffer, n, first, second);
            _append(buffer, n);
            _delete_data(buffer);
        }
        return *this;
    }
    _continuous_container& push_back(TElement element) {
        _append(&element, 1);
        return *this;
    }
    _continuous_container& erase(std::size_t pos = 0, std::size_t len = container_npos::value) {
        _erase(pos, len);
        return *this;
    }
    nstd::iterator<TElement> erase(nstd::const_iterator<TElement> p) {
        _erase(p.current().pos_, 1);
        return p.current();
    }
    nstd::iterator<TElement> erase(nstd::const_iterator<TElement> first, nstd::const_iterator<TElement> last) {
        _erase(first.current().pos_, _getLength(first, last));
        return first.current();
    }
    void swap(_continuous_container& other) {
        _continuous_container temp = std::move(*this);
        *this = std::move(other);
        other = std::move(temp);
    }
    template <class InputIt>
    void insert(iterator pos, InputIt first, InputIt last) {
        if (pos != end()) {
            throw std::runtime_error("Only inserting to end is supported");
        }
        append(first, last);
    }
    void insert(const_iterator pos, const TElement& value) {
        if (pos != cend()) {
            throw std::runtime_error("Only inserting to end is supported");
        }
        append(value);
    }
 
    bool operator==(const _continuous_container& other) const { return std::equal(begin(), end(), other.begin(), other.end()); }
    bool operator!=(const _continuous_container& other) const { return !operator==(other); }
 
    nstd::iterator<TElement> find(const TElement& element) { return std::find(begin(), end(), element); }
    nstd::const_iterator<TElement> find(const TElement& element) const { return std::find(begin(), end(), element); }
    bool contains(const _continuous_container& other) const {
        if (other.length_ > length_) {
            return false;
        }
        return std::all_of(other.begin(), other.end(), [this](const TElement& element) {
            return find(element) != end();
        });
    }
 
private:
    inline void _append(const TElement other) { _append(&other, 1); }
    void _append(const TElement* other, std::size_t n) {
        if (!other || n == 0)
            return;
        _increase_capacity(length_ + n);
        for (std::size_t i = 0; i < n; ++i)
            operator[](length_ + i) = other[i];
        _set_length(length_ + n);
    }
    void _substr(TElement*& buffer, const TElement* other, std::size_t pos = 0, std::size_t len = container_npos::value) const {
        if (other == nullptr) {
            throw;
        }
        _alloc_buffer(buffer, len);
        for (std::size_t i = 0; i < len; ++i)
            buffer[i] = other[pos + i];
    }
    void _erase(std::size_t pos, std::size_t size) {
        size = _getLength(*this, pos, size);
        for (std::size_t i = pos + size; i < length_; ++i)
            operator[](i - size) = operator[](i);
        _clear_str(length_ - size);
    }
    std::size_t _getLength(const _continuous_container& str, std::size_t pos, std::size_t len = container_npos::value) const {
        if (len == container_npos::value)
            len = length_ - pos;
        if (pos + len > str.length_)
            throw;
        return len;
    }
 
public:
    const TElement* data() const { return data_; }
 
public:
    void set_element_malloc_function(element_malloc_fun_t<TElement> function) { malloc_fun_ = function; }
    void set_element_delete_function(element_delete_fun_t<TElement> function) { delete_fun_ = function; }
    inline std::size_t size() const { return length_; }
    std::size_t max_size() const { return container_npos::value - 1; }
    void resize(std::size_t n) {
        if (length_ == n)
            return;
        if (length_ < n) {
            _set_length(n);
            return;
        }
        _clear_str(n);
    }
    void resize(std::size_t n, TElement c) {
        if (length_ == n)
            return;
        if (length_ < n) {
            std::size_t pos = length_;
            _set_length(n);
            _fill_str(data_, length_, pos, c);
            return;
        }
        _clear_str(n);
    }
    std::size_t capacity() const { return cap_length_; }
    void reserve(std::size_t n = 0) {
        if (cap_length_ == n)
            return;
        if (cap_length_ < n) {
            _set_capacity(n);
            return;
        }
        if (cap_length_ / 2 > length_) {
            _decrease_capacity(cap_length_ / 2);
        }
    }
    void clear() {
        _clear_str(0, false);
        _delete_data(data_);
    }
    bool empty() const { return length_ ? false : true; }
    void shrink_to_fit() { _decrease_capacity(length_); }
 
private:
    void _set_length(const std::size_t len) {
        if (length_ > len)
            _clear_str(len);
        else if (cap_length_ < len)
            _increase_capacity(len);
        length_ = len;
    }
    void _set_capacity(const std::size_t cap) {
        if (cap_length_ == cap && data_)
            return;
        if (cap < length_)
            return;
        cap_length_ = cap;
        TElement* buffer = data_;
        data_ = nullptr;
        _alloc_buffer(data_, cap_length_);
        if (buffer) {
            for (std::size_t i = 0; i < length_; ++i)
                operator[](i) = buffer[i];
            _delete_data(buffer);
        }
    }
    void _increase_capacity(const std::size_t cap) {
        if (cap_length_ > cap && data_)
            return;
        std::size_t _cap = cap_length_;
        while (_cap <= cap)
            _cap += increase_step_length_;
        increase_step_length_++;
        _set_capacity(_cap);
    }
    void _decrease_capacity(const std::size_t cap) {
        if (cap_length_ < cap)
            return;
        if (increase_step_length_ > container_increase_step::value)
            --increase_step_length_;
        _set_capacity(cap);
    }
    void _alloc_buffer(TElement*& buffer, const std::size_t n) const {
        if (buffer != 0)
            throw;
        if (n > 0) {
            buffer = _new_data(n);
        }
    }
    void _alloc_buffer(TElement*& buffer, const std::size_t n, const TElement& element) const {
        _alloc_buffer(buffer, n);
        std::size_t begin = 0;
        while (begin != n)
            buffer[begin++] = element;
    }
 
    void _alloc_buffer(TElement*& buffer,
        const std::size_t n,
        const nstd::const_iterator<TElement> i1,
        const nstd::const_iterator<TElement> i2) const {
        _alloc_buffer(buffer, n);
        nstd::const_iterator<TElement> begin = i1;
        for (std::size_t i = 0; i < n; ++i)
            buffer[i] = *begin++;
    }
    void _clear_str(const std::size_t pos, bool destruct = true) {
        std::size_t begin = pos;
        TElement* begin_data = data_ + pos;
        while (begin++ != length_) {
            auto _temp = begin_data++;
            if (destruct) {
                _temp->~TElement();
            }
            // memset(_temp, 0, sizeof(TElement));
        }
        length_ = pos;
        // increase_step_length_ = container_increase_step::value;
    }
    TElement* _new_data(std::size_t count) const {
        if (count <= 0)
            return nullptr;
        if (malloc_fun_ != nullptr)
            return malloc_fun_(count);
        else
            return memory::safe_malloc_container_element<TElement>(count);
    }
    void _delete_data(TElement*& data) {
        if (data == nullptr)
            return;
        if (delete_fun_ != nullptr) {
            delete_fun_(data);
        } else {
            memory::safe_delete_container_element<TElement>(data);
        }
    }
 
private:
    TElement* data_{nullptr};
    element_malloc_fun_t<TElement> malloc_fun_{_malloc};
    element_delete_fun_t<TElement> delete_fun_{_delete};
    std::size_t length_{0};
    std::size_t cap_length_{0};
    std::size_t increase_step_length_{container_increase_step::value};
};
template <class TElement,
    element_malloc_fun_t<TElement> _malloc = memory::safe_malloc_container_element<TElement>,
    element_delete_fun_t<TElement> _delete = memory::safe_delete_container_element<TElement>>
using continuous_container = _continuous_container<TElement, _malloc, _delete>;
 
template <class TElement,
    element_malloc_fun_t<TElement> _malloc = memory::safe_malloc_container_element<TElement>,
    element_delete_fun_t<TElement> _delete = memory::safe_delete_container_element<TElement>>
using vector = continuous_container<TElement, _malloc, _delete>;
}  // namespace nstd
 
#endif  // !NE_STL_INCLUDENE_STL_CONTINUOUS_CONTAINER_