inferior vector util

contiguous_iterator.hpp

#ifndef INFERIOR_ITERATOR_CONTIGUOUS_ITERATOR_HPP_
#define INFERIOR_ITERATOR_CONTIGUOUS_ITERATOR_HPP_
#include <inferior/no_min_max.h>
#include <cstddef>
#include <iterator>
#include <inferior/type_traits.hpp>

namespace inferior {
    template<typename Container>
    class contiguous_iterator {
    private:
        using container_type = std::remove_reference_t<Container>;
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = typename container_type::value_type;
        using difference_type = typename container_type::difference_type;
        using pointer = std::conditional_t<std::is_const<container_type>::value, typename container_type::const_pointer, typename container_type::pointer>;
        using reference = std::conditional_t<std::is_const<container_type>::value, typename container_type::const_reference, typename container_type::reference>;
    private:
        pointer pointer_;
    public:
        contiguous_iterator() = delete;
        contiguous_iterator(const contiguous_iterator&) = default;
        contiguous_iterator(contiguous_iterator&&) = default;
        contiguous_iterator& operator=(const contiguous_iterator&) = default;
        contiguous_iterator& operator=(contiguous_iterator&&) = default;

        constexpr contiguous_iterator(pointer p) noexcept;
        template<typename Container2, enable_if_t<!std::is_const<std::remove_reference_t<Container2>>::value> = nullptr>
        constexpr contiguous_iterator(const contiguous_iterator<Container2>& o) noexcept;

        constexpr pointer ptr() const noexcept;
        constexpr contiguous_iterator next() const noexcept;
        constexpr contiguous_iterator prev() const noexcept;
        constexpr reference operator*() const noexcept;
        constexpr pointer operator->() const noexcept;
        constexpr contiguous_iterator& operator++() noexcept;
        constexpr contiguous_iterator operator++(int) noexcept;
        constexpr contiguous_iterator& operator--() noexcept;
        constexpr contiguous_iterator operator--(int) noexcept;
        constexpr contiguous_iterator operator+(difference_type n) const noexcept;
        constexpr contiguous_iterator operator-(difference_type n) const noexcept;
        constexpr contiguous_iterator& operator+=(difference_type n) noexcept;
        constexpr contiguous_iterator& operator-=(difference_type n) noexcept;
        constexpr reference operator[](difference_type n) const noexcept;
    };
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator==(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator!=(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator<(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator>(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator<=(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr bool operator>=(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept;
    template<
        typename Container1, typename Container2,
        enable_if_t<std::is_same<std::decay_t<Container1>, std::decay_t<Container2>>::value> = nullptr
    >
    inline constexpr auto operator-(const contiguous_iterator<Container1>& l, const contiguous_iterator<Container2>& r) noexcept -> decltype(l.ptr() - r.ptr());
    template<typename Container>
    inline constexpr contiguous_iterator<Container> operator+(typename contiguous_iterator<Container>::difference_type n, const contiguous_iterator<Container>& it) noexcept;
}

#include <inferior/iterator/contiguous_iterator_impl.hpp>

#endif //INFERIOR_ITERATOR_CONTIGUOUS_ITERATOR_HPP_

make_checked_array_iterator_when_msvc_or_passthrough.hpp

#ifndef INFERIOR_ITERATOR_MAKE_CHECKED_ARRAY_ITERATOR_WHEN_MSVC_OR_PASSTHROUGH_HPP_
#define INFERIOR_ITERATOR_MAKE_CHECKED_ARRAY_ITERATOR_WHEN_MSVC_OR_PASSTHROUGH_HPP_
#include <inferior/no_min_max.h>
#include <iterator>

namespace inferior {
#ifdef _MSC_VER
    template<typename Iterator>
    inline auto make_checked_array_iterator_when_msvc_or_passthrough(Iterator it, std::size_t size, std::size_t index = 0)
        -> stdext::checked_array_iterator<Iterator>
    {
        return { it, size, index };
    }
#else
    template<typename Iterator>
    inline Iterator make_checked_array_iterator_when_msvc_or_passthrough(Iterator it, std::size_t, std::size_t = 0)
    {
        return it;
    }
#endif
}
#endif //INFERIOR_ITERATOR_MAKE_CHECKED_ARRAY_ITERATOR_WHEN_MSVC_OR_PASSTHROUGH_HPP_

make_move_if_noexcept_iterator.hpp

#ifndef INFERIOR_ITERATOR_MAKE_MOVE_IF_NOEXCEPT_ITERATOR_HPP_
#define INFERIOR_ITERATOR_MAKE_MOVE_IF_NOEXCEPT_ITERATOR_HPP_
#include <inferior/no_min_max.h>
#include <iterator>
#include <type_traits>

namespace inferior {
	template<typename Iterator>
	using move_if_noexcept_iterator = std::conditional_t<
		!std::is_nothrow_move_constructible<
			typename Iterator::value_type
		>::value
		&& std::is_copy_constructible<
			typename Iterator::value_type
		>::value,
		Iterator,
		std::move_iterator<Iterator>
	>;
	template<typename Iterator>
	inline move_if_noexcept_iterator<Iterator> make_move_if_noexcept_iterator(Iterator i)
	{
		return move_if_noexcept_iterator<Iterator>(i);
	}
}

#endif //INFERIOR_ITERATOR_MAKE_MOVE_IF_NOEXCEPT_ITERATOR_HPP_

memory.hpp

#ifndef INFERIOR_MEMORY_HPP_
#define INFERIOR_MEMORY_HPP_
#include <inferior/no_min_max.h>
#include <memory>
#include <inferior/type_traits.hpp>
#include <inferior/iterator.hpp>

namespace inferior {
    template<class T>
    void destroy_at(T* p)
    {
        p->~T();
    }
    template<class ForwardIt, class Size>
    ForwardIt destroy_n( ForwardIt first, Size n )
    {
        for (; n > 0; (void) ++first, --n)
            destroy_at(std::addressof(*first));
        return first;
    }
    template< class ForwardIt >
    void destroy( ForwardIt first, ForwardIt last )
    {
        for (; first != last; ++first)
            destroy_at(std::addressof(*first));
    }
	template<typename Pointer, enable_if_t<std::is_pointer<Pointer>::value> = nullptr>
	void uninitialized_default_n_a(Pointer p, std::size_t sz)
	{
		using value_type = typename std::pointer_traits<Pointer>::element_type;
		//配置new
		for (std::size_t i = 0; i < sz; ++i) new (p + i) value_type();
		//new (this->finish_) value_type[sz]();//危険
	}
	template <
		typename InputIterator,
		typename ForwardIterator,
		enable_if_t<
			conjunction<
				is_input_iterator<InputIterator>,
				is_forward_iterator<ForwardIterator>
#ifdef _MSC_VER
				,negation<std::is_pointer<ForwardIterator>>
#endif
			>::value
		> = nullptr
	>
	ForwardIterator uninitialized_move_if_noexcept_or_copy(
		InputIterator first,
		InputIterator last,
		ForwardIterator result
	)
	{
		return std::uninitialized_copy(
			inferior::make_move_if_noexcept_iterator(first),
			inferior::make_move_if_noexcept_iterator(last),
			result
		);
	}
	template <
		typename InputIterator,
		typename Pointer,
		enable_if_t<
			conjunction<
				is_input_iterator<InputIterator>,
				std::is_pointer<Pointer>
			>::value
		> = nullptr
	>
	auto uninitialized_move_if_noexcept_or_copy(
		InputIterator first,
		InputIterator last,
		Pointer result,
		std::size_t result_size
	)
	{
		return uninitialized_move_if_noexcept_or_copy(
			first,
			last,
			inferior::make_checked_array_iterator_when_msvc_or_passthrough(result, result_size)
		);
	}
}

#endif //INFERIOR_MEMORY_HPP_

type_traits.hpp

#ifndef INFERIOR_TYPE_TRAITS_HPP_
#define INFERIOR_TYPE_TRAITS_HPP_
#include <inferior/no_min_max.h>
#include <type_traits>

namespace inferior {
    template<bool b>
    using enable_if_t = typename std::enable_if<b, std::nullptr_t>::type;
	template<bool b>
	using bool_constant = std::integral_constant<bool, b>;
	template<typename...> struct conjunction : std::true_type {};
	template<typename B1> struct conjunction<B1> : B1 {};
	template<typename B1, typename... Bn>
	struct conjunction<B1, Bn...>
		: std::conditional_t<bool(B1::value), conjunction<Bn...>, B1> {};
	template<typename B>
	struct negation : bool_constant<!bool(B::value)> {};
	template<typename...>
	using void_t = void;
	template<typename T, typename = void>
	struct is_iterator : std::false_type {};
	template<typename T>
	struct is_iterator<T, void_t<typename std::iterator_traits<T>::iterator_category>>
		: std::true_type
	{};
	template<typename Iterator, bool is_iterator = is_iterator<Iterator>::value>
	struct is_input_iterator : std::false_type {};
	template<typename Iterator>
	struct is_input_iterator<Iterator, true> : std::is_base_of<
		std::input_iterator_tag,
		typename std::iterator_traits<Iterator>::iterator_category
	> {};
	template<typename InputIter>
	using require_input_iterator = enable_if_t<
		inferior::is_input_iterator<InputIter>::value
	>;
	template<typename Iterator, bool is_iterator = is_iterator<Iterator>::value>
	struct is_forward_iterator : std::false_type {};
	template<typename Iterator>
	struct is_forward_iterator<Iterator, true> : std::is_base_of<
		std::forward_iterator_tag,
		typename std::iterator_traits<Iterator>::iterator_category
	> {};
}

#endif //INFERIOR_TYPE_TRAITS_HPP_

vector.hpp

#ifndef INFERIOR_VECTOR_VECTOR_HPP_
#define INFERIOR_VECTOR_VECTOR_HPP_
#include <inferior/no_min_max.h>
#include <cstddef>
#include <iterator>
#include <utility>
#include <initializer_list>
#include <stdexcept>
#include <algorithm>

#include <inferior/type_traits.hpp>
#include <inferior/iterator.hpp>
#include <inferior/memory.hpp>

namespace inferior {
    template<typename T>
    class vector {
    public:
        using reference = T&;
        using const_reference = const T&;
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using const_pointer = const T*;
        using iterator = contiguous_iterator<vector&>;
        using const_iterator = contiguous_iterator<const vector&>;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    private:
        pointer start_;
        pointer finish_;
        pointer end_of_storage_;
        /**
         * @brief 要素番号以降を削除
         * @param pos 対象要素番号
         * @detail LWG Issue 2033より、むやみにMoveAssignableを要求しないことが
         * 求められている。そのための補助関数。
         * http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2033
        */
        void erase_to_end(size_type pos) noexcept;
        /**
         * @brief sizeとcapacityを同時に変更する(メモリはいじらない)
         * @param sz 新しいsizeとcapacity
        */
        void set_size_and_capacity(size_type sz) noexcept;
        static constexpr size_type next_reallocate_size_ratio = 2;
        static constexpr size_type minimam_capacity_size_for_auto_decide = 16;
        /**
         * @brief いわゆる倍々ゲームの根幹、capacityを決定する関数
         * @param min_limit 最低限必要な長さ
        */
        size_type decide_new_capacity_size(size_type min_limit) const noexcept;
        /**
         * @brief 与えられた範囲を使って初期化を行う
         * @param first 範囲
         * @param last 範囲
         * 規格書には
         * Makes only N calls to the copy constructor of T
         * (where N is the distance between first and last)
         * and no reallocations if iterators first and last
         * are of forward, bidirectional, or random access categories
         * とあるので、input_iteratorとそうでないのを弾く必要がある
         * したがって、第3引数を使ってタグディスパッチを行う。
        */
        template<typename InputIter>
        void init_with_range(InputIter first, InputIter last, std::input_iterator_tag);
        /**
         * @brief 与えられた範囲を使って初期化を行う
         * @param first 範囲
         * @param last 範囲
         * 規格書には
         * Makes only N calls to the copy constructor of T
         * (where N is the distance between first and last)
         * and no reallocations if iterators first and last
         * are of forward, bidirectional, or random access categories
         * とあるので、input_iteratorとそうでないのを弾く必要がある
         * したがって、第3引数を使ってタグディスパッチを行う。
        */
        template<typename ForwardIterator>
        void init_with_range(ForwardIterator first, ForwardIterator last, std::forward_iterator_tag);
        /**
         * @brief const_iteratorをiteratorに変換する
         * @param it const_iterator
        */
        iterator to_iterator(const_iterator it) noexcept;
    public:
        vector() noexcept;
        vector(const vector& o);
        vector(vector&& o) noexcept;
        vector& operator=(const vector& o);
        vector& operator=(vector&& o) noexcept;
        ~vector() noexcept;

        explicit vector(size_type n);
        vector(size_type n, const T& value);
        template<typename InputIter, require_input_iterator<InputIter> = nullptr>
        vector(InputIter first, InputIter last);
        vector(std::initializer_list<T> il);

        iterator begin() noexcept;
        const_iterator begin() const noexcept;

        iterator end() noexcept;
        const_iterator end() const noexcept;

        const_iterator cbegin() const noexcept;

        const_iterator cend() const noexcept;

        reverse_iterator rbegin() noexcept;
        const_reverse_iterator rbegin() const noexcept;

        reverse_iterator rend() noexcept;
        const_reverse_iterator rend() const noexcept;

        const_reverse_iterator crbegin() const noexcept;

        const_reverse_iterator crend() const noexcept;

        size_type size() const noexcept;

        void resize(size_type sz);
        void resize(size_type sz, const T& c);

        size_type capacity() const noexcept;

        bool empty() const noexcept;

        void reserve(size_type n);

        void shrink_to_fit();

        reference operator[](size_type n) noexcept;
        const_reference operator[](size_type n) const noexcept;

        reference at(size_type n);
        const_reference at(size_type n) const;

        T* data() noexcept;
        const T* data() const noexcept;

        reference front() noexcept;
        const_reference front() const noexcept;

        reference back() noexcept;
        const_reference back() const noexcept;

        template <class InputIter, require_input_iterator<InputIter> = nullptr>
        void assign(InputIter first, InputIter last);
        void assign(size_type n, const T& u);
        void assign(std::initializer_list<T>);

        void push_back(const T& x);
        void push_back(T&& x);

        template <typename... Args>
        void emplace_back(Args&&... args);

        void pop_back();

        iterator insert(const_iterator position, const T& x);
        iterator insert(const_iterator position, T&& x);
        iterator insert(const_iterator position, size_type n, const T& x);
        template <class InputIter, require_input_iterator<InputIter> = nullptr>
        iterator insert(const_iterator position, InputIter first, InputIter last);
        iterator insert(const_iterator position, std::initializer_list<T> il);

        template <class... Args>
        iterator emplace(const_iterator position, Args&&... args);

        iterator erase(const_iterator position);
        iterator erase(const_iterator first, const_iterator last);

        void swap(vector& x) noexcept;

        void clear() noexcept;
    };
    template<typename T>
    void swap(vector<T>& l, vector<T>& r) noexcept;
}

#include <inferior/vector/vector_impl.hpp>

#endif //INFERIOR_VECTOR_VECTOR_HPP_