C++でvectorの実装をしていたらconstructionにとても時間がかかる
C++の勉強のために下記サイトを参考にstd::vectorのようなものを作っているのですが、最初にコンストラクタを実行するととても時間がかかってしまいます。
どうやらmyvectorで確保される領域の初期化が上手くいっていないようなのですがどうすればよいですか?
このmyvectorではmyvector<int>(10, 5)
とすると5を10個持ったものを生成します。
初期化の際にresize(num, value)を使って値を構築するのですが、このresize内で現在の要素数を取得するときに実行されるsize()(現在の要素数を取得するメソッド)の結果がなぜかとても大きい値を返してきます。
size()は確保した領域の先頭(first)と末尾(last)のアドレスの差を返しているだけの実装になっています。
デバッガを使ってresize()内でsize()を実行してみると14445543(適当)などのとても大きい数値が帰ってきてしまいます。
そこでmyvectorで領域が確保される前まではとりあえずlast - firstを0にしたいのですが、初期値としてどのような値を設定するのが一般的なのでしょうか?
参考サイト: 江添亮のC++入門
myvectorのコード:
#include <iostream>
#include <boost/scope_exit.hpp>
template < typename T, typename Allocator = std::allocator<T> >
class myvector {
public:
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>;
private:
using traits = std::allocator_traits<allocator_type>;
pointer first = nullptr;
pointer last = nullptr;
pointer reserved_last;
allocator_type alloc;
pointer allocate(size_type n);
void deallocate();
void construct(pointer ptr);
void construct(pointer ptr, const_reference value);
void construct(pointer ptr, value_type&& value);
void destroy(pointer ptr);
void destroy_until(reverse_iterator rend);
void clear() noexcept;
public:
myvector(size_type size, const allocator_type& alloc = allocator_type());
myvector(size_type size, const_reference value, const allocator_type& alloc = allocator_type());
myvector();
myvector(const allocator_type& alloc) noexcept;
~myvector();
myvector(const myvector& x);
myvector& operator=(const myvector& x);
void push_back(const T& x);
reference operator[](std::size_t i) noexcept;
const_reference operator[](std::size_t i) const noexcept;
reference at(std::size_t i) noexcept;
const_reference at(std::size_t i) const noexcept;
reference front();
reference back();
const_reference front() const;
const_reference back() const;
pointer data() noexcept;
const_pointer data() const noexcept;
iterator begin() noexcept;
iterator end() noexcept;
iterator begin() const noexcept;
iterator end() const noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;
reverse_iterator rbegin() noexcept;
reverse_iterator rend() noexcept;
const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;
size_type size() const noexcept;
bool empty() const noexcept;
size_type capacity() const noexcept;
void resize(size_type sz);
void resize(size_type sz, const_reference value);
void reserve(size_type sz);
};
// private methods
template < typename T, typename Allocator>
typename myvector<T, Allocator>::pointer myvector<T, Allocator>::allocate(typename myvector<T, Allocator>::size_type n) {
return traits::allocate(alloc, n);
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::deallocate() {
traits::deallocate(alloc, first, capacity());
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::construct(typename myvector<T, Allocator>::pointer ptr) {
traits::construct(alloc, ptr);
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::construct(typename myvector<T, Allocator>::pointer ptr, typename myvector<T, Allocator>::const_reference value) {
traits::construct(alloc, ptr, value);
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::construct(typename myvector<T, Allocator>::pointer ptr, typename myvector<T, Allocator>::value_type&& value) {
traits::construct(alloc, ptr, std::move(value));
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::destroy(typename myvector<T, Allocator>::pointer ptr) {
traits::destroy(alloc, ptr);
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::destroy_until(typename myvector<T, Allocator>::reverse_iterator rend) {
for (auto riter = rbegin(); riter != rend; ++riter, --last) {
destroy(&*riter);
}
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::clear() noexcept {
destroy_until(rend());
}
// public methods
template < typename T, typename Allocator>
myvector<T, Allocator>::~myvector() {
clear();
deallocate();
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::iterator myvector<T, Allocator>::begin() noexcept {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::iterator myvector<T, Allocator>::end() noexcept {
return last;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::iterator myvector<T, Allocator>::begin() const noexcept {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::iterator myvector<T, Allocator>::end() const noexcept {
return last;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_iterator myvector<T, Allocator>::cbegin() const noexcept {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_iterator myvector<T, Allocator>::cend() const noexcept {
return last;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reverse_iterator myvector<T, Allocator>::rbegin() noexcept {
return reverse_iterator{last};
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reverse_iterator myvector<T, Allocator>::rend() noexcept {
return reverse_iterator{first};
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reverse_iterator myvector<T, Allocator>::crbegin() const noexcept {
return const_reverse_iterator{last};
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reverse_iterator myvector<T, Allocator>::crend() const noexcept {
return const_reverse_iterator{first};
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::size_type myvector<T, Allocator>::size() const noexcept {
return end() - begin();
}
template < typename T, typename Allocator>
bool myvector<T, Allocator>::empty() const noexcept {
return begin() == end();
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reference myvector<T, Allocator>::operator[](std::size_t i) noexcept {
return first[i];
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reference myvector<T, Allocator>::operator[](std::size_t i) const noexcept {
return first[i];
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reference myvector<T, Allocator>::at(std::size_t i) noexcept {
if (i >= size()) {
throw std::out_of_range("index is out of range");
}
return first[i];
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reference myvector<T, Allocator>::at(std::size_t i) const noexcept {
if (i >= size()) {
throw std::out_of_range("index is out of range");
}
return first[i];
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reference myvector<T, Allocator>::front() {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::reference myvector<T, Allocator>::back() {
return last - 1;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reference myvector<T, Allocator>::front() const {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_reference myvector<T, Allocator>::back() const {
return last - 1;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::pointer myvector<T, Allocator>::data() noexcept {
return first;
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::const_pointer myvector<T, Allocator>::data() const noexcept {
return first;
}
template < typename T, typename Allocator>
myvector<T, Allocator>::myvector(const myvector<T, Allocator>::allocator_type& alloc) noexcept : alloc(alloc) {};
template < typename T, typename Allocator>
myvector<T, Allocator>::myvector() : myvector(myvector<T, Allocator>::allocator_type()) {};
template < typename T, typename Allocator>
myvector<T, Allocator>::myvector(typename myvector<T, Allocator>::size_type size, const typename myvector<T, Allocator>::allocator_type& alloc) : myvector(alloc) {
resize(size);
};
template < typename T, typename Allocator>
myvector<T, Allocator>::myvector(myvector<T, Allocator>::size_type size,
myvector<T, Allocator>::const_reference value,
const myvector<T, Allocator>::allocator_type& alloc) : myvector(alloc) {
resize(size, value);
};
template < typename T, typename Allocator>
void myvector<T, Allocator>::reserve(typename myvector<T, Allocator>::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;
BOOST_SCOPE_EXIT_ALL(&, this) {
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);
}
}
template < typename T, typename Allocator>
typename myvector<T, Allocator>::size_type myvector<T, Allocator>::capacity() const noexcept {
return reserved_last - first;
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::resize(myvector<T, Allocator>::size_type sz) {
if (sz < size()) {
std::size_t diff = size() - sz;
destroy_until(rbegin() + diff);
last = first + diff;
}
else if (sz > size()) {
reserve(sz);
for (; last != reserved_last; ++last) {
construct(last);
}
}
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::resize(myvector<T, Allocator>::size_type sz, const_reference value) {
if (sz < size()) {
std::size_t diff = size() - sz;
destroy_until(rbegin() + diff);
last = first + sz;
}
else if (sz > size()) {
reserve(sz);
for (; last != reserved_last; ++last) {
construct(last, value);
}
}
}
int main() {
myvector<int> v(10, 1);
v[2] = 99;
v.resize(5);
}