张槎建网站服务/品牌策划的五个步骤

版权声明：原创文章，欢迎转载，但请注明出处，谢谢。
https://blog.csdn.net/qiuguolu1108/article/details/107146466

浅析vector容器(1)-vector内存分配策略

浅析vector容器(2)-减少vector内存占用

浅析vector容器(3)-使用移动语义提高性能

vector之所以会发生大量的拷贝，是因为其内存分配策略造成的。每当vector的内存不够用时，vector都会重新申请两倍的空间，并将之前的元素搬移到新空间。这才是发生拷贝的根源，既然这样，我们能不能预先给vector申请一定的空间，避免因空间不够而发生元素搬移。

1、使用reverse()函数预申请空间

reverse()函数可以给vector预先分配指定大小的空间。

vector<A> va;va.reserve(1024);cout<<"va size     = "<<va.size()<<endl;
cout<<"va capacity = "<<va.capacity()<<endl<<endl;A a;for(int i=0;i<1024;i++)
{va.push_back(a);
}A::dis_copy_construct_count();
cout<<endl;cout<<"va size     = "<<va.size()<<endl;
cout<<"va capacity = "<<va.capacity()<<endl;

使用reverse()给va预先分配了1024个空间，所以再往va推入1024个元素的时候，并没有发生多余的拷贝构造。

通过reverse()给vector预分配空间，确实可以减少元素的拷贝构造，但我们在使用vector时，有时很难确定容器元素的个数。

在使用reverse()时需要自己去平衡，如果reverse()过大，会造成空间的浪费，如果过小还是会发生拷贝构造。

现在又带来一个问题，如何将vector过多的没有存放元素的空间还给系统。

2、erase()函数和clear()会减少vector的内存占用吗？

上篇文章中，我们说过vector占用空间的大小，可以通过capacity()函数来查看。

通过一个示例，来验证一下erase()、clear()会减少vector内存占用吗？

vector<int> vi;for(int i=0;i<65;i++)
{vi.push_back(i);
}cout<<"vi size     = "<<vi.size()<<endl;
cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;auto itr = find(vi.begin(),vi.end(),30);/*删除0~29元素*/
vi.erase(vi.begin(),itr);
cout<<"vi size     = "<<vi.size()<<endl;
cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;vi.clear();
cout<<"vi size     = "<<vi.size()<<endl;
cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;

通过测试我们发现，erase()和clear()只能将vector空间的元素给析构掉，并不能减少vector内存的占用。

这是侯捷老师《STL源码剖析》对vector的erase()、clear()函数实现介绍。

现在我们分析一下SGI版本STL的实现：

/*调用下面函数，释放整个vector区间内的所有元素。*/
void clear() { erase(begin(), end()); }/*释放一个区间的元素*/
iterator erase(iterator first, iterator last)
{/*将 [last,finish)区间的元素，拷贝至first起始的位置*/iterator i = copy(last, finish, first);     /*调用[i,finish)区间内元素的析构器，将该区间内的元素析构掉。*/destroy(i, finish);                 finish = finish - (last - first);return first;  
}

template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {__destroy(first, last, value_type(first));   /*value_type用于获取容器元素的类型*/
}template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {/*萃取容器元素的类型信息*/typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;__destroy_aux(first, last, trivial_destructor());   /*根据trivial_destructor()的类型不同，会调用下面两个不同的函数。*/
}/*元素的析构器是trivial，元素析构器不需要被调用。*/
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}/*元素的析构器是non-trivial，则需要调用每个元素的析构器。*/
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {/*通过迭代器遍历每个容器元素，分别调用它们的析构器。*/for ( ; first < last; ++first)destroy(&*first);     /*需要是容器元素的地址*/
}/*用于调用对象的析构器*/
template <class T>
inline void destroy(T* pointer) {pointer->~T();      /*调用T对象的析构器*/
}

从以上的vector源码可以看出，erase函数和clear函数，并没有释放vector的空间，仅仅是将析构掉了vector中的元素。

3、data()函数可以返回vector元素存放的位置

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;for(int i=0;i<10;i++){vi.push_back(i);}int * p = vi.data();for(int i=0;i<10;i++){cout<<*p++<<endl;}return 0;
}

data()这个函数不用多说了，通过示例就可以看出这个函数好强大，直接杀入了vector的老巢。

4、swap()函数用于交换两个vector

swap()函数可以用于交换两个vector，但是交换了vector的哪些东西？

vector<int> vi0;
for(int i=0;i<5;i++)
{vi0.push_back(i);
}
cout<<"&vi0  = "<<&vi0<<endl;
cout<<"vi0.data() = "<<vi0.data()<<endl<<endl;vector<int> vi1;
for(int i=0;i<5;i++)
{vi1.push_back(i*100);
}
cout<<"&vi1  = "<<&vi1<<endl;
cout<<"vi1.data() = "<<vi1.data()<<endl;cout<<endl<<"====================="<<endl<<endl;vi0.swap(vi1);cout<<"&vi0  = "<<&vi0<<endl;
cout<<"vi0.data() = "<<vi0.data()<<endl<<endl;cout<<"&vi1  = "<<&vi1<<endl;
cout<<"vi1.data() = "<<vi1.data()<<endl;

从示例中可以看出，vector的data()发生了交换，但vi0和vi1所在的地址并没有发生变化。swap()函数还交换了其他内部成员数据，但我们弄清了我们关心的一点，swap并没有发生空间的大量拷贝，交换的仅仅是两个空间地址。

注意：左侧的堆空间是错误的，应该为栈空间。
补充一点：swap()函数，不仅仅交换两个容器的内容，同时它们的迭代器、指针和引用也被交换。在swap发生后，原先指向容器中元素的迭代器、指针和引用依然有效，并指向同样的元素----但是，这些元素已经在另一个容器中了。

5、vector的拷贝构造

使用一个vector去构造器另外一个vector，在构造新的vector时，仅会根据vector实际元素个数去构造新的vector。

vector<int> vi0;
vi0.reserve(100);//插入5个元素
for(int i=0;i<5;i++)
{vi0.push_back(i);
}cout<<"vi0 size     = "<<vi0.size()<<endl;
cout<<"vi0 capacity = "<<vi0.capacity()<<endl<<endl;vector<int> vi1(vi0);
cout<<"vi1 size     = "<<vi1.size()<<endl;
cout<<"vi1 capacity = "<<vi1.capacity()<<endl;

虽然vi0的内存空间可以存放100个int，但实际有效元素只有5个int。通过vi0拷贝构造vi1的时候，并不会像vi0那样占用100个int空间，而是根据实际元素的个数申请空间，并不会有多余的空间。

6、使用swap技巧移除多余的容量

铺垫了这么多，回到我们的主题上，如何减少vector的容量？

vector的构造器在构建新的容器时，会自动的去掉多余的空间，我们可以利用这个特性，结合swap函数去掉vector中多余的容量。

6.1 方法一：通过定义一个新的vector

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;vi.reserve(100);for(int i=0;i<5;i++){vi.push_back(i);}cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;vector<int> tmp(vi);cout<<"tmp size     = "<<tmp.size()<<endl;cout<<"tmp capacity = "<<tmp.capacity()<<endl<<endl;cout<<"=================="<<endl<<endl;tmp.swap(vi);cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;cout<<"tmp size     = "<<tmp.size()<<endl;cout<<"tmp capacity = "<<tmp.capacity()<<endl<<endl;return 0;
}

vi有多余的容量，通过vi构造一个新的容器tmp，tmp没有多余的容量，通过swap函数将tmp和vi交换，则tmp变成了有多余容量的容器。tmp是一个局部变量，在离开其作用域时，会调用vector的析构器，将其自己释放。

注意：左侧的堆空间是错误的，应该为栈空间。

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;vi.reserve(100);for(int i=0;i<5;i++){vi.push_back(i);}{vector<int> tmp(vi);tmp.swap(vi);}//tmp在此处就会调用vector的析构器，将其自己销毁。return 0;
}

这样可以更加快速的消除多余容量。之前示例，tmp需要在main函数的最后才被销毁，此处的示例，tmp在swap之后就立即被销毁。

6.2 方法二：使用临时变量

上面的方法确实可以消除vector多余的容量，但不够优雅，略显啰嗦。使用临时变量可以更加简洁。

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;vi.reserve(100);for(int i=0;i<5;i++){vi.push_back(i);}cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;vector<int>(vi).swap(vi);   //本行产生的匿名对象vector<int>(vi)在离开本行时，就会被销毁。cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl;return 0;
}

没有定义多余的变量，一行代码搞定，真的很优雅了。

简单的说一下：vector<int>(vi)定义一个临时对象，这个临时对象通过拷贝构造器构造。临时对象调用swap成员函数将其自己和vi交换。临时对象在离开其作用域时被销毁。

6.3 清空vi

clear()仅会清空容器中的元素，并不能真正的释放vector占用的内存。使用swap()可以释放vector内存。

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;vi.reserve(100);for(int i=0;i<5;i++){vi.push_back(i);}cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;vector<int>().swap(vi);cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl;return 0;
}

vector<int>()会产生一个临时对象，这个对象没有名字，其size和capacity皆为零。

6.4 总结：

去除vi多余的容量：vector<int>(vi).swap(vi)

将vi的空间清空：vector<int>().swap(vi)

7、使用C++11中shrink_to_fit()函数去除多余容量

看看官方介绍

#include <iostream>
#include <vector>int main()
{std::vector<int> v;std::cout << "Default-constructed capacity is " << v.capacity() << '\n';v.resize(100);std::cout << "Capacity of a 100-element vector is " << v.capacity() << '\n';v.clear();std::cout << "Capacity after clear() is " << v.capacity() << '\n';v.shrink_to_fit();std::cout << "Capacity after shrink_to_fit() is " << v.capacity() << '\n';
}

官方给的示例，很容易理解。

#include <iostream>
#include <vector>using namespace std;int main()
{vector<int> vi;vi.reserve(100);cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;for(int i=0;i<10;i++){vi.push_back(i);}cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;vi.shrink_to_fit();cout<<"vi size     = "<<vi.size()<<endl;cout<<"vi capacity = "<<vi.capacity()<<endl<<endl;return 0;
}

vi的容量是100，向其推入10个元素，则有90个多余的空间，调用shrink_to_fit()后，其容量变为10，释放了多余的空间。

8、减少vector容量，必要的拷贝依然存在。

不管是swap()函数还是shrink_to_fit()函数，在去除vector多余空间的时候，还是会发生必要的元素拷贝。

8.1 swap方法

vector<A> va;
va.reserve(10);A a;for(int i=0;i<3;i++)
{va.push_back(a);
}cout<<endl<<"======================"<<endl<<endl;vector<A>(va).swap(va);cout<<endl<<"======================"<<endl<<endl;

注意：左侧的堆空间是错误的，应该为栈空间。
这里的拷贝构造主要是在构造临时对象产生的。

8.2 shrink_to_fit方法

vector<A> va;
va.reserve(10);A a;for(int i=0;i<3;i++)
{va.push_back(a);
}cout<<endl<<"======================"<<endl<<endl;va.shrink_to_fit();cout<<endl<<"======================"<<endl<<endl;

结果都是一样的，发生了拷贝构造。

9、resize()函数

顺便说一下resize()函数，这个函数使用也有一定的迷惑性。现在通过几个例子说明一下其背后都做了哪些事情。

现在vector有两个大小，一个是size()，vector实际元素的个数；另一个是capacity()，vector的容量。

size是小于等于capacity的。

9.1 resize()参数小于size()

将多余的元素析构掉

#include <iostream>
#include <vector>using namespace std;class A
{
public:A(int data = 100):data_(data){cout<<"constructor : "<<this<<endl;}A(const A& a){data_ = a.data_;cout<<this<<" : copy constructor form : "<<&a<<endl;}void display(){cout<<data_<<" ";}~A(){cout<<"deconstructor : "<<this<<endl;}private:int data_;
};int main()
{vector<A> va;va.reserve(8);A a(0),b(1),c(2),d(3);cout<<endl<<"========================"<<endl;va.push_back(a);va.push_back(b);va.push_back(c);va.push_back(d);cout<<endl<<"========================"<<endl;for(auto & i : va){i.display();}cout<<endl;va.resize(2);for(auto & i : va){i.display();}cout<<endl;return 0;
}

注意：左侧的堆空间是错误的，应该为栈空间。

9.2 resize()参数大于size()，小于capacity()。

9.2.1 情况一：使用默认构造构造新元素

vector<A> va;
va.reserve(8);A a(0),b(1),c(2),d(3);cout<<endl<<"========================"<<endl;
va.push_back(a);
va.push_back(b);
va.push_back(c);
va.push_back(d);cout<<endl<<"========================"<<endl;
for(auto & i : va)
{i.display();
}
cout<<endl;va.resize(6);for(auto & i : va)
{i.display();
}
cout<<endl;

需要添加两个新的元素，没有指定添加的元素，则调用类A的默认构造生成新元素。

A(int data = 100):data_(data)
{cout<<"constructor : "<<this<<endl;
}

这是类A的默认构造器，使用这个构造器生成的对象，其默认值为100。

注意：左侧的堆空间是错误的，应该为栈空间。

9.2.2 情况二：使用指定的元素构造新元素

vector<A> va;
va.reserve(8);A a(0),b(1),c(2),d(3);cout<<endl<<"========================"<<endl;
va.push_back(a);
va.push_back(b);
va.push_back(c);
va.push_back(d);cout<<endl<<"========================"<<endl;
for(auto & i : va)
{i.display();
}
cout<<endl;A aa(99);va.resize(6,aa);for(auto & i : va)
{i.display();
}
cout<<endl;

和上面类似，但新元素的生成，调用了拷贝构造器。但这里多发生了一次拷贝构造，根据调用情况，猜测resize()先把元素拷贝到其内部，所有新元素的拷贝都是基于resize()内部的副本。

9.3 resize()参数大于capacity()

重新申请空间，将原数据拷贝过来，在新的位置调用默认构造器生成新的元素。

vector<A> va;
va.reserve(8);A a(0),b(1),c(2),d(3);cout<<endl<<"========================"<<endl;
va.push_back(a);
va.push_back(b);
va.push_back(c);
va.push_back(d);cout<<endl<<"========================"<<endl;
for(auto & i : va)
{i.display();
}
cout<<endl;va.resize(10);for(auto & i : va)
{i.display();
}
cout<<endl;cout<<va.capacity()<<endl;

注意：左侧的堆空间是错误的，应该为栈空间。

10、总结

本文介绍了如何去除vector多余的容量。shrink_to_fit()是C++11提供的新方法，在C++98中可以使用swap()函数实现去除多余的容量。

参考：
《STL源码剖析》 : https://book.douban.com/subject/1110934/

《Effective STL》：https://book.douban.com/subject/24534868/