c++性能优化：标准模板库

插入删除遍历查找函数对象比STL更好要点

如果你发现你觉得内存占用很大，vector的复制构造函数和析构函数比较耗时，那么使用指针代替对象是个比较好的方法。使用指针进行插入删除的话，实际使用的耗时和插入整型是差不多的。list和vector在存储上面各有优势和劣势。比如，如果在中间插入元素的话，vector需要移动后面的元素，而list可以直接插入位置。

// vector 头插 10000=次耗时800ms
template
void vectorInsertFront(vector* v, T* collection, int size)
{
    for (int i = 0; i < size; i++) {
        v->insert(v->begin(), collection[i]);
    }
}
// list 尾插 10000次耗时10ms
template
void listInsertFront(list* v, T* collection, int size)
{
    for (int i = 0; i < size; i++) {
        v->push_front(collection[k]);
    }
}

删除操作的性能下很多场景下和插入的性能类似。比如在尾部删除的话，vector的性能是最好；双向队列无论从前面还是后面删除（插入）都是比较高效的，其他位置操作是低效的；list从任意位置删除或者插入，都是高效的。

// list的删除在任意位置都很高效
template
void listDeleteFront(list* l)
{
    if (!l->empty()) {
        l->pop_front();
    }
}

// vector的删除在头部的话删除很低效
template
void vectorDeleteFront(vector* v)
{
    if (!v->empty()) {
        v->erase(v->begin());
    }
}

遍历通常就是一次遍历一个元素，vector和array在遍历的性能上是相差不大的。但是，列表的遍历就会慢一点，这和在内存中的存储方式也有关系，连续的内存遍历简单，不连续的内存遍历就会耗时。

使用STL内置的find函数进行查找，multiset的性能是最好的，vector和list相对来说比较耗时。同样，在测试时应该使用内置的find，而不是通用的find。

void arrayFind(int* a, int* collection, int size)
{
    const int value = collection[size/2];
    int* p = find(&a[0], &a[size], value);
}

void vectorFind(vector* v, int* collection, int size)
{
    const int value = collection[size/2];
    vector::iterator it = find(v->begin(), v->end(), value);
}

void listFind(list* l, int* collection, int size)
{
    const int value = collection[size/2];
    list::iterator it = find(l->begin(), l->end(), value);
}
// 多重集有自己的find方法，使用这个效率是最高的
void multiSetFind(multiset* s, int* cllection, int size)
{
    const int value = collection[size/2];
    multiset::iterator it = s->find(value);
}

默认情况下，accumulate函数对集合中的所有参数进行operator+的操作，得到所有元素相加累计的结果。但如果把这个函数参数化，就可以实现不同的操作，比如传入函数指针或者函数对象，实现对应的操作。

int mult(int x, int y) { return x*y; }
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int production = accumulate(&a[0], &a[9], mult);

还有一种做法就是传入函数对象：

class mult {
public:
    int operator()(int x, int y) const {return x*y;}
};
int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int production = accumulate(&a[0], &a[9], times());

times是STL提供的相乘的算法对上面的函数指针和函数对象两种传参方式进行性能耗时计算，函数对象由于在编译时就确定，而函数指针在运行时确定，因此函数对象要明显优于函数指针。

STL我们用的很多，我们是否有想过他的性能是否可以更进一步。下面我们就以accumulate函数为例子进行优化。

// 自己的实现
int myIntegerSum(int* a, int size)
{
    int sum = 0;
    int* begin = &a[0];
    int* end = &a[size - 1];
    for (int* p = begin; p != end; p++) {
        sum += *p;
    }
    return sum;
}
// STL函数的实现
int stlIntegerSum(int* a, int size)
{
    return accumlate(&a[0], &a[size], 0);
}

上面的代码的执行效率几乎相同，这样的结果就表示实际上想要超越STL的执行效率并不是很简单的事。STL库是由多个领域的专家共同开发的库，高效，强大，灵活这些特征都在STL上面有很好的体现。如果真的要打破这样的观念，可能需要举一些特殊的例子，但可能这样的例子在实际的代码y运行环境中并不会用到。
比如：我们把一个五个字符组成的字符串进行翻转，STL的话直接使用reserve函数。我们在自己实现的时候，使用下面这种写法

char* s = "abcde";
char temp;
temp = s[4];
s[4] = s[0];
s[0] = temp;

temp = s[3];
s[3] = s[1];
s[1] = temp;

STL是抽象、灵活和效率的非同寻常的综合
对于某种特定的使用方式，一些容器可能比另一些更加高效，需要具体视情况而定。
除非清楚一些特定领域内STL不清楚的事情，否则很难打破STL的使用性能；不过某些特定情况超越STL是有可能的：毕竟STL是一种模型的概念。