STL源码解析之：vector（3）

一、SWAPswap操作用于交换两个 vector 的内容包括它们所管理的内存、大小和容量。这是一种非常高效的操作通常只是交换内部指针而不会逐个元素拷贝。void swap(vectorT, Alloc x) { __STD::swap(start, x.start); __STD::swap(finish, x.finish); __STD::swap(end_of_storage, x.end_of_storage); } template class T, class Alloc inline void swap(vectorT, Alloc x, vectorT, Alloc y) { x.swap(y); }例如std::vectorint a{1,2,3}, b{4,5,6,7}; a.swap(b); //swap 方式1 std::swap(a, b); //swap 方式2与1等价swap的典型用途1交换两个容器的内容高效避免拷贝元素2) 清空 vector 并释放内存std::vectorint().swap(v); // 构造一个空临时 vector交换后 v 变为空且 capacity 0 // 效果等价于 v.clear(); v.shrink_to_fit();二、eraseerase用于从 vector 中移除一个元素或一个范围的元素。它会将被删除元素之后的所有元素向前移动以填补空缺因此操作复杂度与删除位置及后续元素个数相关。iterator erase(iterator position) { if (position 1 ! end()) copy(position 1, finish, position); --finish; destroy(finish); return position; } iterator erase(iterator first, iterator last) { iterator i copy(last, finish, first); destroy(i, finish); finish finish - (last - first); return first; }2.1 行为与复杂度单个元素删除erase(pos)将pos1到end()的所有元素向前移动一位。复杂度O(size() - index)即线性于pos后面的元素个数。如果删除的是末尾元素pos end()-1复杂度 O(1)。范围删除erase(first, last)将last到end()的所有元素向前移动到first开始的位置。复杂度O(size() - distance(first, last))即线性于删除范围之后的元素个数。2.2 迭代器、引用、指针失效规则被删除的元素所有指向它们的迭代器、引用、指针均失效。未被删除的元素位于删除位置之后的迭代器、引用、指针可能失效因为元素被移动了。但是如果仅删除尾部元素尾部之后的迭代器即end()可能会失效但更早的迭代器不受影响。标准保证erase操作后指向被删除元素之后位置的那些迭代器/引用/指针仍然有效虽然它们指向的元素可能已被移动。例如for (auto it v.begin(); it ! v.end(); ) { if (condition(*it)) { it v.erase(it); // it 被更新为下一个有效位置 } else { it; } }错误使用方法for (auto it v.begin(); it ! v.end();it ) { if (condition(*it)) { v.erase(it); //被删位置及之后所有迭代器全部失效 } }2.3 高效删除方法:remove_if erase 惯用法std::remove_if和std::vector::erase经常配合使用形成所谓的 “擦除-移除惯用法” (erase-remove idiom)以高效地从容器中删除满足条件的元素。std::remove_if并不真正删除元素它只是通过移动赋值将不需要删除的元素向前覆盖将需要删除的元素移到后面最后返回指向新“末尾”的迭代器。真正的删除需要调用容器的erase成员函数。例如std::vectorint v {1, 2, 3, 4, 5, 6} std::vectorint v {1, 2, 3, 4, 5, 6}; // 删除所有偶数 v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end()); for (int x : v) std::cout x ; // 输出: 1 3 5 std::cout \nsize v.size(); // size 3