60821


C++の勉強のためにvectorのようなものを作っています。  
iteratorを使ったコンストラクタ(firstとlastを取り、その間の値をvectorに構築する)を書いているのですがエラーになります。  
なぜでしょうか?

確保するメモリのサイズを調べるためにstd::distanceを使っているのですがそのあたりでエラーが発生しています。  
もしかするとテンプレートの推論で失敗しているのかもしれません。  
どうすればよいのでしょうか?  
ちなみにC++17を使用しています。

iteratorを使ったコンストラクタの実装(下記の自作vectorの一部分)

[code]

    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);
        }
    }
    
[/code]

エラー内容

[code]

    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.
    
[/code]

* * *

自作vectorのコード:

[code]

    #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;
        }
    }
    
[/code]

* * *

### 追記

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

エラー2

[code]

    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();
        ^
    
[/code]

コンストラクタの宣言(変更後):

[code]

    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); 
    
[/code]

コンストラクタの定義の一部(変更後)

[code]

    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*) {
    
[/code]

エラーが出たコード:

[code]

    int main() {
        std::vector vec(3, 2);
        myvector<int> v2(vec.begin(), vec.end());
    
    }
    
[/code]


CC BY-SA 4.0
2019-11-24T10:09:33.703
60807
2019-11-26T04:04:34.307
2019-11-25T16:17:40.480
5246
5246
question
c++
C++のvectorの実装でイテレーターを使ったコンストラクタを書いたのだがエラーになる


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

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

[code]

    int main() {
        myvector<int> v(10, 1);
    
[/code]

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

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

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

[code]

        using size_type = std::size_t;
    
        myvector(size_type size, const_reference value);
    
        template < typename InputIterator>
        myvector(InputIterator first, InputIterator last);
    
[/code]

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

[code]

    int main() {
        myvector<int> v(10, 1);
    
[/code]

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

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

[code]

    int main() {
        myvector<int> v(10u, 1);
    
[/code]

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

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

* * *

追記

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

[code]

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

とし、実際の定義の方を

[code]

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

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

* * *

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

[code]

        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();
    
[/code]


CC BY-SA 4.0
2019-11-24T23:13:37.080
60810
2019-11-26T04:04:34.307
2019-11-26T04:04:34.307
3605
3605
60807
answer


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

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

>
[code]

>     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)
>         ^
>  
[/code]

* * *

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

>
[code]

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

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

> If the constructor
[code]

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

>
> 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用のテンプレートパラメータや関数パラメータが追加されるケースがあります。（このような内部実装は[明示的に許容](https://timsong-
cpp.github.io/cppwp/n4659/library#member.functions-2)されています。）

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

  * <https://github.com/gcc-mirror/gcc/blob/b0b4c933b4f5d0bbeff77523ddd69ac597ba8045/libstdc%2B%2B-v3/include/bits/stl_vector.h#L648-L656>

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

  * <https://github.com/llvm-mirror/libcxx/blob/78d6a7767ed57b50122a161b91f59f19c9bd0d19/include/vector#L527-L533>

* * *

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

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

* * *

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

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


CC BY-SA 4.0
2019-11-25T07:41:53.340
60821
2019-11-26T02:34:51.093
2019-11-26T02:34:51.093
49
49
60807
answer