[lv5] ft_containers(3/6) vectorの実装
[(2/6)vector_otherにもどる] https://note.com/syamashi/n/n55ee0dad207d
[(4/6)stackにすすむ] https://note.com/syamashi/n/nbc30c2c89db4
-std=c++98 をつけてコンパイルすると、c++11の記法でコケます。
どんどん置換します。
auto -> 型の明記
using A = B -> typedef B A
noexcept -> delete
return reverse_iterator{last} -> return reverse_iterator(last)
for(auto v: V) -> for( ; ; )
std::allocator_traits -> allocから直接呼び出す。 // alloc.construct()
vector : vector(alloc) -> ほかのコンストラクタに投げない。
// : first(NULL), last(NULL), reserved_last(NULL), alloc(alloc)
select_on_container_copy_construction -> delete
std::move -> delete
cbegin / cend -> deleteQ. reverse_iterator{last}
A. 一様初期化(c++11)
https://cpprefjp.github.io/lang/cpp11/uniform_initialization.html
reverse_iterator(last) で代替した。
チュートリアルを置換しただけのものが以下。
/testfiles/Makefile
CFLAGS = -Wall -Werror -Wextra -std=c++98/containers/vector.hpp
#ifndef VECTOR_HPP
#define VECTOR_HPP
#include <iostream>
#include <limits>
#include "../utils/algorithm.hpp"
#include "../utils/iterator.hpp"
#include "../utils/random_access_iterator.hpp"
#include "../utils/util.hpp"
namespace ft {
template <typename T, typename Allocator = std::allocator<T> >
class vector {
public:
// value_typeなどネストされた型名
typedef T value_type;
typedef T* pointer;
typedef const pointer const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef Allocator allocator_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef pointer iterator;
typedef const_pointer const_iterator;
typedef ft::reverse_iterator<iterator> reverse_iterator;
typedef ft::reverse_iterator<const_iterator> const_reverse_iterator;
// コンストラクター
vector()
: first(NULL), last(NULL), reserved_last(NULL), alloc(allocator_type()) {}
vector(const allocator_type& alloc)
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {}
explicit vector(size_type count, const T& value = T(),
const Allocator& alloc = Allocator())
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {
resize(count, value);
}
template <typename InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& alloc = Allocator(),
typename ft::enable_if<!ft::is_integral<InputIterator>::value,
InputIterator>::type* = NULL)
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {
reserve(ft::distance(first, last));
for (pointer i = first; i != last; ++i) {
push_back(*i);
}
}
// コピー
vector(const vector& r)
: first(NULL), last(NULL), reserved_last(NULL), alloc(r.alloc) {
// コピー元の要素数を保持できるだけのストレージを確保
reserve(r.size());
// コピー元の要素をコピー構築
// destはコピー先
// [src, last)はコピー元
for (pointer dest = first, src = r.begin(), last = r.end(); src != last;
++dest, ++src) {
construct(dest, *src);
}
last = first + r.size();
}
// デストラクター
~vector() {
// 1. 要素を末尾から先頭に向かう順番で破棄
clear();
// 2. 生のメモリーを解放する
deallocate();
}
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 (const_iterator 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 (const_iterator 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 { return end() - begin(); }
bool empty() const { return begin() == end(); }
size_type capacity() const { return reserved_last - first; }
// 要素アクセス
void push_back(const_reference value) {
// 予約メモリーが足りなければ拡張
if (size() + 1 > capacity()) {
// 現在のストレージサイズ
size_type 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() { return first; }
const_pointer data() const { return first; }
// イテレーターアクセス
iterator begin() { return first; }
iterator end() { return last; }
const_iterator begin() const { return first; }
const_iterator end() const { return last; }
reverse_iterator rbegin() { return reverse_iterator(last); }
reverse_iterator rend() { return reverse_iterator(first); }
const_reverse_iterator rbegin() const { return reverse_iterator(last); }
const_reverse_iterator rend() const { return reverse_iterator(first); }
void clear() { destroy_until(rend()); }
/*
1. すでに指定された要素数以上に予約されているなら何もしない
2. まだ動的メモリー確保が行われていなければ動的メモリー確保をする
3. 有効な要素がある場合は新しいストレージにコピーする
*/
void reserve(size_type sz) {
// すでに指定された要素数以上に予約されているなら何もしない
if (sz <= capacity()) return;
// 動的メモリー確保をする
pointer ptr = allocate(sz);
// 古いストレージの情報を保存
pointer old_first = first;
pointer old_last = last;
size_type old_capacity = capacity();
// 新しいストレージに差し替え
first = ptr;
last = first;
reserved_last = first + sz;
// 例外安全のため
// 関数を抜けるときに古いストレージを破棄する
// std::scope_exit e(
// [&] { traits::deallocate(alloc, old_first, old_capacity); });
// 古いストレージから新しいストレージに要素をコピー構築
// 実際にはムーブ構築
for (pointer old_iter = old_first; old_iter != old_last; ++old_iter, ++last) {
// このコピーの理解にはムーブセマンティクスの理解が必要
construct(last, *old_iter);
}
// 新しいストレージにコピーし終えたので
// 古いストレージの値は破棄
for (reverse_iterator 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()) {
difference_type 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()) {
difference_type 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:
pointer allocate(size_type n) { return alloc.allocate(n); }
void deallocate() { alloc.deallocate(first, capacity()); }
void construct(pointer ptr) { alloc.construct(ptr, 0); }
void construct(pointer ptr, const_reference value) {
alloc.construct(ptr, value);
}
void destroy(pointer ptr) { alloc.destroy(ptr); }
void destroy_until(reverse_iterator rend) {
for (reverse_iterator riter = rbegin(); riter != rend; ++riter, --last) {
destroy(&*riter);
}
}
};
}; // namespace ft
#endif/testfiles/tester.hpp
//// tester
void vector_test();/testfiles/main.cpp
#include "tester.hpp"
int main() {
vector_test();
}tutorial_test()は削除して、vector_test()に吸収します。
/testfiles/test_vector.cpp
#include "tester.hpp"
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 vector_test() {
}Q. pout()
A. --- [テストNo] タイトル ---
Q. vdebug()
A. 引数にvectorを渡したら、サイズ、キャパ、配列の中身を列挙させます。
ここから、cppreferenceを参照して、不足しているvectorの実装を進めます。
・cppreference ( vector )
https://en.cppreference.com/w/cpp/container/vector
・Member types
/containers/vector.hpp
{
typedef typename ft::random_access_iterator<value_type> iterator;
typedef typename ft::random_access_iterator<const value_type> const_iterator;
typedef typename ft::reverse_iterator<iterator> reverse_iterator;
typedef typename ft::reverse_iterator<const_iterator> const_reverse_iterator;
}Q. iterator
もともとusing iterator = pointerとしていましたが、
iterator = ft::random_access_iteratorとします。
そうはいっても、iteratorのメンバ変数は*Tだけだし、vectorのメンバ変数も*Tだけ。名称が違うだけで扱いは全く同じ。iteratorを使わずとも、pointerでvectorの関数実装はできてしまいます。
iteratorのありがたみはmapで実感できるので、とりあえず進めます。
iteratorが変わり、pointerと互換性がなくなりました。
Constructorのコンパイルエラーを解消します。
・Constructor 5つ / operator=
/containers/vector.hpp
// コンストラクター
vector()
: first(NULL), last(NULL), reserved_last(NULL), alloc(allocator_type()) {}
vector(const allocator_type& alloc)
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {}
explicit vector(size_type count, const T& value = T(),
const Allocator& alloc = Allocator())
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {
resize(count, value);
}
template <typename InputIterator>
vector(InputIterator first, InputIterator last,
const Allocator& alloc = Allocator(),
typename ft::enable_if<!ft::is_integral<InputIterator>::value,
InputIterator>::type* = NULL)
: first(NULL), last(NULL), reserved_last(NULL), alloc(alloc) {
reserve(ft::distance(first, last));
for (InputIterator i = first; i != last; ++i) {
push_back(*i);
}
}
// コピー
vector(const vector& r)
: first(NULL), last(NULL), reserved_last(NULL), alloc(r.alloc) {
// コピー元の要素数を保持できるだけのストレージを確保
reserve(r.size());
// コピー元の要素をコピー構築
// destはコピー先
// [src, last)はコピー元
pointer dest = first;
for (const_iterator 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());
// 残りはコピー構築
last = first + r.size();
for (const_iterator 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 (const_iterator src_iter = r.begin(), src_end = r.end();
src_iter != src_end; ++src_iter, ++last) {
construct(last, *src_iter);
}
}
return *this;
}make test でdiffなしなので、ここまでセーブ。
https://github.com/syamashi/ft_container/tree/663c8365b98a3cb0de88c5b051c8b83078e4638e/newgame
やっとアウトラインが固まりました。もう、スムーズに実装を進められます。何か喋れそうな関数と、自作テストケースを置いておきます。
・destructor
・assign
Q. 考察
1. capacityよりも大きいcountが来た場合、capacityから作り直し。
2. そうじゃなければ、sizeを合わせる。
/containers/vector.hpp
void assign(size_type count, const T& value) {
if (count > capacity()) {
clear();
deallocate();
first = allocate(count);
last = first;
reserved_last = first + count;
for (size_type i = 0; i < count; ++i) construct(last++, value);
} else if (count > size()) {
pointer ptr = first;
for (size_type i = 0; i < count; ++i) {
if (i < size())
*(ptr++) = value;
else
construct(last++, value);
}
} else {
clear();
for (size_type i = 0; i < count; ++i) construct(last++, value);
}
}
template <class InputIt>
void assign(InputIt src_first, InputIt src_last,
typename ft::enable_if<!ft::is_integral<InputIt>::value,
InputIt>::type* = NULL) {
size_type count = src_last - src_first;
if (count > capacity()) {
clear();
deallocate();
first = allocate(count);
last = first;
reserved_last = first + count;
for (InputIt head = src_first; head != src_last; ++head)
construct(last++, *head);
} else if (count > size()) {
pointer ptr = first;
for (size_type i = 0; i < count; ++i) {
if (i < size())
*(ptr++) = *src_first++;
else
construct(last++, *src_first++);
}
} else {
clear();
for (InputIt head = src_first; head != src_last; ++head)
construct(last++, *head);
}
}・at
Q. std::out_of_range
A. atは配列外参照エラーを吐きます。
V.at(3)とV[3]は、機能は同じ。
ですが、operator[] はエラーを吐かないので、atが推奨されています？
でも、いつもV[]を使います。見やすいから。
/containers/vector.hpp
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];
}・operator[]/ front / back / data
・begin / end / rbegin / rend
・empty
・size
・max_size
max_sizeですが、定義通りに作っても環境差異が出ます。
定義パターン1
std::numeric_limits<size_type>::max() / sizeof(value_type);
定義パターン2
alloc.max_size() をかえす
実装パターン3(これを採用)
ワカモレにベタ合わせ。
参考値
vector<char> : std::numeric_limits<size_type>::max() / 2
vector<int> : std::numeric_limits<size_type>::max() / 4Q. なぜcharは2byteのサイズをとるのだろうか。
/containers/vector.hpp
size_type max_size() const {
size_t div = sizeof(value_type);
if (div == 1) ++div;
return std::numeric_limits<size_type>::max() / div;
}・reserve
・capacity
・clear
・insert（本家を見ないで挑戦）
Q. 考察
・insert(V.begin()+1, 5)
resize: {1, 2, 3, 4, 0}
| last にconstructしておく
insert: {1, 0, 2, 3, 4}
~~~~~~~ insertする場所までずらす
insert: {1, 5, 2, 3, 4}
| value入れ1. 新しいsizeがcapacityを超えるなら、新しいsizeで作り直し。
2. insert分の新しいポインタをlast以降に作る。
3. 新しいlastに、旧lastを埋めていく。
4. valueを挿入
/containers/vector.hpp
iterator insert(iterator pos, const T& value) {
size_type count = 1;
difference_type offset = pos - begin();
size_type c = capacity();
size_type pre_c = c;
size_type new_size = size() + count;
while (new_size > c) {
if (c == 0)
c = 1;
else
c = c << 1;
if ((c >> 1) != pre_c) throw std::overflow_error("vector::insert");
pre_c = c;
}
reserve(c);
for (; last != first + new_size; ++last) construct(last);
iterator tail = last - 1;
iterator range_end = begin() + offset + count - 1;
// pos + count - 1 までmemmove
for (; tail > range_end; --tail) *tail = *(tail - count);
iterator range_begin = begin() + offset - 1;
for (; tail > range_begin; --tail) *tail = value;
return begin() + offset;
}
void insert(iterator pos, size_type count, const T& value) {
if (count < 0) throw std::length_error("negative length.");
if (count == 0) return;
difference_type offset = pos - begin();
size_type c = capacity();
size_type pre_c = c;
size_type new_size = size() + count;
while (c < new_size) {
if (c == 0)
c = 1;
else
c = c << 1;
if ((c >> 1) != pre_c) throw std::overflow_error("vector::insert");
pre_c = c;
}
reserve(c);
for (; last != first + new_size; ++last) construct(last);
iterator tail = last - 1;
iterator range_end = begin() + offset + count - 1;
// pos + count - 1 までmemmove
for (; tail > range_end; --tail) *tail = *(tail - count);
iterator range_begin = begin() + offset - 1;
for (; tail > range_begin; --tail) *tail = value;
}
template <class InputIt>
void insert(iterator pos, InputIt src_first, InputIt src_last,
typename ft::enable_if<!ft::is_integral<InputIt>::value,
InputIt>::type* = NULL) {
difference_type count = src_last - src_first;
if (count < 0) throw std::length_error("negative length.");
if (count == 0) return;
difference_type offset = pos - begin();
size_type c = capacity();
size_type pre_c = c;
size_type new_size = size() + count;
while (c < new_size) {
if (c == 0)
c = 1;
else
c = c << 1;
if ((c >> 1) != pre_c) throw std::overflow_error("vector::insert");
pre_c = c;
}
reserve(c);
for (; last != first + new_size; ++last) construct(last);
iterator tail = last - 1;
iterator range_end = begin() + offset + count - 1;
// pos + count - 1 までmemmove
for (; tail > range_end; --tail) *tail = *(tail - count);
iterator range_begin = begin() + offset - 1;
--src_last;
for (; src_last > src_first - 1; --src_last) *tail-- = *src_last;
}・erase
Q. 要素がないときのerase
A. no-op？だそうです。
// The iterator first does not need to be dereferenceable if first==last:
// erasing an empty range is a no-op.
ちなみに実行すると、本家クラッシュします。no-op == 未定義かも。
私はクラッシュアレルギーなのでブロックしておきます。
Q. invalid read
A. tutorialそのままだと、src+1して、++srcしたあと、読んではいけない箇所を読んでいるかも。修正しておきます。
/containers/vector.hpp
iterator erase(iterator pos) {
// The iterator first does not need to be dereferenceable if first==last:
// erasing an empty range is a no-op.
if (first == last) return NULL;
difference_type offset = pos - begin();
for (iterator src = pos + 1; src < end(); ++src) {
*(src - 1) = *src;
}
destroy(--last);
return (begin() + offset);
}・push_back
・pop_back
・resize
・swap
普通のswapは普通に書けばいいです。
see also の std::swapへの対応もしておきます。
/containers/vector.hpp
namespace ft {
class vector {
...
void swap(vector& other) {
pointer save_first = other.first;
pointer save_last = other.last;
pointer save_reserved_last = other.reserved_last;
allocator_type save_alloc = other.alloc;
other.first = this->first;
other.last = this->last;
other.reserved_last = this->reserved_last;
other.alloc = this->alloc;
this->first = save_first;
this->last = save_last;
this->reserved_last = save_reserved_last;
this->alloc = save_alloc;
}
...
};
}; // namespace ft
namespace std {
template <class T, class Alloc>
void swap(ft::vector<T, Alloc>& lhs, ft::vector<T, Alloc>& rhs) {
lhs.swap(rhs);
}
} // namespace stdQ namespace std
A. std::swap(ft::vector, ft::vector)
を実行するときに、自作のvectorがどうswapするかを、std::swapは判断できないので、定義します。
この書き方は試行錯誤した結果。なかなかここに入らなくて苦労した。
・Non-member-functions
これですべてだと思います。
・ここまでの記録https://github.com/syamashi/ft_container/tree/2fbfd4e428f28ae62371d21a421b8ff32ffb48dd/newgame
・追記があるのは
/containers/vector.hpp
/testfiles/test_vector.cpp
/testfiles/main.cpp
void bitout(size_t n){
rep(i, 64){
cout << ((n>>(63-i))&1);
if (i%8==7) cout << " ";
}
cout << endl;
}/testfiles/tester.hpp
//// helper
void bitout(size_t n);Q. bitout
A. size_tを、64bit表示するデバッグヘルパーです。max_size_test()で使用。
次: (stack) https://note.com/syamashi/n/nbc30c2c89db4