自己的向量分配实现 [英] Own vector assign implementation
问题描述
我正在通过编写所有默认函数来实现像向量一样的 stl.并且有一个问题，我不明白为什么它为简单类型调用 ragne 版本的assign 并且不默认.下面是实现代码:向量.h
void assign(size_t count, const T& value){//默认版本无效分配(size_t 计数，const T& 值){if(this->_size allocator.deallocate(this->arr, this->_capacity);this->arr = this->allocator.allocate(count);this->_capacity = count;}for(size_t i = 0; i < count; ++i)this->arr[i] = 值；这-> _size = 计数；}模板void assign(InputIt first, InputIt last){//范围版本size_t count = std::distance(first,last);if(this->_size allocator.deallocate(this->arr, this->_capacity);this->arr = this->allocator.allocate(count);this->_capacity = count;}for(size_t i = 0;第一个!=最后一个;i++)this->arr[i] = *first++;这-> _size = 计数；} 主要代码:
Vectorvec;vec.assign(5,10); 输出:
<预><代码>/MyVector/MyVector.h: 在实例化‘void Vector我使用的是 C++17
范围版本更适合 vec.assign(5, 10); 和 InputIt = int代码>.您应该以某种方式禁用不代表输入迭代器的模板参数的重载.
我们来看看stdlibc++ 实现:
template>无效分配(首先输入，最后输入){M_assign_dispatch(第一个，最后一个)；} where RequireInputIter 是
template使用 RequireInputIter = typename enable_if::iterator_category, input_iterator_tag>::value>::type; 换句话说，对于推导的类型InputIt，iterator_traits 类型应该可以转换为input_iterator_tag.否则，由于 SFINAE.
在 C++17 中，RequireInputIter 可以通过 _t 和 _v 助手来简化:
template使用 RequireInputIter = enable_if_t <小时>
另请注意，输入迭代器可用于遍历范围仅一次.在您调用 std::distance(first, last) 之后，除非 InputIt 至少是一个前向迭代器，否则所有后续遍历该范围的尝试都是未定义的行为.对于输入迭代器，您无法确定要预分配多少空间.
这就是 assign 在内部使用标签调度技术的原因.经过一些简化，它看起来像这样:
template>无效分配(首先输入，最后输入){M_assign_aux(第一个，最后一个，typename iterator_traits::iterator_category{});} 有两个 M_assign_aux 重载
templatevoid M_assign_aux(先输入，最后输入，std::input_iterator_tag);模板void M_assign_aux(先转发，最后转发，std::forward_iterator_tag); 完成任务.第一个将仅用于输入迭代器，第二个用于前向迭代器及其派生的迭代器，即双向和随机访问迭代器.
I'm implementing stl like vector with writing all default functions. And there is a problem that I don't understand why It calls ragne version of assign for simple types and doesn't default. Here is the implementation code: Vector.h
void assign(size_t count, const T& value){ // Default version
void assign(size_t count, const T& value){
if(this->_size < count){
this->allocator.deallocate(this->arr, this->_capacity);
this->arr = this->allocator.allocate(count);
this->_capacity = count;
}
for(size_t i = 0; i < count; ++i)
this->arr[i] = value;
this->_size = count;
}
template<class InputIt>
void assign(InputIt first, InputIt last){ // Range version
size_t count = std::distance(first,last);
if(this->_size < count){
this->allocator.deallocate(this->arr, this->_capacity);
this->arr = this->allocator.allocate(count);
this->_capacity = count;
}
for(size_t i = 0; first != last; i++)
this->arr[i] = *first++;
this->_size = count;
}
Main code:
Vector<int> vec;
vec.assign(5,10);
Output:
/MyVector/MyVector.h: In instantiation of ‘void Vector<T, Allocator>::assign(InputIt, InputIt) [with InputIt = int; T = int; Allocator = std::allocator]’:
../MyVector/main.cpp:52:24: required from here
../MyVector/MyVector.h:99:45: error: no matching function for call to ‘distance(int&, int&)’
size_t count = std::distance(first,last);
~~~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from ../MyVector/main.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:138:5: note: candidate: template<class _InputIterator> constexpr typename std::iterator_traits<_Iterator>::difference_type std::distance(_InputIterator, _InputIterator)
distance(_InputIterator __first, _InputIterator __last)
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:138:5: note: template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h: In substitution of ‘template<class _InputIterator> constexpr typename std::iterator_traits<_Iterator>::difference_type std::distance(_InputIterator, _InputIterator) [with _InputIterator = int]’:
../MyVector/MyVector.h:99:45: required from ‘void Vector<T, Allocator>::assign(InputIt, InputIt) [with InputIt = int; T = int; Allocator = std::allocator]’
../MyVector/main.cpp:52:24: required from here
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:138:5: error: no type named ‘difference_type’ in ‘struct std::iterator_traits<int>’
In file included from ../MyVector/main.cpp:2:0:
../MyVector/MyVector.h: In instantiation of ‘void Vector<T, Allocator>::assign(InputIt, InputIt) [with InputIt = int; T = int; Allocator = std::allocator]’:
../MyVector/main.cpp:52:24: required from here
../MyVector/MyVector.h:107:36: error: invalid type argument of unary ‘*’ (have ‘int’)
this->arr[i] = *first++;
^~~~~~~~
Makefile:725: recipe for target 'main.o' failed
make: *** [main.o] Error 1
I'm using C++17
The range version is a better match for vec.assign(5, 10); with InputIt = int. You should somehow disable that overload for a template parameter that doesn't represent an input iterator.
Let's take a look at stdlibc++ implementation:
template<typename InputIt, typename = std::RequireInputIter<InputIt>>
void assign(InputIt first, InputIt last) {
M_assign_dispatch(first, last);
}
where RequireInputIter is
template<typename InputIt>
using RequireInputIter = typename enable_if<is_convertible<typename
iterator_traits<InputIt>::iterator_category, input_iterator_tag>::value>::type;
In other words, for a deduced type InputIt, iterator_traits<InputIt>::iterator_category type should be convertible into input_iterator_tag. Otherwise, that assign overload is silently excluded from the overload resolution set thanks to SFINAE.
In C++17, RequireInputIter can be simplified with _t and _v helpers:
template<typename InputIt>
using RequireInputIter = enable_if_t<is_convertible_v<typename
iterator_traits<InputIt>::iterator_category, input_iterator_tag>>;
Also note that input iterators can be used to traverse a range only once. After you call std::distance(first, last), all subsequent attempts to traverse the range are undefined behaviour unless InputIt is at least a forward iterator. For input iterators you can't determine how much space to preallocate.
That's why assign uses tag dispatch technique internally. With some simplifications it looks like this:
template<typename InputIt, typename = std::RequireInputIter<InputIt>>
void assign(InputIt first, InputIt last) {
M_assign_aux(first, last,
typename iterator_traits<InputIt>::iterator_category{});
}
There are two M_assign_aux overloads
template<typename InputIt>
void M_assign_aux(InputIt first, InputIt last, std::input_iterator_tag);
template<typename ForwardIt>
void M_assign_aux(ForwardIt first, ForwardIt last, std::forward_iterator_tag);
to do the assignment. The first one will be used for input iterators only, and the second one - for forward iterators and those derived from it, i.e. bidirectional and random access ones.
这篇关于自己的向量分配实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
