时间戳

首页 > 解决方案 > 重载时如何选择正确的向量插入（）函数？

c++ - 重载时如何选择正确的向量插入（）函数？

问题描述

我正在尝试实现我自己的向量dml::vector，其 API 与std::vector. 让我感到困惑的是insert()函数的重载分辨率。

我想致电：

template<class InputIt>
void insert(iterator pos, InputIt first, InputIt last)

但因编译或链接错误而失败。

只是删除了不必要的代码以保持简单，关键代码是：

        template<class InputIt, typename = std::_RequireInputIter<InputIt>> // no matching member function for call to 'insert'
        //template<class InputIt> //undefined reference to `dml::operator+(dml::VectorIterator<dml::vector<int> > const&, unsigned long)
        void insert(iterator pos, InputIt first, InputIt last)
        {
            std::cout << "----- 3" << std::endl;
        }

完整的代码是：

#include <new>
#include <string.h>
#include <stdlib.h>
#include <stdexcept>
#include <iostream>

namespace dml
{
    template<typename T>
    void create_memory(T** data, std::size_t num_elem) {
        *data = static_cast<T*>(operator new[](sizeof(T) * num_elem));
    }

    template<typename T>
    void destroy_memory(T* data, std::size_t num_elem) {
        for (std::size_t i=0; i<num_elem; i++) {
            data[i].~T();
        }
        operator delete[](data);
    }

    template<typename vector_type>
    class VectorIterator
    {
    public:
        using ValueType = typename vector_type::value_type;
        using PointerType = ValueType*;
        using ReferenceType = ValueType&;
        using DifferenceType = std::size_t;
    public:
        VectorIterator(PointerType ptr): ptr_(ptr) {}

        VectorIterator& operator ++ () {
            ptr_ ++;
            return *this;
        }

        VectorIterator operator ++ (int) {
            VectorIterator iterator = *this;
            ptr_ ++;
            return iterator;
        }

        VectorIterator& operator -- () {
            ptr_ --;
            return *this;
        }

        VectorIterator operator -- (int) {
            VectorIterator iterator = *this;
            ptr_ --;
            return iterator;
        }

        bool operator == (const VectorIterator& other) {
            return ptr_ == other.ptr_;
        }

        bool operator != (const VectorIterator& other) {
            return ptr_ != other.ptr_;
        }

        ValueType& operator * () {
            return *ptr_;
        }

    private:
        PointerType ptr_;

        template <typename T>
        friend class vector;

        friend VectorIterator<vector_type> operator + (const VectorIterator<vector_type>& lhs, size_t count);
    };

    template <typename vector_type>
    VectorIterator<vector_type> operator + (const VectorIterator<vector_type>& lhs, size_t count)
    {
        return VectorIterator<vector_type>(lhs.ptr_ + count);
    }


    template <typename T>
    class vector {
    public:
        using size_type = std::size_t;
        using value_type = T;
        using reference = value_type&;
        using const_reference = const value_type&;
        using iterator = VectorIterator<vector<T>>;
        using const_iterator = const VectorIterator<vector<T>>;
        using reverse_iterator = VectorIterator<vector<T>>;
        
    public:
        vector(): size_(0), capacity_(0), data_(nullptr) {}

        vector(size_type count, const T& value = T())
            : size_(count), capacity_(count)
        {
            create_memory(&data_, size_);
            for (size_type i=0; i<size_; i++) {
                new (&data_[i]) T (value);
            }
        }

        //! braced-init-list
        vector(std::initializer_list<T> init): size_(init.size()), capacity_(init.size())
        {
            create_memory(&data_, size_);
            typename std::initializer_list<T>::iterator it = init.begin();
            for (size_type i=0; i<size_; i++) {
                new (&data_[i]) T (*it);
                it ++;
            }
        }

        //! cpoy constructor
        vector(const vector& v): size_(v.size_), capacity_(v.capacity_) {
            create_memory(&data_, size_);
            for (size_type i=0; i<size_; i++) {
                new (&data_[i]) T (v.data_[i]);
            }
        }

        ~vector() {
            if (data_!=nullptr) {
                for (int i=0; i<size_; i++) {
                    data_[i].~T();
                }
                operator delete[](data_);
            }
        }

        T& operator [] (size_type pos) {
            return data_[pos];
        }

        const T& operator [] (size_type pos) const {
            return data_[pos];
        }


        ///////////////////// Iterators //////////////////
        iterator begin() noexcept {
            return iterator(data_);
        }

        const_iterator begin() const noexcept {
            return const_iterator(data_);
        }

        iterator end() noexcept {
            return iterator(data_ + size_);
        }

        const_iterator end() const noexcept {
            return const_iterator(data_ + size_);
        }

        size_type size() const {
            return size_;
        }

        size_type capacity() const {
            return capacity_;
        }

        iterator insert(iterator pos, const T& value)
        {
            std::cout << "----- 1" << std::endl;
            return insert(pos, static_cast<size_type>(1), value);
        }

        iterator insert(iterator pos, size_type count, const T& value)
        {
            std::cout << "----- 2" << std::endl;
            iterator it(0);
            return it;
        }

        template<class InputIt, typename = std::_RequireInputIter<InputIt>> // no matching member function for call to 'insert'
        //template<class InputIt> //undefined reference to `dml::operator+(dml::VectorIterator<dml::vector<int> > const&, unsigned long)
        void insert(iterator pos, InputIt first, InputIt last)
        {
            std::cout << "----- 3" << std::endl;
        }

    private:
        size_type size_; // actual size
        size_type capacity_; // actual capacity
        T* data_;
    };

    template<class T>
    bool operator== (const dml::vector<T>& lhs, const dml::vector<T>& rhs)
    {
        if (lhs.size()!=rhs.size()) return false;
        for (size_t i=0; i<lhs.size(); i++) {
            if (lhs[i]!=rhs[i]) return false;
        }
        return true;
    }
}



template<class T>
std::ostream & operator << (std::ostream & os, const dml::vector<T>& v)
{
    for (int i=0; i<v.size(); i++) {
        os << v[i] << ", ";
    }
    os << std::endl;
    return os;
}

#include <vector>

template<class T>
std::ostream & operator << (std::ostream & os, const std::vector<T>& v)
{
    for (int i=0; i<v.size(); i++) {
        os << v[i] << ", ";
    }
    os << std::endl;
    return os;
}

static void insert_test()
{
    std::cout << "---- insert test" << std::endl;
    dml::vector<int> vec(3,100);
    std::cout << vec;

    auto it = vec.begin();
    it = vec.insert(it, 200);
    std::cout << vec;

    vec.insert(it,2,300);
    std::cout << vec;

    // "it" no longer valid, get a new one:
    it = vec.begin();
 
    dml::vector<int> vec2(2,400);
    vec.insert(it+2, vec2.begin(), vec2.end()); // ! this line cause compile/link error
    std::cout << vec;
 
    int arr[] = { 501,502,503 };
    vec.insert(vec.begin(), arr, arr+3);
    std::cout << vec;
}

int main()
{
    insert_test();

    return 0;
}

注意：替换dml::为std::in insert_test()，将编译并链接正常。我期望的是使用dml::compile & link OK 并运行与使用std::.

注2：有一个类似的问题：重载解析如何为 std::vector<int>::insert 工作，但我不太明白人们对enable_if. 只是使用我的代码，我该如何修改它？

更新

正如答案和评论中提到的，std::_RequireInputIter似乎没有正确使用。我也试过自己写一个：

        template <typename InputIterator>
        using RequireInputIterator = typename std::enable_if<
        std::is_convertible<typename std::iterator_traits<InputIterator>::iterator_category, 
                    std::input_iterator_tag
                    >::value
            >::type;


        //template<class InputIt, typename = std::_RequireInputIter<InputIt>>
        template<class InputIt, typename = RequireInputIterator<InputIt>>
        void insert(iterator pos, InputIt first, InputIt last)
        {
           ...
        }

但这仍然导致重载解析失败。

更新 2

new [] / delete []在@JDługosz 的回答中，提到并operator new[] / operator delete[]涉及了“称为重复的析构函数” 。让我提供这个简单的片段来证明我的观点：operator new[]只分配内存，不会调用构造函数，并且与new[].

这是代码：

#include <iostream>

int main() {
    {
        std::cout << "--- begin of case 1" << std::endl;
        Entity* p = static_cast<Entity*>(operator new[](sizeof(Entity)*10));
        std::cout << "--- end of case 1" << std::endl;
    }

    std::cout << std::endl;

    {
        std::cout << "--- begin of case 2" << std::endl;
        Entity* q = new Entity[10];
        std::cout << "--- end of case 2" << std::endl;
    }

    return 0;
}

这是输出（x64 ubuntu 20.04，clang 10.0）：

--- begin of case 1
--- end of case 1

--- begin of case 2
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- Entity()
--- end of case 2

标签： c++overload-resolution

解决方案

我认为问题在于检查VectorIterator不知道您的类型是迭代器std::_RequireInputIter。因此，通过该检查，它不会使用该模板。

这似乎是您必须从std::库容器的标题中复制的内部助手。这不是标准的东西。

超载问题

考虑模板成员函数的基本 C++11 签名：

template <typename T> void insert (iterator pos, T first, T last)

这是为了处理任何一对迭代器而实现的，但没有任何东西告诉编译器只有某些类型可以在T这里使用。现在模板参数推导使其变得贪婪，因此任何对x.insert(pos, a,b);wherea和bare 相同类型的调用都会导致此表单是完全匹配的，因此即使您打算 a成为一个计数并b成为一个值，它也会被采用。当您有一些简单数字类型的向量（或具有采用单个数字参数的构造函数的向量等）时，这是一个问题。

所以，看看cppreference状态：

InputIt此重载仅在符合条件时才参与重载解析LegacyInputIterator，以避免与重载 (3) 产生歧义。

命名模板参数InputIt而不是T没有任何意义；这只是一个名字。

您原来的疯狂的东西，添加一个额外的未命名模板参数，是一种施加此约束的概念前方法。如果您愿意，您可以阅读过时enable_if的 SFINAE 在高级模板元编程中的创造性使用（我称之为A Slow Descent Into Madness）。

您的更新显示的是，InputIt当（且仅当）std::iterator_traits<InputIt>::iterator_category产生input_iterator_tag 或更好时，您允许参数的类型。也就是说，双向迭代器“isa”输入迭代器等（顺便说一句，这个公式在 C++14 中会更清晰一些，这让我觉得这个咒语是在 C++14 之前为 C++11 编写的。）

如果您使用 a std::vectoror的迭代器测试您的实现std::array，它会工作得很好（假设它都是正确的）。问题不在于您的insert. 问题是你VectorIterator没有iterator_traits为它定义任何东西，所以模板代码认为它根本不是迭代器。

同时...

for (size_t i=0; i<lhs.size(); i++) {
if (lhs[i]!=rhs[i]) return false;

只需使用std::equal并且不要使用您自己的循环重新实现标准算法。

此外，我建议使用“嘈杂”类对容器进行测试，该类记录所有构造函数和析构函数调用以及地址。

推荐阅读