前言
如果我们试图将一个vector1内全部元素替换为vector2的后半部分,最好的办法是这样:1
v1.assign(v2.begin() + v2.size() / 2, v2.end());
assign是一个很好用的函数,当我们想把容器复制到另一个类型相同的容器,operator=是一个好选择,但如果我们试图在不同的容器之间进行拷贝,或者给容器一组全新的值时,assign更优。
区间函数
区间成员函数的特点是其形参是一对表示区间的迭代器。如果不用这种区间,我们往往需要编写循环,但这样效率很低。如果拒绝编写循环,我们可能会使用泛型算法来前言中提到的问题,比如说copy算法:1
2
3
4
5
6
7
8
9//循环写法
vector<Widget> v1, v2;
v1.clear();
for (auto ci = v2.begin() + v2.size() / 2;ci != v2.end();++ci){
v1.push_back(*ci);
}
//copy算法
v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));
但是实际上copy里面必然也包含循环,而且,所有利用插入迭代器(inserter,back_inserter,front_inserter)来限定目标区间的copy调用,其实都应该替换为对应区间版本函数的调用,比如上文的copy,可以替换为利用区间的insert版本1
v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());
与copy相比,代码略微简洁,但是最关键的是它直截了当地指出了发生的事情:插入。
STL滥用copy的情况应该被避免,所以再次重申:通过利用插入迭代器的方式来限定目标区间的copy调用,不如直接被替代为对区间成员函数的调用。
区间成员函数在可阅读性上的优点可以被总结为:
- 代码简洁
- 意图清晰直接
性能优劣分析
我们会发现单元素成员函数比使用区间成员函数需要更多地调用allocator,更频繁地复制,以及更多的冗余操作。举例如下:
假定我们需要将一个int数组复制到vector的前端,如果使用insert函数:1
2
3
4int data[numValues];
vector<int> v;
...
v.insert(v.begin(), data, data + numValues);
如果通过循环显式地调用insert:1
2
3
4
5vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
insertLoc = v.insert(insertLoc, data[i]);
++insertLoc;
}
这里值得注意的是,每一次都需要在insert后更新insertLoc,否则会出现2点问题,
1. insertLoc失效,其插入行为不可预料
2. 即便不失效,插入总是发生在begin处,即倒着把data插入到最前面.
如果使用copy算法:1
copy(data, data + numValues, inserter(v, v.begin()));
当copy模版被实例化后,其代码与基于循环的代码几乎完全相同。因此,我们在分析效率时,只需要分析循环那个版本。
总的说来,一共有3处影响了效率。
- 不必要的函数调用
n个元素的插入必然调用了n次插入操作,而insert只有一次调用,虽然内联能解决这个问题,但编译器不一定会给你内联。 - 将v中已有的元素频繁地向后移动
如果内部元素是自定义类型,则会造成频繁地使用赋值操作运算符和拷贝构造函数(之前都是赋值,最后一个拷贝)
假设原有容器中有m个元素,需要插入n个元素,一共需要mn次调用:(m-1)n次赋值操作符,n次拷贝构造函数。而insert总是一步到位地将现有元素直接放到最终位置。总代价包括m次移动,n次拷贝构造函数。
虽然insert几乎总是一次性地移动所有元素到位,但其实它是建立在已知两个迭代器之间距离的基础上,而这个功能是由前向迭代器提供的。也就是说,当传入区间的是输入迭代器例如istream_iterator之类,insert就失去了性能上的优势 - 多次扩容
我们都知道如果你插入时vector的容量已满,它会进行扩容,此时又会复制一大波元素到新的位置。如果插入次数很多,那么扩容的次数也很多,因此,造成了大量的浪费。insert因为已知需要多少容量,因此减少了浪费。
以上说法对于vector和string同样有效。deque内存管理方式不同,所以内存重复分配的话题对它无效,但是反复移动与多次调用的结论仍然有效。list使用区间形式也有其优势,减少函数调用次数的优势依然存在,虽然list无需反复移动和构造,也不存在内存分配,但是存在对节点的next与prev指针重复多余的操作。一般而言,每一次插入都会导致节点的next与prev赋值一次,但如果我们提前知道插入了多少节点,就避免了重复指针赋值。
哪些函数支持区间操作
区间构造
所有标准容器都提供这种形式的构造函数:1
container::container(InputIterator begin,InputIterator end);
但如果传给构造函数的是istream_iterator或者istreambuf_iterator时,c++的分析机制会把这条语句解释为函数声明,而不是新建对象。
区间插入
所有标准序列容器都提供这种形式的insert:1
void container::insert(iterator position, InputIterator begin,InputIterator end);
关联容器使用比较函数来决定元素要放在哪里,所以不能指定位置:1
void container::insert(lnputIterator begin, InputIterator end);
对于插入,不要忘了很多函数其实做着与insert一样的事情,当你看到反复的push_back或者push_infront时,不妨提供给他们区间形式的insert版本。
区间删除
STL容器都支持区间删除,但是关联与非关联的返回值不同。
序列容器如下:1
iterator container::erase(iterator begin, iterator end);
关联容器如下:1
void container::erase(iterator begin, iterator end);
据说因为关联容器返回一个迭代器(指向被删除元素之后的元素)会造成难以负担的性能影响,所以关联容器不反回迭代器。
区间赋值
所有标准列容器都提供了区间形式的assign:1
void container::assign(InputIterator begin, InputIterator end);
总结
区间函数的三大优点:
- 代码简洁
- 目的明确
- 效率更高