C++のvectorの実装でイテレーターを使ったコンストラクタを書いたのだがエラーになる
C++の勉強のためにvectorのようなものを作っています。
iteratorを使ったコンストラクタ(firstとlastを取り、その間の値をvectorに構築する)を書いているのですがエラーになります。
なぜでしょうか?
確保するメモリのサイズを調べるためにstd::distanceを使っているのですがそのあたりでエラーが発生しています。
もしかするとテンプレートの推論で失敗しているのかもしれません。
どうすればよいのでしょうか?
ちなみにC++17を使用しています。
iteratorを使ったコンストラクタの実装(下記の自作vectorの一部分)
template < typename T, typename Allocator >
template < typename InputIterator >
myvector<T, Allocator>::myvector(InputIterator first, InputIterator last, const Allocator&) {
reserve(std::distance(first, last));
for (auto i = first; i != last; ++i) {
push_back(*i);
}
}
エラー内容
myvector.cpp:330:13: error: no matching function for call to 'distance'
reserve(std::distance(first, last));
^~~~~~~~~~~~~
myvector.cpp:337:19: note: in instantiation of function template specialization 'myvector<int, std::allocator<int> >::myvector<int>' requested here
myvector<int> v(10, 1);
^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_iterator_base_funcs.h:138:5: note: candidate template ignored: substitution failure [with _InputIterator = int]: no type named 'difference_type' in 'std::iterator_traits<int>'
distance(_InputIterator __first, _InputIterator __last)
^
myvector.cpp:332:19: error: indirection requires pointer operand ('int' invalid)
push_back(*i);
^~
2 errors generated.
自作vectorのコード:
#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 = nullptr;
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;
template < typename InputIterator>
myvector(InputIterator first, InputIterator last, const Allocator& = Allocator());
~myvector();
myvector(const myvector& x);
myvector& operator=(const myvector& 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);
void push_back(const_reference value);
void shrink_to_fit();
};
// 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);
}
}
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::push_back(typename myvector<T, Allocator>::const_reference value) {
if (size() + 1 > capacity()) {
size_t s = size();
if (s == 0) {
s = 1;
}
reserve(s * 2);
}
construct(last, value);
++last;
}
template < typename T, typename Allocator>
void myvector<T, Allocator>::shrink_to_fit() {
if (capacity() == size()) {
return;
}
auto current_size = size();
auto ptr = allocate(current_size());
for (auto raw_ptr = ptr, iter = begin(), iter_end = end(); iter != iter_end; ++iter, ++raw_ptr) {
construct(raw_ptr, *iter);
}
clear();
deallocate();
first = ptr;
last = first + current_size;
reserved_last = last;
}
template < typename T, typename Allocator >
template < typename InputIterator >
myvector<T, Allocator>::myvector(InputIterator first, InputIterator last, const Allocator&) {
reserve(std::distance(first, last));
for (auto i = first; i != last; ++i) {
push_back(*i);
}
}
int main() {
myvector<int> v(10, 1);
v[2] = 99;
v.resize(5);
v.push_back(33);
for (auto &s: v) {
std::cout << s << std::endl;
}
}
追記
libc++の実装を参考に宣言と定義の先頭を以下のようにして、std::vectorのイテレーターからコンストラクトしようとしたところをエラー2のようなエラーが出ます。なぜでしょうか?
エラー2
myvector.cpp:338:19: error: no matching constructor for initialization of 'myvector<int>'
myvector<int> v(v2.begin(), v2.end());
^ ~~~~~~~~~~~~~~~~~~~~
myvector.cpp:33:9: note: candidate constructor not viable: no known conversion from 'std::vector<int, std::allocator<int> >::iterator' (aka '__normal_iterator<int *, std::vector<int, std::allocator<int> > >') to 'myvector::size_type' (aka 'unsigned long') for 1st argument
myvector(size_type size, const allocator_type& alloc = allocator_type());
^
myvector.cpp:34:9: note: candidate constructor not viable: no known conversion from 'std::vector<int, std::allocator<int> >::iterator' (aka '__normal_iterator<int *, std::vector<int, std::allocator<int> > >') to 'myvector::size_type' (aka 'unsigned long') for 1st argument
myvector(size_type size, const_reference value, const allocator_type& alloc = allocator_type());
^
myvector.cpp:38:9: note: candidate constructor template not viable: requires at least 3 arguments, but 2 were provided
myvector(InputIterator first, InputIterator last, const Allocator&, typename std::enable_if<std::is_base_of<typename std::input_iterator_tag, typename std::iterator_traits<InputIterator>::iterator_category>::value, typename std::iterator_traits<InputIterator>::value_type>::type* = nullptr);
^
myvector.cpp:36:9: note: candidate constructor not viable: requires single argument 'alloc', but 2 arguments were provided
myvector(const allocator_type& alloc) noexcept;
^
myvector.cpp:40:9: note: candidate constructor not viable: requires single argument 'x', but 2 arguments were provided
myvector(const myvector& x);
^
myvector.cpp:35:9: note: candidate constructor not viable: requires 0 arguments, but 2 were provided
myvector();
^
コンストラクタの宣言(変更後):
template < typename InputIterator>
myvector(InputIterator first, InputIterator last, const Allocator&, typename std::enable_if<std::is_base_of<typename std::input_iterator_tag, typename std::iterator_traits<InputIterator>::iterator_category>::value, typename std::iterator_traits<InputIterator>::value_type>::type* = nullptr);
コンストラクタの定義の一部(変更後)
template < typename T, typename Allocator >
template < typename InputIterator >
myvector<T, Allocator>::myvector(InputIterator first, InputIterator last, const Allocator&, typename std::enable_if<std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<InputIterator>::iterator_category>::value, typename std::iterator_traits<InputIterator>::value_type>::type*) {
エラーが出たコード:
int main() {
std::vector vec(3, 2);
myvector<int> v2(vec.begin(), vec.end());
}