[lv5] ft_containers(1/6) vectorチュートリアル

[(0/6)はじめにもどる] https://note.com/syamashi/n/nd36a889a1166
[(2/6)サブ関数にすすむ] https://note.com/syamashi/n/na27f05d42ac8

0. 江添亮のC++入門。
vectorだけやればいいかと思ったが、array編の実装を引き継いだ話になるので、ここから読みます。
・std::array
https://cpp.rainy.me/020-array.html

読み終えたら、いよいよvectorの実装。ここで書くコードは提出まで使います。ここから
・vectorの実装 : 基礎　簡易vectorの概要
https://cpp.rainy.me/033-vector-implementation.html#%E7%B0%A1%E6%98%93vector%E3%81%AE%E6%A6%82%E8%A6%81

・コピー
https://cpp.rainy.me/035-copy.html
ここまで写経。

ちなみに、c++11以降の機能/関数を実装してはいけないので、以下の写経はスキップします。

1. move
2. void shrink_to_fit()
3. 初期化子リスト: vector<int> V = {1,2,3};

コピーチュートリアルまで写経しても、脱字や環境差異によって動きません。4点修正し、動くようにしたものがこちら。

containers/vector.hpp

#ifndef VECTOR_HPP
#define VECTOR_HPP

#include <iostream>
#include <iterator>
#include <limits>

namespace ft {

template <typename T, typename Allocator = std::allocator<T> >
class vector {
public:
 // value_typeなどネストされた型名
 using value_type = T;
 using pointer = T*;
 using const_pointer = const pointer;
 using reference = value_type&;
 using const_reference = const value_type&;
 using allocator_type = Allocator;
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;

 using iterator = pointer;
 using const_iterator = const_pointer;
 using reverse_iterator = std::reverse_iterator<iterator>;
 using const_reverse_iterator = std::reverse_iterator<const_iterator>;

 // コンストラクター
 vector() : vector(allocator_type()) {}
 vector(const allocator_type& alloc) noexcept
     : first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {}

 explicit vector(size_type count, const T& value = T(),
                 const Allocator& alloc = Allocator())
     : vector(alloc) {
   resize(count, value);
 }

 template <typename InputIterator>
 vector(InputIterator first, InputIterator last,
        const Allocator& allocator = Allocator(),
        typename std::enable_if<!std::is_integral<InputIterator>::value,
                                InputIterator>::type* = NULL)
     : first(NULL), last(NULL), reserved_last(NULL), alloc(allocator) {
   reserve(std::distance(first, last));
   for (auto i = first; i != last; ++i) {
     push_back(*i);
   }
 }

 // デストラクター
 ~vector() {
   // 1. 要素を末尾から先頭に向かう順番で破棄
   clear();
   // 2. 生のメモリーを解放する
   deallocate();
 }
 // コピー
 vector(const vector& r)
     : first(NULL),
       last(NULL),
       reserved_last(NULL),
       alloc(traits::select_on_container_copy_construction(r.alloc)) {
   // コピー元の要素数を保持できるだけのストレージを確保
   reserve(r.size());
   // コピー元の要素をコピー構築
   // destはコピー先
   // [src, last)はコピー元
   for (auto dest = first, src = r.begin(), last = r.end(); src != last;
        ++dest, ++src) {
     construct(dest, *src);
   }
   last = first + r.size();
 }

 vector& operator=(const vector& r) {
   // 1. 自分自身への代入なら何もしない
   if (this == &r) return *this;

   // 2. 要素数が同じならば
   if (size() == r.size()) {  // 要素ごとにコピー代入
     std::copy(r.begin(), r.end(), begin());
   }
   // 3. それ以外の場合で
   else
       // 予約数が十分ならば、
       if (capacity() >= r.size()) {
     // 有効な要素はコピー
     std::copy(r.begin(), r.begin() + r.size(), begin());
     // 残りはコピー構築
     for (auto src_iter = r.begin() + r.size(), src_end = r.end();
          src_iter != src_end; ++src_iter, ++last) {
       construct(last, *src_iter);
     }
   }
   // 4. 予約数が不十分ならば
   else {
     // 要素をすべて破棄
     destroy_until(rbegin());
     // 予約
     reserve(r.size());
     // コピー構築
     for (auto src_iter = r.begin(), src_end = r.end(), dest_iter = begin();
          src_iter != src_end; ++src_iter, ++dest_iter, ++last) {
       construct(dest_iter, *src_iter);
     }
   }
   return *this;
 }
 // 容量確認
 size_type size() const noexcept { return end() - begin(); }
 bool empty() const noexcept { return begin() == end(); }
 size_type capacity() const noexcept { return reserved_last - first; }

 // 要素アクセス

 void push_back(const_reference value) {
   // 予約メモリーが足りなければ拡張
   if (size() + 1 > capacity()) {
     // 現在のストレージサイズ
     auto c = size();
     // 0の場合は1に
     if (c == 0)
       c = 1;
     else
       // それ以外の場合は2倍する
       c *= 2;

     reserve(c);
   }
   construct(last, value);
   ++last;
 }

 reference operator[](size_type i) { return first[i]; }
 const_reference operator[](size_type i) const { return first[i]; }
 reference at(size_type i) {
   if (i >= size()) throw std::out_of_range("index is out of range.");

   return first[i];
 }
 const_reference at(size_type i) const {
   if (i >= size()) throw std::out_of_range("index is out of range.");

   return first[i];
 }

 reference front() { return *first; }
 const_reference front() const { return *first; }
 reference back() { return *(last - 1); }
 const_reference back() const { return *(last - 1); }

 pointer data() noexcept { return first; }
 const_pointer data() const noexcept { return first; }

 // イテレーターアクセス
 iterator begin() noexcept { return first; }
 iterator end() noexcept { return last; }
 iterator begin() const noexcept { return first; }
 iterator end() const noexcept { return last; }
 const_iterator cbegin() const noexcept { return first; }
 const_iterator cend() const noexcept { return last; }
 reverse_iterator rbegin() noexcept { return reverse_iterator{last}; }
 reverse_iterator rend() noexcept { return reverse_iterator{first}; }
 const_reverse_iterator rbegin() const noexcept {
   return reverse_iterator{last};
 }
 const_reverse_iterator rend() const noexcept {
   return reverse_iterator{first};
 }

 void clear() noexcept { destroy_until(rend()); }

 /*
 1. すでに指定された要素数以上に予約されているなら何もしない
 2. まだ動的メモリー確保が行われていなければ動的メモリー確保をする
 3. 有効な要素がある場合は新しいストレージにコピーする
 */
 void reserve(size_type sz) {
   // すでに指定された要素数以上に予約されているなら何もしない
   if (sz <= capacity()) return;

   // 動的メモリー確保をする
   auto ptr = allocate(sz);

   // 古いストレージの情報を保存
   auto old_first = first;
   auto old_last = last;
   auto old_capacity = capacity();

   // 新しいストレージに差し替え
   first = ptr;
   last = first;
   reserved_last = first + sz;

   // 例外安全のため
   // 関数を抜けるときに古いストレージを破棄する
   //    std::scope_exit e(
   //        [&] { traits::deallocate(alloc, old_first, old_capacity); });

   // 古いストレージから新しいストレージに要素をコピー構築
   // 実際にはムーブ構築
   for (auto old_iter = old_first; old_iter != old_last; ++old_iter, ++last) {
     // このコピーの理解にはムーブセマンティクスの理解が必要
     construct(last, std::move(*old_iter));
   }

   // 新しいストレージにコピーし終えたので
   // 古いストレージの値は破棄
   for (auto riter = reverse_iterator(old_last),
             rend = reverse_iterator(old_first);
        riter != rend; ++riter) {
     destroy(&*riter);
   }
   // scope_exitによって自動的にストレージが破棄される
   alloc.deallocate(old_first, old_capacity);
 }

 /*
 1. 現在の要素数より少なくリサイズする場合、末尾から要素を破棄する
 2. 現在の要素数より大きくリサイズする場合、末尾に要素を追加する
 3. 現在の要素数と等しくリサイズする場合、何もしない
 */
 void resize(size_type sz) {
   // 現在の要素数より少ない
   if (sz < size()) {
     auto diff = size() - sz;
     destroy_until(rbegin() + diff);
     last = first + sz;
   }
   // 現在の要素数より大きい
   else if (sz > size()) {
     reserve(sz);
     for (; last != reserved_last; ++last) {
       construct(last);
     }
   }
 }

 void resize(size_type sz, const_reference value) {
   // 現在の要素数より少ない
   if (sz < size()) {
     auto diff = size() - sz;
     destroy_until(rbegin() + diff);
     last = first + sz;
   }
   // 現在の要素数より大きい
   else if (sz > size()) {
     reserve(sz);
     for (; last != reserved_last; ++last) {
       construct(last, value);
     }
   }
 }

private:
 // 先頭の要素へのポインター
 pointer first;
 // 最後の要素の1つ前方のポインター
 pointer last;
 // 確保したストレージの終端
 pointer reserved_last;
 // アロケーターの値
 allocator_type alloc;

 // ヘルパー関数
private:
 using traits = std::allocator_traits<allocator_type>;
 pointer allocate(size_type n) { return traits::allocate(alloc, n); }
 void deallocate() { traits::deallocate(alloc, first, capacity()); }
 void construct(pointer ptr) { traits::construct(alloc, ptr); }
 void construct(pointer ptr, const_reference value) {
   traits::construct(alloc, ptr, value);
 }
 // ムーブ用
 void construct(pointer ptr, value_type&& value) {
   traits::construct(alloc, ptr, std::move(value));
 }
 void destroy(pointer ptr) { traits::destroy(alloc, ptr); }
 void destroy_until(reverse_iterator rend) {
   for (auto riter = rbegin(); riter != rend; ++riter, --last) {
     destroy(&*riter);
   }
 }
};

};  // namespace ft

#endif

編集は4点。
1. constructerをcppreference準拠に変更。

1. cppreference に準拠

  // コンストラクター
 vector() : vector(allocator_type()) {}

 vector(const allocator_type& alloc) noexcept
     : first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {}

 explicit vector(size_type count, const T& value = T(),
                 const Allocator& alloc = Allocator())
     : vector(alloc) {
   resize(count, value);
 }

 template <typename InputIterator>
 vector(InputIterator first, InputIterator last,
        const Allocator& allocator = Allocator(),
        typename std::enable_if<!std::is_integral<InputIterator>::value,
                                InputIterator>::type* = NULL)
     : first(NULL), last(NULL), reserved_last(NULL), alloc(allocator) {
   reserve(std::distance(first, last));
   for (auto i = first; i != last; ++i) {
     push_back(*i);
   }
 }

Q. cppreference
A. cppの公式サイト。
例えば、以下は std::vector の constructer 定義が記載されています。
https://en.cppreference.com/w/cpp/container/vector/vector

Q. どう読めばいい
A. まず関数のバージョンから見ます。
今課題で実装すべきは、c++11より前バージョンの関数。以下5つです。

(1) vector(); (until c++17)
(2) explicit vector( const Allocator& alloc ); (until C++17)
(3) explicit vector( size_type count,
                const T& value = T(),
                const Allocator& alloc = Allocator()); (until C++11)
(5) template< class InputIt >
vector( InputIt first, InputIt last, 
       const Allocator& alloc = Allocator() ); (until C++20)
(6) vector( const vector& other ); (until C++20)

Q.  (5) typename std::enable_if<!std::is_integral<InputIterator>::value,
InputIterator>::type* = NULL
A. 引数templateの、InputIteratorについて。
なんと、Iterator認識してくれません。なので、
vector<int>(1, 2);
が(5) template <typename InputIterator> に入ってしまいます。
std::enable_ifを使用することで、Iteratorのみ正しくオーバーロードされるようになります。後ほど記載するので今は写経。

2. std::scope_exitを削除

void reserve(size_type sz) {
  ...
  // scope_exitによって自動的にストレージが破棄されるところ、されなくなるので、deallocateを追記
  alloc.deallocate(old_first, old_capacity);
}

3. referenceの型あわせ

 reference front() { return *first; }
 const_reference front() const { return *first; }
 reference back() { return *(last - 1); }
 const_reference back() const { return *(last - 1); }

4. destroy_allではない

 destroy_until(rbegin()); // destory_all()

次。テストケースはこちら。
これは消去予定。コンパイルできるかどうか、ぐらいの確認で適当。
testfiles/main.cpp

#include "tester.hpp"

int main() {
  tutorial_test();
}

testfiles/tutorial.cpp

#include "tester.hpp"
#include <array>

template <typename T>
void pout(T s) {
 static int no;
 cout << endl;
 cout << "--- [" << ++no << "]:" << s << " ---" << endl;
}

template <class T>
void vdebug(T& V) {
 cout << "size:" << V.size() << " capacity:" << V.capacity() << endl;
 cout << "{ ";
 for (typename T::iterator it = V.begin(); it != V.end(); ++it)
   cout << *it << " ";
 cout << "}" << endl;
}

void tutorial_test() {
 {
   ft::vector<int> v(1);
   // ft::vector<int>::iterator
   auto i = v.begin();
   // OK、代入可能
   *i = 0;
   // constなvectorへのリファレンス
   auto const& cv = v;
   // ft::vector<int>::const_iterator ここがとれない
   auto ci = cv.begin();
   // エラー
   // const_iteratorを参照した先には代入できない
   cout << *ci << endl;
 }


 {
   ft::vector<int> v(1);
   // ft::vector<int>::const_iterator
   auto i = v.cbegin();
   cout << *i << endl;
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);

   // イテレーター
   auto i = v.begin();
   cout << *i << endl;  // 1

   // リバースイテレーター
   auto r = v.rbegin();
   cout << *r << endl;  // 5
 }

 {
   ft::vector<int> v;
   // true、要素数0
   bool a = v.empty();
   cout << a << endl;
   v.push_back(0);
   // false、要素数非ゼロ
   bool b = v.empty();
   cout << b << endl;
   // 1、現在の要素数
   auto s = v.size();
   cout << s << endl;
   // 実装依存、追加の動的メモリー確保をせずに格納できる要素の最大数
   auto c = v.capacity();
   cout << c << endl;
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);
   v[1];  // 2
   v[3];  // 4
 }

 {
   try {
     // 有効なインデックスはv[0]からv[4]まで
     ft::vector<int> v;
     for (int i = 1; i <= 5; ++i) v.push_back(i);

     v[0] = 0;  // OK
     v[3] = 0;  // OK
     v[5] = 0;  // エラー
   } catch (std::out_of_range e) {
     cout << e.what();
   }
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);
   v.front();  // 1
   v.back();   // 5
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 3; ++i) v.push_back(i);
   int* ptr = v.data();
   cout << *ptr << endl;  // 1
 }

 {
   ft::vector<int> v;
   cout << v.empty() << endl;  // true
 }

 {
   ft::vector<int> v(100);
   cout << v.size() << endl;  // 100
 }

 {
   ft::vector<int> v(100, 123);
   v[0];   // 123
   v[12];  // 123
   v[68];  // 123
 }

 {
   ft::vector<int> v;
   v.resize(10);
   v.size();  // 10
   // 減らす
   v.resize(5);
   v.size();  // 5
 }

 {
   ft::vector<int> v;
   v.resize(3, 123);
   // vは{123,123,123}
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);
   v.resize(3);
   // vは{1,2,3}
 }

 {
   ft::vector<int> v;
   // vは{}
   v.push_back(1);
   // vは{1}
   v.push_back(2);
   // vは[1,2}
   v.push_back(3);
   // vは{1,2,3}
 }

 {
   ft::vector<int> v;
   // 少なくとも3個の要素を追加できるように動的メモリー確保
   v.reserve(3);
   v.size();      // 0
   v.capacity();  // 3以上

   // 動的メモリー確保は発生しない
   v.push_back(1);
   v.push_back(2);
   v.push_back(3);
   // 動的メモリー確保が発生する可能性がある。
   v.push_back(3);
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 3; ++i) v.push_back(i);
   v.clear();
   v.size();  // 0
 }

 {
   std::allocator<int> alloc;
   // 空
   ft::vector<int> v1(alloc);
   // 要素数5
//    ft::vector<int> v2(5, alloc);
   // 要素数5で初期値123
   ft::vector<int> v3(5, 123, alloc);
 }

 {
   // 要素数5
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);
   // 3個の要素を保持できるよう予約
   v.reserve(3);
   // 無視する
 }

 {
   ft::vector<int> v;
   // おそらく動的メモリー確保
   v.reserve(10000);
 }

 {
   // 要素数3
   ft::vector<int> v;
   for (int i = 1; i <= 3; ++i) v.push_back(i);
   // 1万個の要素を保持できるだけのメモリーを予約
   v.reserve(10000);
   // vは{1,2,3}
 }

 {
   // 要素数0
   ft::vector<int> v;
   // 要素数10
   v.resize(10);
   // 要素数5
   v.resize(5);
   // 要素数変わらず
   v.resize(5);
 }

 {
   ft::vector<int> v ;
   for(int i=1; i<=3; ++i) v.push_back(i);
   v.resize(5, 4);
   // vは{1,2,3,4,4}
 }

 {
   // 要素数5
   ft::vector<int> v(5);
   v.resize(5);  // 何もしない
 }

 {
   ft::vector<int> v(10, 1);
   v[2] = 99;
   v.resize(5);
   // vは{1,1,99,1,1}
 }

 {
   ft::vector<int> v;
   // vは{}
   v.push_back(1);
   // vは{1}
   v.push_back(2);
   // vは{1,2}
 }

 {
   std::array<int, 5> a{1, 2, 3, 4, 5};
   ft::vector<int> v(std::begin(a), std::end(a));
   // vは{1,2,3,4,5}
 }

 {
   ft::vector<int> v;
   for (int i = 1; i <= 5; ++i) v.push_back(i);
   ft::vector<int> w = v;
   // wは{1,2,3,4,5}
 }
}

江添int main()のうち、テストケースを2つ除外します。
1.1) const_iteratorにならない。

  {
   ft::vector<int> v(1);
   // ft::vector<int>::iterator
   auto i = v.begin();
   // OK、代入可能
   *i = 0;
   // constなvectorへのリファレンス
   auto const& cv = v;
   // ft::vector<int>::const_iterator
   auto ci = cv.begin();
   // エラー
   // const_iteratorを参照した先には代入できない
   cout << *ci << endl;
 }

最後の *ci = 0; を対象外。
random_access_iteratorを実装したら、const_iteratorとして読まれるようになります。

1.2) c++11なので実装対象外

ft::vector<int> v2(5, alloc);
                ^  ~~~~~~~~
tutorial.cpp:184:21: error: no matching constructor for initialization of 'ft::vector<int>'

・tutorial写経->c++11でコンパイルできるところまで。
newgameフォルダで仕事してます。
https://github.com/syamashi/ft_container/tree/c593b635ab4c2b5f46f61b81bcf5285bcb60790b/newgame

コンパイル成功でようやく一息。

vectorに必要な関数を先に実装します。

[その他関数にすすむ] https://note.com/syamashi/n/na27f05d42ac8