3

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());

}
2
  • エラー内容を記載しませんか?
    – sayuri
    Commented 2019年11月24日 13:04
  • とても大事なのに忘れていました 記載しました Commented 2019年11月24日 13:10

2 件の回答 2

2

根本的な原因は、イテレータを引数に取るコンストラクタが、イテレータ以外のものまで受け付けてしまうことです。

エラーメッセージを見てみると、main()の中のmyvector<int> v(10, 1);がエラーのもともとの始まりです。

int main() {
    myvector<int> v(10, 1);

コンパイラは、このvを定義した行を、イテレータを二つ与えたコンストラクタとして解釈していますが、どうみても、10と1はイテレータではないので、これはmyvector(size_type size, const_reference value, const allocator_type& alloc = allocator_type());を使おうとしたもの、つまりベクターのサイズと初期値を指定したコンストラクタを使うつもりだったと思います。

(以下、簡単のため、デフォルトの値を持つ引数は無視します)

下のコードは、意図したはずのコンストラクタと、実際に呼ばれたコンストラクタを抜粋したものです。

    using size_type = std::size_t;

    myvector(size_type size, const_reference value);

    template < typename InputIterator>
    myvector(InputIterator first, InputIterator last);

呼び出し側のコードを見てみると、実引数はどちらもsigned intです。

int main() {
    myvector<int> v(10, 1);

しかし、意図したコンストラクタの最初の引数はsize_type、つまりunsignedなので、厳密には型が一致しません。一方、イテレータを指定するコンストラクタの方は、テンプレート引数が<typename InputIterator>で、名前こそInputIteratorですが、実際には任意のデータ型と一致します。

つまり、コンパイラは、テンプレートではないコンストラクタで完全一致するものが見つけられなかったため、テンプレートのコンストラクタから完全一致するものを選択したわけです。実際、

int main() {
    myvector<int> v(10u, 1);

と、最初の引数をunsignedにすれば、目的のコンストラクタが使われ、エラーは出ません。

このままだと不便ですし、予想外のエラーが起きる可能性があるので、イテレータを取るコンストラクタは、実引数が実際にイテレータでない場合は、実体化されないようにしたいところですが、なかなかに面倒でしょう。標準のライブラリと一緒に使えるようにするには、std::enable_ifstd::iterator_traitsなどを駆使する必要がありそうです。


追記

ちょっと試してみました。イテレータとして使えない型Tの場合、std::iterator_traits<T>は、何もメンバを持ちません。これを利用して、コンストラクタの宣言の方を

template < typename InputIterator, typename = typename std::iterator_traits<InputIterator>::value_type>
myvector(InputIterator first, InputIterator last, const Allocator & = Allocator());

とし、実際の定義の方を

template < typename T, typename Allocator >
template < typename InputIterator, typename>
myvector<T, Allocator>::myvector(InputIterator first, InputIterator last, const Allocator&) {
    // 以下、実際のコード

とすれば、うまくいきそうです。ただし、あまりテストはしていません。


再追記
新しいコードでのエラーは、単に宣言の三番目の仮引数にデフォルトの値を与えてないので、実引数が二つの場合に一致していないだけです。

    template < typename InputIterator>
    myvector(InputIterator first, InputIterator last, const Allocator& = allocator_type(), 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();
3
  • std::enable_if<std::is_base_of<std::input_iterator_tag,std::iterator_traits<InputIterator>::iterator_category>::value>::typeを使うのでしょうか 実際にどうやるかはわからないのですが、 やることとしては (InputIteratorのitetator_categoryをみてstd::input_iterator_tagを継承していたらイテレーターを取るコンストラクタを実体化する)ということでしょうか? Commented 2019年11月25日 1:28
  • @KiYugadgeter すこし試したコードを追加しました。これを参考にしてください。
    – Hideki
    Commented 2019年11月25日 2:39
  • @KiYugadgeter 質問を少しずつ修正してダラダラ続けるのはあまりよくないと思いますが、とりあえず回答に追加しました。
    – Hideki
    Commented 2019年11月26日 4:06
1

もしかするとテンプレートの推論で失敗しているのかもしれません。

下記エラーメッセージが示唆している通り、望まないテンプレート型推論 InputIterator = int が行われています。読みやすさのため変形引用します。

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);
                  ^
.../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)
    ^

直接のエラー原因は、下記テンプレートコンストラクタの存在です。std::vector<T>コンテナ設計を参考にされたと推測しますが、C++標準ライブラリのインタフェースを “文字通り” 定義してしまうとこの落とし穴にはまります。

template <typename InputIterator>
myvector(InputIterator first, InputIterator last, const Allocator& = Allocator());

std::vectorクラステンプレートは確かに同一シグニチャのテンプレートコンストラクタを宣言するのですが、実際には「テンプレートパラメータInputIteratorが入力イテレータ(input itererator)要件を満たすときに限る」という条件付きとなっています。C++17 [sequence.reqmts]/paragraph 13にある "participate in overload resolution" という言い回しが該当します。

If the constructor

template <class InputIterator>
 X(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

is called with a type InputIterator that does not qualify as an input iterator, then the constructor shall not participate in overload resolution.

C++標準ライブラリ仕様は「プログラマ向けの外部公開インタフェース」を定めますが、前述のように追加要件が課せられるケースが存在するため、標準ライブラリ内部実装としてはSFINAE用のテンプレートパラメータや関数パラメータが追加されるケースがあります。(このような内部実装は明示的に許容されています。)

例えば libstdc++-v3 標準ライブラリ実装では、std::vectorの該当テンプレートコンストラクタにはSFINAE用の隠れたテンプレート引数が存在します。

また別の標準ライブラリ実装 libcxx では、該当コンストラクタにSFINAE用の隠れたデフォルト引数が追加されています。


コメント:libc++の実装でenable_if内がfalseになった場合はどうなるのでしょうか? そもそもtemplateが満たされないのでこのコンストラクタは実体化されないということですか?

enable_if<false>::typeは定義されないため、SFINAE(Substitution Failure Is Not An Error)規則により該当コンストラクタの実体化は行われません。


追記質問:libc++の実装を参考に宣言と定義の先頭を以下のようにして、std::vectorのイテレーターからコンストラクトしようとしたところをエラー2のようなエラーが出ます。

変更差分が断片的なため不確かですが、試した限りでは問題なくコンパイルできました。追加箇所をコメント///で囲っていますので、差分ご確認ください。
https://wandbox.org/permlink/n45mhgv8i8beLveI

2
  • libc++の実装でenable_if内がfalseになった場合はどうなるのでしょうか? そもそもtemplateが満たされないのでこのコンストラクタは実体化されないということですか? Commented 2019年11月25日 13:54
  • イテレーターからのコンストラクタを呼び出してみたところ新たなエラーがでました。ここに書くのは長くなるので質問に追記しました。 Commented 2019年11月25日 16:19

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。