Skip to content

Instantly share code, notes, and snippets.

@yumetodo
Last active December 17, 2018 11:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yumetodo/a7221eece1ba19f5f26eff3ddcadf008 to your computer and use it in GitHub Desktop.
Save yumetodo/a7221eece1ba19f5f26eff3ddcadf008 to your computer and use it in GitHub Desktop.
inferior vector util
#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_
#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_
#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_
#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_
#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_
#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_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment