#ifndef __GBLIBCPP_VECTOR__ #define __GBLIBCPP_VECTOR__ #include #include #include #include #include #include namespace std { template > class vector { public: using value_type = T; using allocator_type = Allocator; using size_type = std::size_t; using difference_type = std::ptrdiff_t; using reference = T&; using const_reference = const T&; template class _iterator { public: // TODO: // using iterator_category = std::random_access_iterator_tag; using value_type = std::conditional_t; using difference_type = std::ptrdiff_t; using pointer = std::add_pointer_t; using reference = std::add_lvalue_reference_t; private: T* m_ptr; public: constexpr _iterator(void) noexcept : m_ptr() {} constexpr explicit _iterator(const T* ptr) noexcept : m_ptr(const_cast(ptr)) {} constexpr _iterator(const _iterator& other) noexcept = default; constexpr _iterator(_iterator&& other) noexcept = default; constexpr _iterator& operator=(const _iterator& other) noexcept = default; constexpr _iterator& operator=(_iterator&& other) noexcept = default; constexpr bool operator==(const _iterator& other) const noexcept = default; constexpr reference operator*() const noexcept { return *m_ptr; } constexpr pointer operator&() const noexcept { return std::addressof(this->operator*()); } constexpr pointer operator->() const noexcept { return this->operator&(); } constexpr _iterator& operator++() noexcept { ++m_ptr; return *this; } constexpr _iterator operator++(int) noexcept { _iterator ret(m_ptr); (void)this->operator++(); return ret; } constexpr _iterator& operator--(void) noexcept { --m_ptr; return *this; } constexpr _iterator operator--(int) noexcept { _iterator ret(m_ptr); (void)this->operator--(); return ret; } constexpr _iterator& operator+=(difference_type n) noexcept { m_ptr += n; return *this; } constexpr _iterator& operator-=(difference_type n) noexcept { m_ptr -= n; return *this; } constexpr _iterator operator+(difference_type n) const noexcept { return _iterator { m_ptr + n }; } constexpr _iterator operator-(difference_type n) const noexcept { return _iterator { m_ptr - n }; } constexpr difference_type operator-(const _iterator& other) const noexcept { return m_ptr - other.m_ptr; } constexpr reference operator[](difference_type n) const noexcept { return m_ptr[n]; } constexpr operator bool() { return m_ptr; } constexpr operator _iterator() { return _iterator { m_ptr }; } constexpr operator _iterator() { return _iterator { m_ptr }; } constexpr operator const T*() { return m_ptr; } }; private: using alloc_traits = std::allocator_traits; public: using pointer = typename alloc_traits::pointer; using const_pointer = typename alloc_traits::const_pointer; using iterator = _iterator; using const_iterator = _iterator; private: impl::compressed_pair m_data; size_type m_size; size_type m_capacity; private: constexpr allocator_type& _alloc() noexcept { return m_data.second(); } constexpr const allocator_type& _alloc() const noexcept { return m_data.second(); } constexpr T*& _data() noexcept { return m_data.first(); } constexpr T* const& _data() const noexcept { return m_data.first(); } // assert(n >= m_size) constexpr void _reallocate_safe(size_type n) { T* newptr = nullptr; if (n) newptr = alloc_traits::allocate(_alloc(), n); for (size_t i = 0; i < m_size; ++i) { if (n) alloc_traits::construct(_alloc(), newptr + i, std::move(_data()[i])); alloc_traits::destroy(_alloc(), _data() + i); } alloc_traits::deallocate(_alloc(), _data(), m_capacity); _data() = newptr; m_capacity = n; } // make m_capacity >= n >= m_size constexpr void _pre_resize(size_type n) { while (n < m_size) pop_back(); reserve(n); } public: constexpr vector(void) noexcept(noexcept(Allocator())) : m_data{impl::default_construct_t{}}, m_size(), m_capacity() {} constexpr explicit vector(const Allocator& alloc) noexcept : m_data{nullptr, alloc}, m_size(), m_capacity() {} constexpr vector(size_type n, const T& val, const Allocator& alloc = Allocator()) : vector(alloc) { resize(n, val); } constexpr explicit vector(size_type n, const Allocator& alloc = Allocator()) : vector(alloc) { resize(n); } // TODO: check whether InputIter satisfies LegacyInputIterator template constexpr vector(InputIter first, InputIter last, const Allocator& alloc = Allocator()) : vector(alloc) { insert(cbegin(), first, last); } constexpr vector(const vector& other) : vector(std::allocator_traits:: select_on_container_copy_construction(other._alloc())) { insert(cbegin(), other.begin(), other.end()); } constexpr vector(const vector& other, const Allocator& alloc) : vector(alloc) { insert(cbegin(), other.begin(), other.end()); } constexpr vector(vector&& other) noexcept : m_data{std::exchange(other._data(), nullptr), std::move(other._alloc())} , m_size(std::exchange(other.m_size, 0)) , m_capacity(std::exchange(other.m_capacity, 0)) { } constexpr vector(vector&& other, const Allocator& alloc) : vector(alloc) { if (alloc == other._alloc()) { _data() = std::exchange(other._data(), nullptr); m_size = std::exchange(other.m_size, 0); m_capacity = std::exchange(other.m_capacity, 0); } else { // TODO: std::move_iterator // insert(cbegin(), std::make_move_iterator(other.begin()), // std::make_move_iterator(other.end())); for (auto& item : other) emplace_back(std::move(item)); } } constexpr vector(std::initializer_list init, const Allocator& alloc = Allocator()) : vector(alloc) { insert(cbegin(), init.begin(), init.end()); } constexpr ~vector() { resize(0); shrink_to_fit(); } constexpr vector& operator=(const vector& other) { clear(); if constexpr (alloc_traits:: propagate_on_container_copy_assignment::value) { if (_alloc() != other._alloc()) shrink_to_fit(); _alloc() = other._alloc(); } insert(cbegin(), other.begin(), other.end()); return *this; } constexpr vector& operator=(vector&& other) { clear(); if constexpr (alloc_traits:: propagate_on_container_move_assignment::value) { shrink_to_fit(); _alloc() = std::move(other._alloc()); } else { if (_alloc() != other._alloc()) { // TODO: std::move_iterator for (auto& item : other) emplace_back(std::move(item)); return *this; } shrink_to_fit(); } _data() = std::exchange(other._data(), nullptr); m_size = std::exchange(other.m_size, 0); m_capacity = std::exchange(other.m_capacity, 0); return *this; } constexpr vector& operator=(std::initializer_list init) { assign(init.begin(), init.end()); return *this; } constexpr void assign(size_type n, const T& val) { clear(); resize(n, val); } // TODO: check whether InputIter satisfies LegacyInputIterator template constexpr void assign(InputIter first, InputIter last) { clear(); insert(cbegin(), first, last); } constexpr void assign(std::initializer_list init) { clear(); insert(cbegin(), init.begin(), init.end()); } constexpr allocator_type get_allocator(void) const noexcept { return _alloc(); } constexpr reference at(size_type pos) { // TODO: exceptions // if (pos >= sz) // throw std::out_of_range("vector::at"); return _data()[pos]; } constexpr const_reference at(size_type pos) const { // TODO: exceptions // if (pos >= sz) // throw std::out_of_range("vector::at"); return _data()[pos]; } constexpr reference operator[](size_type pos) noexcept { return _data()[pos]; } constexpr const_reference operator[](size_type pos) const noexcept { return _data()[pos]; } constexpr reference front() noexcept { return _data()[0]; } constexpr const_reference front() const noexcept { return _data()[0]; } constexpr reference back() noexcept { return _data()[m_size - 1]; } constexpr const_reference back() const noexcept { return _data()[m_size - 1]; } constexpr T* data(void) noexcept { return _data(); } constexpr const T* data(void) const noexcept { return _data(); } // TODO: std::reverse_iterator constexpr iterator begin() noexcept { return iterator { _data() }; } constexpr const_iterator begin() const noexcept { return const_iterator { _data() }; } constexpr const_iterator cbegin() const noexcept { return const_iterator { _data() }; } constexpr iterator end() noexcept { return iterator { _data() + m_size }; } constexpr const_iterator end() const noexcept { return const_iterator { _data() + m_size }; } constexpr const_iterator cend() const noexcept { return const_iterator { _data() + m_size }; } [[nodiscard]] constexpr bool empty() const noexcept { return m_size == 0; } constexpr size_type size() const noexcept { return m_size; } constexpr size_type capacity() const noexcept { return m_capacity; } constexpr void reserve(size_type new_cap) { if (new_cap > m_capacity) _reallocate_safe(new_cap); } constexpr void resize(size_type n) { _pre_resize(n); while (n > m_size) emplace_back(); } constexpr void resize(size_type n, const value_type& value) { _pre_resize(n); while (n > m_size) emplace_back(value); } constexpr void shrink_to_fit() { if (m_size < m_capacity) _reallocate_safe(m_size); } constexpr void clear() noexcept { resize(0); } template constexpr iterator emplace(const_iterator pos, Args&&... args) { size_type idx = pos - _data(); if (!_data()) reserve(1); if (m_size == m_capacity) reserve(m_capacity * 2); for (size_type i = m_size; i > idx; --i) alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-1])); alloc_traits::construct(_alloc(), _data() + idx, std::forward(args)...); ++m_size; return iterator { _data() + idx }; } constexpr iterator insert(const_iterator pos, T&& val) { return emplace(pos, std::move(val)); } constexpr iterator insert(const_iterator pos, const T& val) { return emplace(pos, val); } constexpr iterator insert(const_iterator pos, size_type n, const T& val) { if (!n) return pos; size_type idx = pos - _data(); if (!pos) reserve(n); if (m_size + n > m_capacity) reserve(m_size + n); for (size_type i = m_size + n - 1; i >= idx + n; --i) alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-n])); for (size_type i = idx; i < idx + n; ++i) alloc_traits::construct(_alloc(), _data() + i, val); m_size += n; return iterator { _data() + idx }; } // TODO: LegacyInputIterator version of this template constexpr iterator insert(const_iterator pos, ForwardIter first, ForwardIter last) { size_type idx = pos - _data(); size_type n = 0; ForwardIter tmp = first; while (tmp != last) ++n, ++tmp; if (!n) return pos; if (!pos) reserve(n); if (m_size + n > m_capacity) reserve(m_size + n); for (size_type i = m_size + n - 1; i >= idx + n; --i) alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i-n])); for (size_type i = idx; i < idx + n; ++i) alloc_traits::construct(_alloc(), _data() + i, *first++); m_size += n; return iterator { _data() + idx }; } constexpr iterator insert(const_iterator pos, std::initializer_list init) { return insert(pos, init.begin(), init.end()); } constexpr iterator erase(const_iterator pos) { size_type idx = pos - _data(); alloc_traits::destroy(_alloc(), _data() + idx); for (size_type i = idx; i < m_size - 1; ++i) alloc_traits::construct(_alloc(), _data() + i, std::move(_data()[i+1])); --m_size; return iterator { _data() + idx }; } constexpr iterator erase(const_iterator first, const_iterator last) { size_type n = last - first; if (!n) return last; size_type idx = first - _data(); for (size_type i = idx; i < idx + n; ++i) alloc_traits::destroy(_alloc(), _data() + i); for (size_type i = idx; i < m_size - n; ++i) _alloc().construct(_data() + i, std::move(_data()[i+n])); m_size -= n; return iterator { _data() + idx }; } constexpr void push_back(const T& val) { insert(cend(), val); } constexpr void push_back(T&& val) { insert(cend(), std::move(val)); } template constexpr reference emplace_back(Args&&... args) { return *emplace(cend(), std::forward(args)...); } constexpr void pop_back() { erase(--cend()); } constexpr void swap(vector& other) noexcept( alloc_traits::propagate_on_container_swap::value || alloc_traits::is_always_equal::value) { if (alloc_traits::propagate_on_container_swap::value) std::swap(_alloc(), other.m_alloc); std::swap(_data(), other.m_data); std::swap(m_size, other.m_size); std::swap(m_capacity, other.m_capacity); } }; template constexpr void swap( std::vector& lhs, std::vector& rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } template constexpr typename std::vector::size_type erase(std::vector& vec, const U& value) { typename std::vector::size_type n = 0; for (auto iter = vec.begin(); iter != vec.end(); ) { if (*iter == value) { iter = vec.erase(iter); ++n; } else { ++iter; } } return n; } template constexpr typename std::vector::size_type erase_if(std::vector& vec, Pred pred) { typename std::vector::size_type n = 0; for (auto iter = vec.begin(); iter != vec.end(); ) { if (pred(*iter)) { iter = vec.erase(iter); ++n; } else { ++iter; } } return n; } } // namespace std #endif