为 std::vector 编写自定义插入函数

Question

我正在为我的个人项目编写 std：：vector 的插入函数。

插入前的矢量布局：

position : 0 1 2 3 4
Value    : a b c e f 

假设有足够的容量，我想在位置 3 插入"d"。

插入后的矢量布局：

position : 0 1 2 3 4 5
Value    : a b c d e f

我编写了一个函数，将值向右移动给定插入位置(在示例中为 3(，然后在请求的插入位置分配给定值。

我写给shift_right的函数如下：

template <typename T>
void vector<T>::shift_right(typename vector<T>::iterator given_pos) {
for (auto iter = end() - 1; iter != given_pos - 1; iter--) {
*(iter + 1) = *iter;
}
}

是否有std：：算法或其变体可以帮助我摆脱 shift_right 函数中的原始循环？

Answer 1

您可以使用std::move_backward：

template< class BidirIt1, class BidirIt2 ><br>
BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

将元素从范围[first, last)移动到另一个以d_last结尾的范围。元素以相反的顺序移动(最后一个元素首先移动(，但它们的相对顺序保持不变。

所以你的代码可能看起来像这样(未经测试(：

template <typename T>
void vector<T>::shift_right(typename vector<T>::iterator given_pos) {
std::move_backward(given_pos, end()-2, end()-1);
}

这假设容量已经在必要时增加，并且end()返回新的结束迭代器(即插入新空格后最后一个元素之后的一个迭代器(。如果不是这种情况，请更改为std::move_backward(given_pos, end()-1, end());。

Answer 2

看来你的意思是像下面这样

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
template <typename T>
typename std::vector<T>::iterator 
shift_right( std::vector<T> &v, typename std::vector<T>::size_type pos )
{
v.resize( v.size() + 1 );
typename std::vector<T>::iterator result = std::end( v );
if ( pos < v.size() )
{
result = std::copy_backward( std::next( std::begin( v ), pos ), 
std::prev( std::end( v  )),
std::end( v ) );
}
return std::prev( result ); 
}
int main() 
{
std::vector<int> v;
auto it = shift_right( v, v.size( ) );
*it = 2;
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
it = shift_right( v, v.size() );
*it = 3;
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
it = shift_right( v, 0 );
*it = 0;
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
it = shift_right( v, 1 );
*it = 1;
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
return 0;
}

程序输出为

2 
2 3 
0 2 3 
0 1 2 3

请注意，最好使用std::copy_backward而不是std::move_backward因为在第一种情况下，向量的所有元素的状态在移动它们后将与基本类型数组的元素类似。

如果使用std::move_backward则相应的函数可以如下所示，如下面的演示程序所示。

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
template <typename T>
typename std::vector<T>::iterator 
shift_right( std::vector<T> &v, typename std::vector<T>::size_type pos )
{
v.resize( v.size() + 1 );
typename std::vector<T>::iterator result = std::end( v );
if ( pos < v.size() )
{
result = std::move_backward( std::next( std::begin( v ), pos ), 
std::prev( std::end( v  )),
std::end( v ) );
}
result = std::prev( result );
*result = T();
return result; 
}
int main() 
{
std::vector<int> v = { 1, 2, 4, 5, 6 };
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
auto it = shift_right( v, 2 );
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
*it = 3;
for ( const auto &item : v ) std::cout << item << ' ';
std::cout <<'n';
return 0;
}

程序输出为

1 2 4 5 6 
1 2 0 4 5 6 
1 2 3 4 5 6 

Answer 3

我将首先定义一个方便的函数模板，right_shift_by_one()，它将元素在有效迭代器范围[first，last(中向右移动一个位置：

template<typename BidirIt>
void right_shift_by_one(BidirIt first, BidirIt last) {
std::move_backward(first, std::prev(last), last);
}

然后，自定义向量的成员函数shift_right()，它最终调用上面定义的便利函数：

template<typename T>
auto shift_right(typename vector<T>::iterator pos) {
auto dist = std::distance(begin(), pos);
// this only compiles if T is default constructible
resize(size()+1);
// resize() may have invalidated the pos iterator due to vector's reallocation
// recompute it
pos = begin() + dist;
right_shift_by_one(pos, end());
return pos;
}

此成员函数返回一个迭代器，指向与右移创建的新空间对应的元素。即使向量没有足够的容量，这也有效，因为已经考虑了重新分配时迭代器的失效。但是，您必须在自定义矢量实现中实现resize()。

用：

auto it = shift_right(vec.begin() + 2);
*it = 'c';