重载时如何选择正确的矢量 insert() 函数?

Question

我正在尝试实现我自己的向量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;
}

注意：insert_test()中将dml::替换为std::，将编译和链接确定。我期望的是使用dml::编译和链接 OK 并运行与使用std::时相同的结果。

注意2：有一个类似的问题：重载分辨率如何适用于std：：vector：：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

在 @JD ługosz 的回答中，提到了一个"称为重复析构函数"，涉及new [] / delete []和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

Answer 1

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

这似乎是您必须从库容器的std::标头复制的内部帮助程序。 这不是一个标准的东西。

重载问题

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

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

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

所以，看看cpp偏好声明的内容：

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

将模板参数命名为InputIt而不是T没有任何意义;它只是一个名称。

原文中的疯狂内容，添加一个额外的未命名模板参数，是强加此约束的预概念方式。 如果你愿意，你可以阅读过时的enable_ifSFINAE在高级模板元编程中的创造性使用(我称之为ASlow Descent Into Madness)。

您的更新显示的是，当(且仅当)std::iterator_traits<InputIt>::iterator_category产生input_iterator_tag或更好的参数时，您才允许InputIt参数的类型。 即双向迭代器"isa"输入迭代器等。 (顺便说一句，C++14 中的表述会更干净一些，这让我认为这个咒语是在 C++14 之前为 C++11 写的。

如果您使用来自std::vector或std::array的迭代器测试了您的实现，它将正常工作(假设它都是正确的)。 问题不在于您的insert声明。 问题是您的VectorIterator没有为其定义任何iterator_traits，因此模板代码认为它根本不是迭代器。

<小时 />

同时...

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

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

另外，我建议使用一个"嘈杂"类来估计容器，该类记录所有构造函数和析构函数调用以及地址。