401 lines
14 KiB
C++
401 lines
14 KiB
C++
/**
|
|
This file is a part of rexy's general purpose library
|
|
Copyright (C) 2022 rexy712
|
|
|
|
This program is free software: you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation, either version 3 of the License, or
|
|
(at your option) any later version.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#ifndef REXY_LLIST_HPP
|
|
#define REXY_LLIST_HPP
|
|
|
|
#include <cstddef> //size_t, ptrdiff_t
|
|
#include "allocator.hpp"
|
|
#include "detail/hasallocator.hpp"
|
|
#include "traits.hpp"
|
|
#include <iterator> //bidirectional_iterator_tag, reverse_iterator
|
|
#include <memory> //allocator_traits
|
|
#include <initializer_list>
|
|
#include <utility> //pair
|
|
#include <type_traits>
|
|
|
|
namespace rexy{
|
|
|
|
template<class T, class Alloc>
|
|
class list;
|
|
|
|
namespace detail{
|
|
struct list_node_base{
|
|
list_node_base* next = nullptr;
|
|
list_node_base* prev = nullptr;
|
|
};
|
|
|
|
template<class T>
|
|
struct list_iterator;
|
|
template<class T>
|
|
struct const_list_iterator;
|
|
template<class T>
|
|
struct list_node;
|
|
}
|
|
|
|
template<class T, class Alloc = rexy::allocator<T>>
|
|
class list : protected detail::hasallocator<typename std::allocator_traits<Alloc>::template rebind_alloc<detail::list_node<T>>>
|
|
{
|
|
private:
|
|
using node_allocator_type = detail::hasallocator<typename std::allocator_traits<Alloc>::template rebind_alloc<detail::list_node<T>>>;
|
|
|
|
public:
|
|
using value_type = T;
|
|
using allocator_type = Alloc;
|
|
using size_type = std::size_t;
|
|
using difference_type = std::ptrdiff_t;
|
|
using reference = value_type&;
|
|
using const_reference = const value_type&;
|
|
using pointer = value_type*;
|
|
using const_pointer = const value_type*;
|
|
using iterator = detail::list_iterator<T>;
|
|
using const_iterator = detail::const_list_iterator<T>;
|
|
using reverse_iterator = std::reverse_iterator<iterator>;
|
|
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
|
|
|
|
public:
|
|
using node = detail::list_node<T>;
|
|
|
|
private:
|
|
detail::list_node_base m_sentinel = {&m_sentinel, &m_sentinel};
|
|
size_type m_size = 0;
|
|
|
|
public:
|
|
constexpr list(void)noexcept = default;
|
|
|
|
constexpr explicit list(const allocator_type& alloc)noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list(size_type count, const_reference value = value_type(), const allocator_type& = allocator_type())noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
explicit list(size_type count, const allocator_type& alloc = allocator_type())noexcept(
|
|
std::is_nothrow_default_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class InputIt>
|
|
REXY_CPP20_CONSTEXPR
|
|
list(InputIt first, InputIt last, const allocator_type& alloc = allocator_type())noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list(const list& other, const allocator_type& alloc = allocator_type())noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list(list&& other, const allocator_type& alloc = allocator_type())noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list(std::initializer_list<value_type> l, const allocator_type& alloc = allocator_type())noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
~list(void)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list& operator=(const list& other)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list& operator=(list&& other)noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
list& operator=(std::initializer_list<value_type> l)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
constexpr bool operator==(const list& other)const noexcept;
|
|
#if __cpp_impl_three_way_comparison
|
|
constexpr auto operator<=>(const list& other)const noexcept;
|
|
#else
|
|
constexpr bool operator!=(const list& other)const noexcept;
|
|
constexpr bool operator<(const list& other)const noexcept;
|
|
constexpr bool operator<=(const list& other)const noexcept;
|
|
constexpr bool operator>(const list& other)const noexcept;
|
|
constexpr bool operator>=(const list& other)const noexcept;
|
|
#endif
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void assign(size_type count, const_reference value)noexcept(
|
|
std::conditional_t<
|
|
std::is_copy_assignable_v<value_type>,
|
|
std::is_nothrow_copy_assignable<value_type>,
|
|
std::true_type>::value &&
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class InputIt>
|
|
REXY_CPP20_CONSTEXPR
|
|
void assign(InputIt first, InputIt last)noexcept(
|
|
std::conditional_t<
|
|
std::is_assignable_v<value_type, decltype(*first)>,
|
|
std::is_nothrow_assignable<value_type, decltype(*first)>,
|
|
std::true_type>::value &&
|
|
std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void assign(std::initializer_list<value_type> l)noexcept(
|
|
std::conditional_t<
|
|
std::is_assignable_v<value_type, decltype(*l.begin())>,
|
|
std::is_nothrow_assignable<value_type, decltype(*l.begin())>,
|
|
std::true_type>::value &&
|
|
std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
constexpr allocator_type get_allocator(void)const noexcept;
|
|
|
|
constexpr reference front(void)noexcept;
|
|
constexpr const_reference front(void)const noexcept;
|
|
constexpr reference back(void)noexcept;
|
|
constexpr const_reference back(void)const noexcept;
|
|
|
|
constexpr iterator begin(void)noexcept;
|
|
constexpr const_iterator begin(void)const noexcept;
|
|
constexpr const_iterator cbegin(void)const noexcept;
|
|
constexpr iterator end(void)noexcept;
|
|
constexpr const_iterator end(void)const noexcept;
|
|
constexpr const_iterator cend(void)const noexcept;
|
|
|
|
constexpr iterator next(iterator i)noexcept;
|
|
constexpr const_iterator next(const_iterator i)noexcept;
|
|
|
|
constexpr iterator prev(iterator i)noexcept;
|
|
constexpr const_iterator prev(const_iterator i)noexcept;
|
|
|
|
constexpr reverse_iterator rbegin(void)noexcept;
|
|
constexpr const_reverse_iterator rbegin(void)const noexcept;
|
|
constexpr const_reverse_iterator crbegin(void)const noexcept;
|
|
constexpr reverse_iterator rend(void)noexcept;
|
|
constexpr const_reverse_iterator rend(void)const noexcept;
|
|
constexpr const_reverse_iterator crend(void)const noexcept;
|
|
|
|
constexpr bool empty(void)const noexcept;
|
|
constexpr size_type size(void)const noexcept;
|
|
constexpr size_type max_size(void)const noexcept;
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void clear(void)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator insert(const_iterator pos, const_reference value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator insert(const_iterator pos, value_type&& value)noexcept(
|
|
std::is_nothrow_move_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator insert(const_iterator pos, size_type count, const_reference value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class InputIt>
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator insert(const_iterator pos, InputIt first, InputIt last)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator insert(const_iterator pos, std::initializer_list<value_type> l)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*l.begin())> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class... Args>
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator emplace(const_iterator pos, Args&&... args)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, Args&&...> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator erase(const_iterator pos)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
iterator erase(const_iterator first, const_iterator last)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
reference push_back(const_reference value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
reference push_back(value_type&& value)noexcept(
|
|
std::is_nothrow_move_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class... Args>
|
|
REXY_CPP20_CONSTEXPR
|
|
reference emplace_back(Args&&... args)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, Args&&...> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void pop_back(void)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
reference push_front(const_reference value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
reference push_front(value_type&& value)noexcept(
|
|
std::is_nothrow_move_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class... Args>
|
|
REXY_CPP20_CONSTEXPR
|
|
reference emplace_front(Args&&... args)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, Args&&...> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void pop_front(void)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void resize(size_type count)noexcept(
|
|
std::is_nothrow_default_constructible_v<value_type> &&
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void resize(size_type count, value_type value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void swap(list& other)noexcept;
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void merge(list&& other)noexcept;
|
|
template<class Comp>
|
|
REXY_CPP20_CONSTEXPR
|
|
void merge(list&& other, Comp comp)noexcept;
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void splice(const_iterator pos, list&& other)noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void splice(const_iterator pos, list&& other, const_iterator it)noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void splice(const_iterator pos, list&& other, const_iterator first, const_iterator last)noexcept;
|
|
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
size_type remove(const_reference value)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class UnaryPred>
|
|
REXY_CPP20_CONSTEXPR
|
|
size_type remove_if(UnaryPred p)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void reverse(void)noexcept;
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
size_type unique(void)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class BinaryPred>
|
|
REXY_CPP20_CONSTEXPR
|
|
size_type unique(BinaryPred p)noexcept(
|
|
std::is_nothrow_destructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void sort(void)noexcept;
|
|
|
|
template<class Comp>
|
|
REXY_CPP20_CONSTEXPR
|
|
void sort(Comp comp)noexcept;
|
|
|
|
|
|
private:
|
|
|
|
template<class InputIt>
|
|
REXY_CPP20_CONSTEXPR
|
|
void iterator_initialize_(InputIt first, InputIt last)noexcept(
|
|
std::is_nothrow_constructible_v<value_type, decltype(*first)> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void constant_initialize_(size_type count, const_reference value)noexcept(
|
|
std::is_nothrow_copy_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
REXY_CPP20_CONSTEXPR
|
|
void default_initialize_(size_type count)noexcept(
|
|
std::is_nothrow_default_constructible_v<value_type> &&
|
|
is_nothrow_allocator_v<node_allocator_type>);
|
|
|
|
template<class Comp>
|
|
static iterator mergesort(iterator first, size_type firstlen, Comp comp)noexcept;
|
|
static std::pair<iterator,size_type> ms_split(iterator it, size_type len)noexcept;
|
|
|
|
static void insert_node_(detail::list_node_base* prev, detail::list_node_base* n)noexcept;
|
|
static void remove_node_(detail::list_node_base* rm)noexcept;
|
|
static detail::list_node_base* get_next_then_move_node_(detail::list_node_base* dest, detail::list_node_base* n)noexcept;
|
|
};
|
|
|
|
}
|
|
|
|
#include "list.tpp"
|
|
|
|
#endif
|