[lv5] ft_containers(2/6) vectorで使うサブ関数

2021年12月24日 16:00

[(1/6)vectorチュートにもどる] https://note.com/syamashi/n/n55ee0dad207d
[(3/6)vector実装にすすむ] https://note.com/syamashi/n/n329e33f09bb3

vectorの全体像が見えたところで、いったんサブ関数の再実装にうつります。

この課題を進める一番大事なテク。まず本家実装をよく読みます。
Q. 本家実装とは
A. VSCodeだと、Ctrlを押しながら変数名をクリックで、参照元にアクセスできます。

#include <type_traits>

int main(){
  std::iterator_traits  // Ctrlを押しながらアクセス
}

参照先
...\include\c++\bits\stl_iterator_base_types.h


 template<typename _Iterator>
   struct iterator_traits
   : public __iterator_traits<_Iterator> { };
#else
 template<typename _Iterator>
   struct iterator_traits
   {
     typedef typename _Iterator::iterator_category iterator_category;
     typedef typename _Iterator::value_type        value_type;
     typedef typename _Iterator::difference_type   difference_type;
     typedef typename _Iterator::pointer           pointer;
     typedef typename _Iterator::reference         reference;
   };
#endif

記載の本家コードを読み解いて実装します。

・iterators_traits

チュートリアルを読む。
https://cpp.rainy.me/031-iterator-operations.html#iterator-traits

基本方針は cppreference とします。
https://en.cppreference.com/w/cpp/iterator/iterator_traits

/utis/iterator.hpp

#ifndef ITERATOR_HPP
#define ITERATOR_HPP

#include <cstddef>

namespace ft {

//// Tags

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

};  // namespace ft

#endif

iteratorは必ず5種類のどれかに分類されます。そのタグを作成します。

/utis/iterator.hpp

//// iterator_traits

template <class Iterator>
struct iterator_traits {
 typedef typename Iterator::iterator_category iterator_category;
 typedef typename Iterator::value_type value_type;
 typedef typename Iterator::difference_type difference_type;
 typedef typename Iterator::pointer pointer;
 typedef typename Iterator::reference reference;
};

/// Partial specialization for pointer types.
template <class T>
struct iterator_traits<T*> {
 typedef ptrdiff_t difference_type;
 typedef T value_type;
 typedef T* pointer;
 typedef T& reference;
 typedef ft::random_access_iterator_tag iterator_category;
};

/// Partial specialization for pointer types.
template <class T>
struct iterator_traits<const T*> {
 typedef ptrdiff_t difference_type;
 typedef T value_type;
 typedef const T* pointer;
 typedef const T& reference;
 typedef ft::random_access_iterator_tag iterator_category;
};

iterator_traits は決まった5つの Member types を必ず持ちます。

・reverse_iterator

・cppreference
https://en.cppreference.com/w/cpp/iterator/reverse_iterator

Member Types から。
std::iteratorの継承からMember Typesを受け取るように、とのことなので、ft::iteratorも仕込んでおきます。
/utis/iterator.hpp

//// other iterators

template <class Category, class T, class Distance = std::ptrdiff_t,
         class Pointer = T*, class Reference = T&>
struct iterator {
 typedef Category iterator_category;
 typedef T value_type;
 typedef Distance difference_type;
 typedef Pointer pointer;
 typedef Reference reference;
};

//// reverse_iterator

template <class Iter>
class reverse_iterator
   : public iterator<typename ft::iterator_traits<Iter>::iterator_category,
                     typename ft::iterator_traits<Iter>::value_type,
                     typename ft::iterator_traits<Iter>::difference_type,
                     typename ft::iterator_traits<Iter>::pointer,
                     typename ft::iterator_traits<Iter>::reference> {
protected:
 Iter _current;
 typedef ft::iterator_traits<Iter> traits_type;

public:
 typedef Iter iterator_type;
 typedef typename traits_type::iterator_category iterator_category;
 typedef typename traits_type::value_type value_type;
 typedef typename traits_type::difference_type difference_type;
 typedef typename traits_type::pointer pointer;
 typedef typename traits_type::reference reference;
 }
};

Member functions をうめていきます。
Constructor 3つ
/utis/iterator.hpp

class reverse_iterator{
...

 //// Member functions

 reverse_iterator() : _current() {}
 explicit reverse_iterator(iterator_type x) : _current(x) {}
 template <class U>
 reverse_iterator(const reverse_iterator<U>& other) : _current(other.base()) {}

operator=

 template <class U>
 reverse_iterator& operator=(const ft::reverse_iterator<U>& other) {
   _current = other.base();
   return *this;
 }

destructor ( coplien form にするため )

 virtual ~reverse_iterator() {}

base

 iterator_type base() const { return _current; }

operator* / operator->

 reference operator*() const {
   Iter tmp = _current;
   return *--tmp;
 }
 pointer operator->() const { return &(operator*()); }

Q. operator*() で *--tmpをかえす
A. reverse_iteratorでは、ポインタの管理と、出力するポインタに1個ずれがあります。

・ポインタ管理
rbegin は end の位置に。
rend は begin の位置に_currentが割り当てられます。

    begin                end
      0    1    2    3    X

     rend              rbegin
      0    1    2    3    X

・出力するポインタ
rbeginはendの位置にあるけど、3をかえします。
1個左を返すので、*--iter が戻り値。
なお、*rend は参照しない想定。

    begin                end
      0    1    2    3    X

rend               rbegin
 Y    0    1    2    3    X

operator[]

reference operator[](difference_type n) const { return *(*this + n); }

operators

 reverse_iterator& operator++() {
   --_current;
   return *this;
 }
 reverse_iterator& operator--() {
   ++_current;
   return *this;
 }
 reverse_iterator operator++(int) {
   reverse_iterator __tmp = *this;
   --_current;
   return __tmp;
 }
 reverse_iterator operator--(int) {
   reverse_iterator __tmp = *this;
   ++_current;
   return __tmp;
 }
 reverse_iterator operator+(difference_type n) const {
   return reverse_iterator(_current - n);
 }
 reverse_iterator operator-(difference_type n) const {
   return reverse_iterator(_current + n);
 }
 reverse_iterator& operator+=(difference_type n) {
   _current -= n;
   return *this;
 }
 reverse_iterator& operator-=(difference_type n) {
   _current += n;
   return *this;
 }

reverse_iterator非メンバ関数のオーバーロード
/utis/iterator.hpp

//// reverse_iterator_nonmember_functions

template <class Iterator1, class Iterator2>
bool operator==(const ft::reverse_iterator<Iterator1>& lhs,
               const ft::reverse_iterator<Iterator2>& rhs) {
 return lhs.base() == rhs.base();
}
template <class Iterator1, class Iterator2>
bool operator!=(const ft::reverse_iterator<Iterator1>& lhs,
               const ft::reverse_iterator<Iterator2>& rhs) {
 return !(lhs == rhs);
}

template <class Iterator1, class Iterator2>
bool operator<(const ft::reverse_iterator<Iterator1>& lhs,
              const ft::reverse_iterator<Iterator2>& rhs) {
 return rhs.base() < lhs.base();
}
template <class Iterator1, class Iterator2>
bool operator>(const ft::reverse_iterator<Iterator1>& lhs,
              const ft::reverse_iterator<Iterator2>& rhs) {
 return lhs < rhs;
}
template <class Iterator1, class Iterator2>
bool operator<=(const ft::reverse_iterator<Iterator1>& lhs,
               const ft::reverse_iterator<Iterator2>& rhs) {
 return !(rhs < lhs);
}
template <class Iterator1, class Iterator2>
bool operator>=(const ft::reverse_iterator<Iterator1>& lhs,
               const ft::reverse_iterator<Iterator2>& rhs) {
 return !(lhs < rhs);
}

template <class Iter>
ft::reverse_iterator<Iter> operator+(
   typename ft::reverse_iterator<Iter>::difference_type n,
   const ft::reverse_iterator<Iter>& it) {
 return ft::reverse_iterator<Iter>(it.base() - n);
}

template <class Iterator>
typename ft::reverse_iterator<Iterator>::difference_type operator-(
   const ft::reverse_iterator<Iterator>& lhs,
   const ft::reverse_iterator<Iterator>& rhs) {
 return rhs.base() - lhs.base();
}

const ~~ でも動かすため、非メンバを実装。
引数でft::reverse_iterator<>を呼び出す必要があり、関数宣言がとても長くなりがち。
template<>を含む関数は.hppに書いていい、というのはそこから来てるのかもしれない。
template<>の中にない関数は.cppに記述しないといけません。自分の実装ではすべて.hppで完結します。

その他関数
/utis/iterator.hpp

//// Functions

template <class InputIterator, class Distance>
void advance(InputIterator& it, Distance n) {
 while (n > 0) {
   ++it;
   --n;
 }
 while (n < 0) {
   --it;
   ++n;
 }
 return;
}

template <class InputIterator>
typename ft::iterator_traits<InputIterator>::difference_type distance(
   InputIterator first, InputIterator last) {
 typename ft::iterator_traits<InputIterator>::difference_type ret = 0;
 while (first != last) {
   ++first;
   ++ret;
 }
 return (ret);
}

・random_access_iterator

アウトラインはreverse_iterator と全く同じ。中身だけ変えます。
ft::iteratorの継承からMember Typesを受けとります。
utis/random_access_iterator.hpp

#ifndef RANDOM_ACCESS_ITERATOR_HPP
#define RANDOM_ACCESS_ITERATOR_HPP

#include "iterator.hpp"

namespace ft {
template <typename T>
class random_access_iterator
   : public ft::iterator<ft::random_access_iterator_tag, T> {

}
};  // namespace ft
#endif

5つの Member Typesを記述。
utis/random_access_iterator.hpp

protected:
 T* _current;

public:
 typedef typename ft::iterator<ft::random_access_iterator_tag,
                               T>::iterator_category iterator_category;
 typedef typename ft::iterator<ft::random_access_iterator_tag, T>::value_type
     value_type;
 typedef
     typename ft::iterator<ft::random_access_iterator_tag, T>::difference_type
         difference_type;
 typedef T* pointer;
 typedef T& reference;

Member functionをうめます。
utis/random_access_iterator.hpp

 random_access_iterator() : _current(NULL) {}
 random_access_iterator(pointer x) : _current(x) {}
 random_access_iterator(const random_access_iterator& other)
     : _current(other._current) {}
 random_access_iterator& operator=(const random_access_iterator& other) {
   if (this == &other) return (*this);
   _current = other._current;
   return (*this);
 }
 ~random_access_iterator() {}
 pointer base() const { return _current; }
 reference operator*() const { return *_current; }
 pointer operator->() const { return &(operator*()); }
 reference operator[](difference_type n) const { return *(*this + n); }
 random_access_iterator& operator++() {
   ++_current;
   return *this;
 }
 random_access_iterator& operator--() {
   --_current;
   return *this;
 }
 random_access_iterator operator++(int) {
   random_access_iterator __tmp = *this;
   ++_current;
   return __tmp;
 }
 random_access_iterator operator--(int) {
   random_access_iterator __tmp = *this;
   --_current;
   return __tmp;
 }
 random_access_iterator operator+(difference_type n) const {
   return random_access_iterator(_current + n);
 }
 random_access_iterator operator-(difference_type n) const {
   return random_access_iterator(_current - n);
 }
 random_access_iterator& operator+=(difference_type n) {
   _current += n;
   return *this;
 }
 random_access_iterator& operator-=(difference_type n) {
   _current -= n;
   return *this;
 }

 /*
 ** ex. ft::reverse_iterator<ft::vector<int>::const_iterator> it1 =
 *a1.rbegin();
 */
 operator random_access_iterator<const T>() const {
   return (random_access_iterator<const T>(_current));
 }
};

Q. operator+=
A.
_current += n;
random_access_iteratorは要素が連続的に入っている想定のiteratorなので、ポインタの足し算で要素移動します。

非メンバ関数を埋めます。

utis/random_access_iterator.hpp

//// Non-member functions

template <class Iterator1, class Iterator2>
bool operator==(const ft::random_access_iterator<Iterator1>& lhs,
               const ft::random_access_iterator<Iterator2>& rhs) {
 return lhs.base() == rhs.base();
}
template <class Iterator1, class Iterator2>
bool operator!=(const ft::random_access_iterator<Iterator1>& lhs,
               const ft::random_access_iterator<Iterator2>& rhs) {
 return !(lhs == rhs);
}
template <class Iterator1, class Iterator2>
bool operator<(const ft::random_access_iterator<Iterator1>& lhs,
              const ft::random_access_iterator<Iterator2>& rhs) {
 return lhs.base() < rhs.base();
}
template <class Iterator1, class Iterator2>
bool operator<=(const ft::random_access_iterator<Iterator1>& lhs,
               const ft::random_access_iterator<Iterator2>& rhs) {
 return rhs < lhs;
}
template <class Iterator1, class Iterator2>
bool operator>(const ft::random_access_iterator<Iterator1>& lhs,
              const ft::random_access_iterator<Iterator2>& rhs) {
 return rhs < lhs;
}
template <class Iterator1, class Iterator2>
bool operator>=(const ft::random_access_iterator<Iterator1>& lhs,
               const ft::random_access_iterator<Iterator2>& rhs) {
 return lhs < rhs;
}

template <class Iter>
ft::random_access_iterator<Iter> operator+(
   typename ft::random_access_iterator<Iter>::difference_type n,
   const ft::random_access_iterator<Iter>& it) {
 return ft::random_access_iterator<Iter>(it.base() + n);
}

template <class Iterator>
typename ft::random_access_iterator<Iterator>::difference_type operator-(
   const ft::random_access_iterator<Iterator>& lhs,
   const ft::random_access_iterator<Iterator>& rhs) {
 return lhs.base() - rhs.base();

・enable_if / is_integral

vectorのconstructer(5)を読む
・実装サンプル
https://secret-garden.hatenablog.com/entry/2016/12/22/032008

・vector constructer(5)

 template <typename InputIterator>
 vector(InputIterator first, InputIterator last,
        const Allocator& allocator = Allocator(),
        typename std::enable_if<!std::is_integral<InputIterator>::value,
                                InputIterator>::type* = NULL)

第1引数 InputIterator first
第2引数 InputIterator last
第3引数 const Allocator& allocator = Allocator()
第4引数 typename std::enable_if<!std::is_integral<InputIterator>::value,
                                InputIterator>::type* = NULL

・第4引数について。
・もし InputIterator == int だった場合、

std::enable_if<!std::is_integral<InputIterator>::value, InputIterator>::type* = NULL
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ == true
               ~ == false
std::enable_if<false, >になるので、::type* が定義されず、第4引数が存在しない扱いになる。
よって、オーバーロードが適応されない。


・もし InputIterator == iterator だった場合、

std::enable_if<!std::is_integral<InputIterator>::value, InputIterator>::type* = NULL
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ == false
               ~ == true
std::enable_if<true, >になるので、::type* が定義され、第4引数が存在する扱いになる。
よって、オーバーロードが適応される。

・テンプレートってなに？ってところからSFINAEあたりまで頑張る
https://dora119.hateblo.jp/entry/2017/12/05/001607

std::is_initegralというのはTが整数の時に::valueがtrue、そうでなければfalseになるテンプレートです
大体予想できているかもしれませんが、intCheck(10)のように呼び出すと、引数10は整数なのでenable_if::typeが存在し、"xは整数"と出力されます
一方intCheck(1.5)のようにするとenable_if::typeは存在せずエラーになるというわけです
こんな風にしてテンプレート版if文ができちゃいました、SFINAE強い

「::type」の有無でオーバーロード判定を分ける機構のことをSFINAEという。すふぃ姉。

実装します。

/utils/util.hpp

#ifndef UTIL_HPP
#define UTIL_HPP

namespace ft {

/// integral_constant

template <typename _Tp, _Tp __v>
struct integral_constant {
 static const _Tp value = __v;
 typedef _Tp value_type;
 typedef integral_constant<_Tp, __v> type;
 const value_type operator()() const { return value; }
};

/// The type used as a compile-time boolean with true value.
typedef integral_constant<bool, true> true_type;

/// The type used as a compile-time boolean with false value.
typedef integral_constant<bool, false> false_type;


};  // namespace ft
#endif

Q. integral_constant
A. is_integral / enable_if のメタ構造体。
覚えておくのは2つの特徴だけで、
1. valueとvalue_typeの定義があること。
2.
true_type::value をとったときに true。
false_type::value をとったときに falseを返す構造体。
とでも思っておきます。

本家にある

constexpr operator value_type() const { return value; } // c++11

戻り値のないoperatorとは？という感じですが、c++11の機能「conversion function: 変換関数」で、割愛します。ともなって、テストケース

 ft::is_integral<int>() // 1
 ft::is_integral<int*>() // 0

これらの出力は含めません。

Q. const value_type operator()() const { return value; }
A. こう呼び出せます。

 ft::is_integral<int> F;
 int f = F(); // f == 1

/utils/util.hpp

/// is_same
/*
通常はfalse_typeを継承
型が同じ場合だけtrueになる
*/
template <typename, typename>
struct is_same : public false_type {};

template <typename _Tp>
struct is_same<_Tp, _Tp> : public true_type {};

Q. is_same()
A.
is_same<int, int>::valueでtrue
is_same<int, char>::valueでfalse がとれます。使いません。

/utils/util.hpp

/// remove_const
template <typename T>
struct remove_const {
 typedef T type;
};

template <typename T>
struct remove_const<T const> {
 typedef T type;
};

/// remove_volatile
template <typename T>
struct remove_volatile {
 typedef T type;
};

template <typename T>
struct remove_volatile<T volatile> {
 typedef T type;
};

/// remove_cv
template <typename T>
struct remove_cv {
 typedef typename remove_const<typename remove_volatile<T>::type>::type type;
};

/// helper

template <typename>
struct __is_integral_helper : public false_type {};

template <>
struct __is_integral_helper<bool> : public true_type {};

template <>
struct __is_integral_helper<char> : public true_type {};

template <>
struct __is_integral_helper<signed char> : public true_type {};

template <>
struct __is_integral_helper<unsigned char> : public true_type {};

template <>
struct __is_integral_helper<wchar_t> : public true_type {};

//template <>
//struct __is_integral_helper<char16_t> : public true_type {};

//template <>
//struct __is_integral_helper<char32_t> : public true_type {};

template <>
struct __is_integral_helper<short> : public true_type {};

template <>
struct __is_integral_helper<unsigned short> : public true_type {};

template <>
struct __is_integral_helper<int> : public true_type {};

template <>
struct __is_integral_helper<unsigned int> : public true_type {};

template <>
struct __is_integral_helper<long> : public true_type {};

template <>
struct __is_integral_helper<unsigned long> : public true_type {};

template <>
struct __is_integral_helper<long long> : public true_type {};

template <>
struct __is_integral_helper<unsigned long long> : public true_type {};

//// is_integral
template <typename T>
struct is_integral
   : public __is_integral_helper<typename remove_cv<T>::type>::type {};

Q. is_integral()
A. 最後のis_integralを読み解きます。
1. remove_cv は、const / volatile修飾を外した型Tを返します。
2. __is_integral_helper<> は、整数型なら true_type、そうじゃないならfalse_typeを返すように定義しています。
まず、基本的にfalse_typeを返すように定義。

template <typename>
struct __is_integral_helper : public false_type {};

そのあと、すべての整数型でtrue_typeを定義しています。
以上から、
is_integral<int>::value == true だし、
is_integral<iter>::value == false が得られます。

最後に、

/utils/util.hpp

template <bool B, class T = void>
struct enable_if {};

template <class T>
struct enable_if<true, T> {
 typedef T type;

enable_if<true, T>::type が存在し、
enable_if<false, T>は、typedef type がないので、「::type」が得られません。ここがオーバーロード判定に利用されています。

Q. 継承が嫌い。 : public true_type() をしない場合

value と value_type の定義が必須です。

template <>
struct __is_integral_helper<int>{
 static const bool value = true;
 typedef int value_type;
 typedef __is_integral_helper<int> type;
 const value_type operator()() const { return value; }
};

とでも書きます。これを全部書くの大変。

オーバーロードの判定に::typeの有無を使う是非はわかりませんが、スマートなのかわからないけど、なるほど解決という気分になります。

・equal/lexicographical compare

https://cpprefjp.github.io/reference/algorithm/equal.html
https://cpprefjp.github.io/reference/algorithm/lexicographical_compare.html
サンプルコードが明解です。

#ifndef ALGORITHM_HPP
#define ALGORITHM_HPP

namespace ft {
template <class InputIt1, class InputIt2>
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) {
 for (; first1 != last1; ++first1, ++first2)
   if (!bool(*first1 == *first2)) return false;
 return true;
}

template <class InputIt1, class InputIt2, class BinaryPredicate>
bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2,
          BinaryPredicate p) {
 for (; first1 != last1; ++first1, ++first2)
   if (!bool(p(*first1, *first2))) return false;
 return true;
}

template <class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                            InputIt2 last2) {
 for (; (first1 != last1) && (first2 != last2); ++first1, (void)++first2) {
   if (*first1 < *first2) return true;
   if (*first2 < *first1) return false;
 }
 return (first1 == last1) && (first2 != last2);
}

template <class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                            InputIt2 last2, Compare comp) {
 for (; (first1 != last1) && (first2 != last2); ++first1, (void)++first2) {
   if (comp(*first1, *first2)) return true;
   if (comp(*first2, *first1)) return false;
 }
 return (first1 == last1) && (first2 != last2);
}
};  // namespace ft
#endif

これでft::vectorを実装するアイテムが整いました。
vectorチュートリアルだけだと、実は結構な関数が欠けています。埋めていきます。

[(3/6)vector実装にすすむ]

https://note.com/syamashi/n/n329e33f09bb3

[lv5] ft_containers(2/6) vectorで使うサブ関数

・iterators_traits

・reverse_iterator

・random_access_iterator

・enable_if / is_integral

・equal/lexicographical compare

いいなと思ったら応援しよう！