高效的使用STL

「爱情、让人受尽委屈。」 2022-07-25 15:56 151阅读 0赞

# 原文：http://www.cnblogs.com/me115/p/4596543.html #

# 高效的使用STL #

仅仅是个选择的问题，都是STL，可能写出来的效率相差几倍；  
熟悉以下条款，高效的使用STL；

## 当对象很大时，建立指针的容器而不是对象的容器 ##

1）STL基于拷贝的方式的来工作，任何需要放入STL中的元素，都会被复制；  
这也好理解，STL工作的容器是在堆内开辟的一块新空间，而我们自己的变量一般存放在函数栈或另一块堆空间中；为了能够完全控制STL自己的元素，为了能在自己的地盘随心干活；这就涉及到复制；  
而如果复制的对象很大，由复制带来的性能代价也不小 ；  
对于大对象的操作，使用指针来代替对象能消除这方面的代价；  
2）只涉及到指针拷贝操作， 没有额外类的构造函数和赋值构造函数的调用；

vecttor <BigObj> vt1;
    vt1.push_bach(myBigObj);
    
    vecttor <BigObj* > vt2;
    vt2.push_bach(new BigObj());

注意事项：  
1）容器销毁前需要自行销毁指针所指向的对象；否则就造成了内存泄漏；  
2）使用排序等算法时，需要构造基于对象的比较函数，如果使用默认的比较函数，其结果是基于指针大小的比较，而不是对象的比较；

## 用empty() 代替size()来检查是否为空 ##

因为对于list，size()会遍历每一个元素来确定大小，时间复杂度 o（n），线性时间；而empty总是保证常数时间；

## 尽量用区间成员函数代替单元素操作 ##

使用区间成员函数有以下好处：  
1）更少的函数调用  
2）更少的元素移动  
3）更少的内存分配

例：将v2后半部的元素赋值给v1：  
单元式操作：

for (vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
    ci != v2.end();
    ++ci)
    v1.push_back(*ci)

使用区间成员函数assign()：

v1.assign(v2.begin() + v2.size() / 2, v2.end());

## 使用reserver避免不必要的内存分配(for vector) ##

新增元素空间不够时，vector会进行如下操作：  
1）分配当前空间的两倍空间；  
2）将当前元素拷贝到新的空间中；  
3）释放之前的空间；  
4）将新值放入新空间指定位置；

如果预先知道空间的大小，预先分配了空间避免了重新分配空间和复制的代价；  
注：reserve()只是修改了容量，并非大小，向vector中增加元素还是需要通过push\_back加入；

## 使用有序的vector代替关联容器(阶段性的操作适用) ##

对阶段性操作的定义：  
先做一系列插入、完成之后，后续操作都是查询；

在阶段性的操作下，使用vector有以下优势：  
1）因为vector有序，关联容器带来的有序优势散失；  
2）都是使用二分法查找的前提下，查询算法对连续的内存空间的访问要快于离散的空间；

## 在map的insert()和operator［］中仔细选择 ##

插入时，insert效率高；因为operator会先探查是否存在这个元素，如果不存在就构造一个临时的，然后才涉及到赋值，多了一个临时对象的构造；  
更新时，［］效率更高，insert会创造一个对象，然后覆盖一个原有对象；而［］是在原有的对象上直接赋值操作；

散列函数的默认比较函数是equal＿to，因为不需要保持有序；

## 尽量用算法替代手写的循环 ##

1）效率相比手写更高；  
STL的代码都是C++专家写出来的，专家写出来的代码在效率上很难超越；  
除非我们放弃了某些特性来满足特定的需求，可能能快过stl；比如，基于特定场合下的编程，放弃通用性，可移植性；  
2）不容易出错；  
3）使用高层次思维编程  
相比汇编而言，C是高级语言；一条C语言语句，用汇编写需要好几条；  
同样的，在STL的世界中，我们也有高层次的术语：  
高层次的术语：insert／find／for＿each（STL算法）  
低层次的词汇：for ／while（C++语法）  
用高层次术语来思考编程，会更简单；

## 尽量用成员函数代替同名的算法 ##

1）基于效率考虑，成员函数知道自己这个容器和其他容器有哪些特有属性，能够利用到这些特性；而通用算法不可以；  
2）对于关联容器，成员函数find基于等价搜索；而通用算法find基于相等来搜索；可能导致结果不一样；

## 使用函数对象代替裸函数作为算法的输入参数 ##

因为内联，在函数对象的方式中，内联有效，而作为函数指针时，一般编译器都不会内联函数指针指向的函数；即使指定了inline；  
比如：

inline bool doubleGreater(double d1, double d2)
    {
        
        return dl > d2;
    }
    vector<double> v;
    ...
    sort(v.begin(), v.end(), doubleGreater);

这个调用不是真的把doubleGreater传给sort，它传了一个doubleGreater的指针。  
更好的方式是使用函数对象：

sort(v.begin(), v.end(), greater<double>())

注：《effcient c＋＋》中的实验结论，使用函数对象一般是裸函数的1.5倍，最多能快2倍多

## 选择合适的排序算法 ##

需要排序前思考我们的必要需求，可能我们只是需要前多少个元素，这时并不需要使用sort这种线性时间的工具，性能消耗更少的parttition可能是更好的选择；  
以下算法的效率从左到右依次递减：

partition > stable_partition / nth_element / patical_sort / sort / stable_sort

功能说明：  
partition ：将集合分隔为满足和不满足某个标准两个区间；  
stable\_partition ：partition的稳定版本；  
nth\_element ：获取任意顺序的前N个元素；  
patical\_sort ：获取前N个元素，这个N个元素已排序；  
sort：排序整个区间；  
stable\_sort：sort的稳定版本；

## 选择合适的容器 ##

为什么vector不提供push\_front()成员方法？因为效率太差，如果有太多从前面插入的需求，就不应该使用vector，而用list；  
关心查找速度，首先应该考虑散列容器（非标准STL容器,如：unordered\_map,unordered\_set)；其次是排序的vector，然后是标准的关联容器；