第一章容器

第一条：慎重选择容器类型

C++所提供的容器类型有如下几种：

标准STL序列容器 vector string deque list
标准STL关联容器 set multiset map multimap
非标准序列容器 slist rope
非标准关联容器 hash_set hash_multiset hash_map hash_multimap
vector作为string的替代
vector作为标准关联容器的替代
非标准的STL容器 array bitset valarray stack queue priority_queue

标准容器中的vector string和list比较熟悉。deque是double ended queue,提供了与vector一样的随机访问功能，但同时对头尾元素的增删操作提供了优化。set和multiset中的数据都是顺序排列的，数据值本身就是键值，set中的数据必须唯一而multiset没有这样的限制。map和multimap中的数据对按照键值顺序排列，map中不允许出现重复的key，而multimap中可以用相同的key对应不同的value。slist是single linked list，与STL中标准的list之间的区别就在于slist的iterator是单向的，而list的iterator是双向的。rope用于处理大规模的字符串。hash_set，hash_multiset，hash_map，hash_multimap利用hash算法对相对应的关联容器进行了优化。bitset是专门用来存储bit的容器。valarray主要用于对一系列的数字进行高速运算。priority_queue类似于heap,可以高效的获取最高priority的元素。

连续内存容器，动态申请一块或多块内存，每块内存中存储多个容器中的元素，当发生插入或删除操作时，要对该内存中的其他元素进行新移动操作，这会降低效率。vector，string，rope都是连续内存容器。
基于节点的容器，为容器中的每一元素申请单独的内存，元素中有指针指向其他的元素，插入和删除的操作只需要改变指针的指向。缺点在于占用内存相对连续内存容器较大。list, slist, 关联容器以及hash容器都是基于节点的容器。

第二条：不要编写试图独立于容器的代码

数组被泛化为以其所包含对象的类型为参数的容器
函数被泛化为以其使用的迭代器的类型为参数的算法
指针被泛化为以其所指向的对象的类型为参数的迭代器

考虑到以后可能会使用其他的容器替换现有的容器，为了使修改的部分最小化，最好采用如下的方式

class Widget{...};
template<typename T>
SpecialAllocator{...};

typedef vector<Widget, SpecialAllocator<Widget>> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;

WidgetContainer wc;
Widget widget;
...
WCIterator i = find(wc.begin(), wc.end(), widget);

使用Class将自定义的容器封装起来，可以更好的实现修改部分最小化，同时达到了安全修改的目的

class CustomizedContainer
{
private:
    typedef vector<Widget> InternalContainer;
    typedef InternalContainer::Iterator ICIterator;
    
    InternalContainer container;
    
public:
    ...
};

第三条：确保容器内对象的拷贝正确而高效

STL的工作方式是Copy In, Copy Out，也就是说在STL容器中的插入对象和读取对象，使用的都是对象的拷贝。在存放基类对象的容器中存放子类的对象，当容器内的对象发生拷贝时，会发生截断(剥离 slicing)。

vector<Widget> vw;

class SpecialWidget : public Widget
{
...
};

SpecialWidget sw;
vw.push_back(sw);

正确的方法是使容器包含指针而非对象。

vector<Widget*> vw;

class SpecialWidget : public Widget
{
...
};

SpecialWidget sw;
vw.push_back(&sw);

容器与数组在数据拷贝方面的对比：

当创建一个包含某类型对象的一个数组的时候，总是调用了次数等于数组长度的该类型的构造函数。尽管这个初始值之后会被覆盖掉

1	Widget w[maxNumWidgets]; //maxNumWidgets 次的Widget构造函数

如果使用vecor，效率会有所提升。

vector<widget> w;     //既不调用构造函数也不调用拷贝构造函数

vector<widget> w(5);  //1次构造 5次拷贝构造

vector<widget> w;     //既不调用构造函数也不调用拷贝构造函数
w.reserve(5);         //既不调用构造函数也不调用拷贝构造函数
vector<widget> w(5);  //1次构造 5次拷贝构造
w.reserve(6);         //需要移动位置，调用5次拷贝构造

第四条：调用empty()而不是检查size()是否为0

empty()对于所有标准容器都是常数时间，而对list操作，size()耗费线性时间。list具有常数时间的Splice操作，如果在两个list之间做链接的时候需要记录被链接到当前list的节点的个数，那么Splice操作将会变成线性时间。对于list而言，用户对Splice效率的要求高于取得list长度的要求，所以list的size()需要耗费线性的时间去遍历整个list。所以，调用empty()是判断list是否为空的最高效方法。

第五条：区间成员函数优先于与之对应的单元素成员函数

区间成员函数在效率方面的开销要小于循环调用单元素的成员函数，以insert为例

避免不必要的函数调用
避免频繁的元素移动
避免多次进行内存分配

区间创建

1	container::container(InputIterator begin, InputIterator end);

区间插入

1 2	void container::insert(Iterator position, InputIterator begin, InputIterator end); void associatedContainer::insert(InputIterator begin, InputIterator end);

区间删除

1 2	Iterator container::erase(Iterator begin, Interator end); void associatedContainer:erase(Iterator begin, Iterator end);

区间赋值

1	void container::assign(InputIterator begin, InputIterator end);

第六条：当心C++编译器最烦人的分析机制

C++会尽可能的将一条语句解释为函数声明。下列语句都声明了一个函数返回值为int类型的函数f，其参数是double类型。

1
2
3

int f(double(d));
int f(double d);
int f(double);

下列语句都声明了一个返回值为int类型的函数g，它的参数是返回值为double类型且无参的函数指针

int g(double(*pf)());
int g(double pf());
int g(double ()); //注意与int g(double (f))的区别
```　　

对于如下语句，编译器会做出这样的解释：声明了一个返回值为`list<int>`的函数data，该函数有两个参数，一个是`istream_iterator<int>`类型的变量，另一个是返回值为`istream_iterator<int>`类型的无参函数指针。
```C++
ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile),istream_iterator<int>());

如果希望构造一个list<int>类型的变量data，最好的方式是使用命名的迭代器。尽管这与通常的STL风格相违背，但是消除了编译器的二义性而且增强了程序的可读性。

ifstream dataFile("ints.dat");
istream_iterator dataBegin(dataFile);
istream_iterator dataEnd;
list<int> data(dataBegin,dataEnd);

第七条：如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

STL容器在析构之前，会将其所包含的对象进行析构。

class widget
{
    ...
};

doSth()
{
    widget w; //一次构造函数
    vector<widget> v;
    v.push_back(w); //一次拷贝构造函数
} // 两次析构函数

但如果容器中包含的是指针的话，一旦没有特别将指针delete掉将会发生内存泄漏

class widget
{
    ...
};

doSth()
{
    widget* w = new widget();
    vector<widget*> v;
    v.push_back(w); 
} // memory leak!!!

最为方便并且能够保证异常安全的做法是将容器所保存的对象定义为带有引用计数的智能指针

class widget
{
    ...
};

doSth()
{
    shared_ptr<widget> w(new widget()); //构造函数一次
    vector<shared_ptr<widget>> v;
    v.push_back(w); 
} //析构函数一次 没有内存泄漏

第八条：切勿创建包含auto_ptr对象的容器

由于auto_ptr对于其”裸指针”必须具有独占性，当将一个auto_ptr的指针赋给另一个auto_ptr时，其值将被置空。

auto_ptr<int> p1(new int(1)); // p1 = 1
auto_ptr<int> p2(new int(2)); // p2 = 2

p2 = p1; // p2 = 1  p1 = emtpy;

第三条提到STL容器中的插入对象和读取对象，使用的都是对象的拷贝，并且基于STL容器的算法也通常需要进行对象的copy，所以，创建包含auto_ptr的容器是不明智的。

第九条：慎重选择删除元素的方法

要删除容器中特定值的所有对象

//对于vector、string、deque 使用erase-remove方法
container.erase(remove(container.begin(),container.end(),value),container.end());

//对于list 使用remove方法
list.remove(value);

//对于标准关联容器 使用erase方法
associatedContainer.erase(value);

要删除容器中满足特定条件的所有对象

bool condition(int );

//对于vector、string、deque 使用erase-remove_if方法
container.erase(remove_if(container.begin(),container.end(),condition),container.end());

//对于list 使用remove_if方法
list.remove_if(condition);

//对于标准关联容器 第一种方法是结合remove_copy_if和swap方法
associatedContainer.remove_copy_if(associatedContainer.begin(),
                                   associatedContainer.end(),
                                   insert(tempAssocContainer,tempAssocContainer.end()),
                                   condition);

//另外一种方法是遍历容器内容并在erase元素之前将迭代器进行后缀递增
for(assocIt = associatedContainer.begin(); assocIt != associatedContainer.end())
{
    if(condition(*assoIt))
    {
        ///当关联容器中的一个元素被删除掉时，所有指向该元素的迭代器都被设为无效，所以要提前将迭代器向后递增
        associatedContainer.erase(assoIt++); 
    }
    else
    {
        assocIt++;
    }
}

如果除了在删除容器内对象的同时还需要进行额外的操作时

bool condition(int );
void dosth();

//对于标准序列容器，循环遍历容器内容，利用erase的返回值更新迭代器
for(containerIt = container.begin(); containerIt != container.end())
{
    if(condition(*containerIt))
    {
        doSth();
        //当标准容器中的一个元素被删除掉时，所有指向该元素以及该元素之后的迭代器都被设为无效，所以要利用erase的返回值
        containerIt = container.erase(containerIt++);
    }
    else
    {
        containerIt++;
    }
}

//对于标准关联容器，循环遍历容器内容，并在erase之前后缀递增迭代器
for(assocIt = associatedContainer.begin(); assocIt != associatedContainer.end())
{
    if(condition(*assoIt))
    {
        dosth();
        associatedContainer.erase(assoIt++); 
    }
    else
    {
        assocIt++;
    }
}

我觉得第三种情况下可以用第二种情况的实现代替，我们需要做的仅是将额外做的事情和判断条件包装在一个函数内，并用这个函数替代原有的判断条件。　

bool condition_doSth(int i)
{
    bool ret = condition(i);
    if(ret)
    {
        doSth();
    }

    return ret;
}

第十条：了解分配子的约定和限制

如果需要编写自定义的分配子，有以下几点需要注意

当分配子是一个模板，模板参数T代表你为其分配内存的对象的类型
提供类型定义pointer和reference，始终让pointer为T*而reference为T&
不要让分配子拥有随对象而不同的状态，通常，分配子不应该有非静态数据成员
传递给allocator的是要创建元素的个数而不是申请的字节数，该函数返回T*，尽管此时还没有T对象构造出来
必须提供rebind模板，因为标准容器依赖于该模板

第十一条：理解自定义分配子的合理用法

如果需要在共享的内存空间中手动的管理内存分配，下列代码提供了一定的参考

//用户自定义的管理共享内存的malloc和free
void* mallocShared(size_t bytesNeeded);
void* freeShared(void* ptr);

template<typename T>
class sharedMemoryAllocator
{
public:
    ...
    
    point allocator(size_type numObjects, const void* localityHint=0)
    {
        return static_cast<pointer>(mallocShared(numObjects*sizeof(T)));
    }

    void deallocate(pointer ptrMemory, size_type numObjects)
    {
        freeShared(ptrMemory);
    }
}

　　
如果不仅仅是将容器的元素放在共享内存，而且要将容器对象本身也放在共享内存中，参考如下代码

void* ptrVecMemory = mallocShared(sizeof(SharedDoubleVec));
SharedDoubleVec* sharedVec = new(ptrVecMemory) SharedDoubleVec;

...

sharedVec->~SharedDoubleVec();
freeShared(sharedVec);

第十二条：切勿对STL容器的线程安全性有不切实际的依赖

对于STL容器的多线程读是安全的，对于多个不同的STL容器，采用面向对象的方式对STL容器进行加锁和解锁

template<typename Container>
class lock
{
public:

    Lock(const Container& container):c(container)
    {
        getMutexFor(c);
    }

    ~Lock()
    {
        releaseMutex(c);
    }

private:
    Container& c;
},
vector<int> v;
...

{
    Lock<vector<int>> lock(v); //构造lock,加锁v
    doSthSync(v); //对v进行多线程的操作
} //析构lock,解锁v

vector和string

第十三条： vector和string优先于动态分配的数组

如果使用new来动态分配内存，使用者必须承担以下的责任

确保之后调用delete将内存释放
确保使用的是正确的delete形式，对于单个对象要用delete，对于数组对象需要用delete[]
确保对于一个对象只delete一次

vector、string自动管理其所包含元素的构造与析构，并有一系列的STL算法支持，同时vector也能够保证和老代码的兼容。使用了引用计数的string可以避免不必要的内存分配和字符串拷贝(COW- copy on write)，但是在多线程环境里，对这个string进行线程同步的开销远大于COW的开销。此时，可以考虑使用vector<char>或动态数组。

第十四条：使用reserve来避免不必要的内存分配

对于STL容器而言，当他们的容量不足以放下一个新元素的时候，会自动增长以便容纳新的数据。(只要不超过max_size)

分配一块儿原内存大小数倍的新内存，对于vector和string而言，通常是两倍。
将原来容器中的元素拷贝到新内存中
析构旧内存中的对象
释放旧内存

reserve以及与resever相关的几个函数

size() 容器中现有的元素的个数
capacity() 容器在不重新分配内存的情况下可容纳元素的总个数
resize(Container::size_type n) 将容器的size强制改变为n
- n>size 将现有容器中的元素拷贝到新内存，并将空余部分用默认构造的新函数填满
- n<size 将尾部的元素全部析构掉
reserve(Container::size_type n)将容器的size改变至少为n
- n>size 将现有容器中的元素拷贝到新内存，多余部分的内存仍然空置
- n<size 对容器没有影响

通常有两种方式使用reserve避免不必要的内存分配

预测大致所需的内存，并在构造容器之后就调用reserve预留内存
先用reserve分配足够大的内存，将所有元素都加入到容器之后再去除多余内存。

第十五条： string实现的多样性

实现A 在该实现中，包含默认Allocator的string是一个指针大小的4倍。对于有自定义的Allocator的string，他的大小将更大

实现B 在使用默认的Allocator的情况下，string对象的大小与指针的大小相等。当使用自定义的Allocator时，string对象将加上对应的自定义Allocator的对象。Other部分用来在多线程条件下进行同步控制，其大小通常为指针大小的6倍。

实现C string对象的大小总与指针大小相同，没有对单个对象的Allocator的支持。X包含一些与值的可共享性相关的数据

实现D 对于使用默认Allocator的string，其大小等于指针大小的7倍。不使用引用计数，string内部包含一块内存可容纳15个字符的字符串。

总结string的多种实现

string的值可能会被引用计数(实现A 实现B 实现C)也可能不会(实现D)
string对象的大小可能在char*指针的1倍到7倍之间
创建一个新的字符串值可能需要0次(实现D capacity<=15)、1次(实现A、实现C、实现D capacity>15)或2次(实现B)动态的内存分配
string对象可能共享(实现B、实现C)也可能不共享(实现A 实现D)其大小和容量信息
string可能支持(实现A 实现B 实现D)也可能不支持(实现C)单个对象的分配子
不同的实现对字符内存的最小分配单位有不同的策略

第十六条：了解如何把vector和string数据传给旧的API

将vector传递给接受数组指针的函数，要注意vector为空的情况。迭代器并不等价于指针，所以不要将迭代器传递给参数为指针的函数。

void foo(const int* ptr, size_t size);


vector<int> v;
...
foo(v.empty() ? NULL : &v[0], v.size());

将string传递给接受字符串指针的函数。该方法还适用于s为空或包含”\0”的情况

void foo(const char* ptr);


string s;
...
foo(s.c_str());

使用初始化数组的方式初始化vector

//向数组中填入数据
size_t fillArray(int* ptr, size_t size);

int maxSize = 10;
vector<int> v(maxSize);
v.resize(fillArray(&v[0],v.size()));

借助vector与数组内存布局的一致性，我们可以使用vector作为中介，将数组中的内容拷贝到其他STL容器之中或将其他STL容器中的内容拷贝到数组中

//向数组中填入数据
size_t fillArray(int* ptr, size_t size);

vector<int> v(maxSize);
v.resize(fillArray(&v[0],v.size()));
set<int> s(v.begin(),v.end());

void foo(const int* ptr, size_t size);

list<int> l();
...

vector<int> v(l.begin(),l.end());
foo(v.empty()? NULL : &v[0],v.size());

第十七条：使用swap去除多余容量

1	vector<int>(v).swap(v);

vector<int>(v)使用v创建一个临时变量，v中空余的内存将不会被拷贝到这个临时变量的空间中，再利用swap将这个临时变量与v进行交换，相当于去除掉了v中的多余内存。

由于STL实现的多样性，swap的方式并不能保证去掉所有的多余容量，但它将尽量将空间压缩到其实现的最小程度。利用swap的交换容器的值的好处在于可以保证容器中元素的迭代器、指针和引用在交换后依然有效。

vector<int> v1;
v1.push_back(1);
vector<int>::iterator i = v1.begin();

vector<int> v2(v1);
v2.swap(v1);
cout<<*i<<endl;  //output 1  iterator指向v2的begin

但是在使用基于临时变量的swap要当心iterator失效的情况　　

vector<int> v1;
v1.push_back(1);
vector<int>::iterator i = v1.begin();

vector<int>(v1).swap(v1);
cout<<*i<<endl;  //crash here

原因在于第5行构造的临时变量在该行结束后就被析构了。

第十八条：避免使用vector

vector<bool>并不是一个真正的容器，也并不存储真正的bool类型，为了节省空间，它存储的是bool的紧凑表示，通常是一个bit。
由于指向单个bit的指针或引用都是不被允许的，vector<bool>采用代理对象模拟指针指向单个bit。

vector<bool> v;
//...

bool *pb = &v[0]; // compile error
vector<bool>::reference *pr = &v[0];  // OK

可以考虑两种方式替代vector<bool>

deque<bool>但是要注意deque的内存布局与数组并不一致
bitset不是STL容器所以不支持迭代器，其大小在编译器就已经确定，bool也是紧凑的存储在内存中。

关联容器

第十九条：理解相等(equality)和等价(equivalence)的区别　　

相等的概念是基于operator==的，也就是取决于operator==的实现。等价关系是基于元素在容器中的排列顺序的，如果两个元素谁也不能排列在另一个的前面，那么这两个元素是等价的。标准关联容器需要保证内部元素的有序排列，所以标准容器的实现是基于等价的。标准关联容器的使用者要为所使用的容器指定一个比较函数(默认为less)，用来决定元素的排列顺序。

非成员的函数(通常为STL算法)大部分是基于相等的。下列代码可能会返回不同的结果

struct CIStringCompare:
    public binary_function<string, string, bool> {
    bool operator()(const string& lhs,
                    const string& rhs) const
    {
        int i = stricmp(lhs.c_str(),rhs.c_str());
        if(i < 0)
            return true;
        else
            return false;
    }
};

set<string, CIStringCompare> s; //set的第二个参数是类型而不是函数
s.insert("A");

if(s.find("a") != s.end())  //true
{
    cout<<"a";
}

if(find(s.begin(),s.end(),"a") != s.end())   //false
{
    cout<<"a";
}

第二十条：为包含指针的关联容器指定比较类型　　

下面的程序通常不会得到用户期望的结果。

set<string*> s;
s.insert(new string("A"));
s.insert(new string("C"));
s.insert(new string("B"));

for(set<string*>::iterator i = s.begin(); i != s.end(); i++)
{
    cout<<**i;  //输出一定会是ABC么？
}

因为set中存储的是指针类型，而它也仅仅会对指针所处的位置大小进行排序，与指针所指向的内容无关。当关联容器中存储指针或迭代器类型的时候，往往需要用户自定义一个比较函数来替换默认的比较函数。

struct CustomedStringCompare:
    public binary_function<string*, string*, bool> {
    bool operator()(const string* lhs,
                    const string* rhs) const
    {
        return *lhs < *rhs;
    }
};

set<string*,CustomedStringCompare> s;
s.insert(new string("A"));
s.insert(new string("C"));
s.insert(new string("B"));

for(set<string*, CustomedStringCompare>::iterator i = s.begin(); i != s.end(); i++)
{
    cout<<**i; //ABC
}

　　
可以更进一步的实现一个通用的解引用比较类型

struct DerefenceLess{
    template<typename PtrType>
    bool operator()(PtrType ptr1, PtrType ptr2) const
    {
        return *ptr1 < *ptr2;
    }
};

set<string*,DerefenceLess> s;

如果用less_equal来实现关联容器中的比较函数,那么对于连续插入两个相等的元素则有

1
2
3

set<int,less_equal<int>> s;
s.insert(1);
s.insert(1);

因为关联容器是依据等价来实现的,所以判断两个1是否等价!

1	!(1<=1) && !(1<=1) // false 不等价

所以这两个1都被存储在set中,从而破坏了set中不能有重复数据的约定.　

比较函数的返回值表明元素按照该函数定义的顺序排列,一个值是否在另一个之前。相等的值不会有前后顺序，所以，对于相等的值，比较函数应该返回false。

对于multiset又如何呢？multiset应该可以存储两个相等的元素吧？答案也是否定的。对于下面的操作:

multiset<int,less_equal> s;
s.insert(1);
s.insert(1);

pair<multiset<int,less_equal>::iterator,multiset<int,less_equal>::iterator> ret = s.equal_range(1);

返回的结果并不是所期望的两个1。因为equal_range的实现(lower_bound:第一个不小于参数值的元素(基于比较函数的小于), upper_bound:第一个大于参数值的元素)是基于等价的，而这两个1基于less_equal是不等价的，所以返回值中比不存在1。

事实上，上面的代码在执行时会产生错误。VC9编译器Debug环境会在第3行出错，Release环境会在之后用到ret的地方发生难以预测的错误。

第二十二条：切勿直接修改set或multiset的键　　

set、multiset、map、multimap都会按照一定的顺序存储其中的元素，但如果修改了其中用于排序的键值，则将会破坏容器的有序性。

对于map和multimap而言，其存储元素的类型为pair<const key, value>，修改map中的key值将不能通过编译(除非使用const_cast)。对于set和multiset，其存储的键值并不是const的，在修改其中元素的时候，要小心不要修改到键值。

class Employee
{
public:
    int id;
    string title;
};

struct compare:
    public binary_function<Employee&, Employee&, bool> {
    bool operator()(const Employee& lhs,
                    const Employee& rhs) const
    {
        return lhs.id < rhs.id;
    }
};

set<Employee,compare> s;

Employee e1,e2;

e1.id = 2;
e1.title = "QA";

e2.id = 1;
e2.title = "Developer";

s.insert(e1);
s.insert(e2);

set<Employee,compare>::iterator i = s.begin();
i->title = "Manager"; //OK to update non-key value
i->id = 3; // 破坏了有序性

　　
有些STL的实现将set<T>::iterator的operator*返回一个const T&，用来保护容器中的值不被修改，在这种情况下，如果希望修改非键值，必须通过const_case。

set<Employee,compare>::iterator i = s.begin();
const_cast<Employee&>(*i).title = "Manager"; //OK
const_cast<Employee*>(&*i).title = "Arch"; //OK
const_cast<Employee>(*i).title = "Director"; // Bad 仅仅就修改了临时变量的值 set中的值没有发生改变

对于map和multimap而言，尽量不要修改键值，即使是通过const_cast的方式，因为STL的实现可能将键值放在只读的内存区域当中。

相对安全(而低效)的方式来修改关联容器中的元素

找到希望修改的元素。
将要被修改的元素做一份拷贝。(注意拷贝的Map的key值不要声明为const)
修改拷贝的值。
从容器中删除元素。(erase 见第九条)
插入拷贝的那个元素。如果位置不变或邻近，可以使用hint方式的insert从而将插入的效率从对数时间提高到常数时间。

set<Employee,compare> s;

Employee e1,e2;

e1.id = 2;
e1.title = "QA";

e2.id = 1;
e2.title = "Developer";

s.insert(e1);
s.insert(e2);

set<Employee,compare>::iterator i = s.begin();
Employee e(*i);
e.title = "Manager";

s.erase(i++);
s.insert(i,e);

第二十三条：考虑使用排序的vector替代关联容器　　

哈希容器大部分情况下可以提供常数时间的查找效率，标准容器也可以达到对数时间的查找效率。

标准容器通常基于平衡二叉树实现，这种实现对于插入、删除和查找的混合操作提供了优化。但是对于3步式的操作(首先进行插入操作，再进行查找操作，再修改元素或删除元素)，排序的vector能够提供更好的性能。因为相对于vector，关联容器需要更大的存储空间。在排序的vector中存储数据比在关联容器中存储数据消耗更少的内存，考虑到页面错误的因素，通过二分搜索进行查找，排序的vector效率更高一些。

如果使用排序的vector替换map，需要实现一个自定义的排序类型，该排序类型依照键值进行排序。

第二十四条：当效率至关重要时，请在map:operator[]和map:insert之间谨慎作出选择　

从效率方面的考虑，当向map中添加元素时，应该使用insert，当需要修改一个元素的值的时候，需要使用operator[]
如果使用operator[]添加元素

class Widget{
};

map<int,Widget> m;
Widget w;

m[0] = w；
//Widget构造函数被调用两次

对于第8行，如果m[0]没有对应的值，则会通过默认的构造函数生成一个widget对象，然后再用operator=将w的值赋给这个widget对象。使用insert可以避免创建这个中间对象。

map<int,Widget> m;
Widget w; 

m.insert(map<int,Widget>::value_type(0,w));  //没有调用构造函数

如果使用insert修改元素的值（当然，不会有人这样做）

map<int,Widget> m;
Widget w(1); 
m.insert(map<int,Widget>::value_type(0,w)); 

Widget w2(2);

m.insert(map<int,Widget>::value_type(0,w2)).first->second = w2;  //构造了一个pair对象

// 上面这段代码比较晦涩
// map::insert(const value_type& x)的返回值为pair<iterator,bool> 
// 当insert的值已经存在时，iterator指向这个已经存在的值，bool值为false。
// 反之，指向新插入的值，bool值为true。

使用operator[]则轻便且高效的多

map<int,Widget> m;
Widget w(1); 
m.insert(map<int,Widget>::value_type(0,w));

Widget w2(2);

m[0] = w2;

　
一个通用的添加和修改map中元素的方法

template<typename MapType,
         typename KeyType,
         typename ValueType>
typename MapType::iterator InsertOrUpdate(MapType& map,const KeyType& k, const ValueType& v) // 注意typename的用法 从属类型前一定要使用typename
{
    typename MapType::iterator i = map.lower_bound(k); // 如果i！=map.end()，则i->first不小于k

    if(i!=map.end() && !map.key_comp()(k,i->first)) // k不小于i->first 等价！
    {
        i->second = v;
        return i;
    }

    else
    {
        return map.insert(i,pair<const KeyType, ValueType>(k,v));
    }
};

map<int,Widget> m;
Widget w(1); 

map<int,Widget>::iterator i  = InsertOrUpdate<map<int,Widget>,int,Widget>(m,0,w);

第二十五条：熟悉非标准的哈希容器

常见的hash容器的实现有SGI和Dinkumware，SGI的hashset的声明类似于

template<typename T,
         typename HashFunction = hash<T>,
         typename CompareFunction = equal_to<T>,
         typename Allocator = allocator<T>>
class hashSet;

Dinkumware的hash_set声明

template<typename T,
         typename CompareFunction>
class hash_compare;

template<typename T,
         typename HashingInfo = hash_compare<T,less<T>>,
         typename Allocator = allocator<T>>
class hash_set;

SGI使用传统的开放式哈希策略，由指向元素的单向链表的指针数组(桶)构成。Dinkumware同样使用开放式哈希策略，由指向元素的双向链表的迭代器数组(桶)组成。从内存的角度上讲，SGI的设计要节省一些。

迭代器

第二十六条： iterator优先于const_iterator, reverse_iterator以及const_reverse_iterator

对于容器类container<T>而言，

iterator的功效相当与T*
const_iterator的功效相当于 const T*
reverse_iterator与const_reverse_iterator与前两者类似，只是按照反向遍历

它们之间相互转换的关系如图

从iterator到const_iterator和reverse_iterator存在隐式转换，从reverse_iterator到const_iterator也存在隐式转换。

通过base()可以将reverse_iterator转换为iterator，同样可以将const_reversse_iterator转换为const_iterator，但是转换后的结果并不指向同一元素(有一个偏移量)

第二十七条：使用distance和advance将容器的const_iterator转换成iterator

对于大多数的容器，const_cast并不能将const_iterator转换为iterator。即使在某些编译器上可以将vector和string的const_iterator转换为iterator，但存在移植性的问题

通过distance和advance将const_iterator转换为iterator的方法

vector<Widget> v;

typedef vector<Widget>::const_iterator ConstIter;
typedef vector<Widget>::iterator Iter;

ConstIter ci; 

... //使ci指向v中的元素
Iter i = v.begin();
advance(i,distance<ConstIter>(i,ci));

第二十八条：正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

使用reverse_iterator的base()成员函数所产生的iterator和原来的reverse_iterator之间有一个元素的偏移量。

容器的插入、删除和修改操作都是基于iterator的，所以对于reverse_iterator，必须通过base()成员函数转换为iterator之后才能进行增删改的操作。

对于插入操作而言，新插入的元素都在3和4之间，所以可以直接使用insert(ri.base(),xxx)
对于修改和删除操作，由于ri和ri.base()并不指向同一元素，所以在修改和删除前，必须修正偏移量

修正ri和ri.base()偏移量的做法

set<Widget> s;

typedef set<Widget>::reverse_iterator RIter;

RIter ri;

... //使ri指向v中的元素 

s.erase(--ri.base()); //直接修改函数返回的指针不能被直接修改。 如果iterator是基于指针实现的，代码将不具有可以执行。
s.erase((++ri).base()); //具备可移植性的代码

第二十九条：对于逐个字符的输入请考虑使用istreambuf_iterator

常用的istream_iterator内部使用的operator>>实际上执行了格式化的输入，每一次的operator>>操作都有很多的附加操作

一个内部sentry对象的构造和析构(设置和清理行为的对象)
检查可能影响行为的流标志(比如skipws)
检查可能发生的读取错误
出现错误时检查流的异常屏蔽标志以决定是否抛出异常

对于istreambuf_iterator，它直接从流的缓冲区中读取下一个字符，不存在任何的格式化，所以效率相对istream_iterator要高得多。对于非格式化的输出，也可以考虑使用ostreambuf_iterator代替ostream_iterator。（损失了格式化输出的灵活性）

算法

第三十条：确保目标区间足够大

下面例子中,希望将一个容器中的内容添加到另一个容器的尾部

int transformogrify(int x); //将x值做一些处理，返回一个新的值

vector<int> values;

vector<int> results;

... //初始化values

transform(values.begin(),values.end(),results.end(),transformogrify);

由于results.end()返回的迭代器指向一段未初始化的内存，上面的代码在运行时会导致无效对象的赋值操作。

可以通过back_inserter或者front_inserter来实现在头尾插入另一个容器中的元素。因为front_inserter的实现是基于push_front操作(vector和string不支持push_front)，所以通过front_inserter插入的元素与他们在原来容器中的顺序正好相反，这个时候可以使用reverse_iterator。

int transformogrify(int x); //将x值做一些处理，返回一个新的值
vector<int> values;
vector<int> results;

... //初始化values
transform(values.begin(),values.end(),back_inserter(results),transformogrify);
int transformogrify(int x); //将x值做一些处理，返回一个新的值

deque<int> values;
deque<int> results;

... //初始化values
transform(values.rbegin(),values.rend(),front_inserter(results),transformogrify);

另外可以使用inserter在results的任意位置插入元素

int transformogrify(int x); //将x值做一些处理，返回一个新的值

vector<int> values;
vector<int> results;

... //初始化values
transform(values.begin(),values.end(),inserter(results,results.begin()+results.size()/2),transformogrify); //插入中间

书中提到“但是，如果该算法执行的是插入操作，则第五条中建议的方案(使用区间成员函数)并不适用”，不知是翻译的问题还是理解不到位，为什么插入操作不能用区间成员函数替换？在我看来是因为区间成员函数并不支持自定义的函数对象，而这又跟插入操作有什么关系呢？莫非删除可以？？？

如果插入操作的目标容器是vector或string，可以通过reserve操作来避免不必要的容器内存重新分配。

int transformogrify(int x); //将x值做一些处理，返回一个新的值

vector<int> values;
vector<int> results;

//... //初始化values
results.reserve(values.size()+results.size()); //预留results和values的空间
transform(values.begin(),values.end(),back_inserter(results),transformogrify);

如果操作的结果不是插入而是替换目标容器中的元素，可以采用下面的两种方式

int transformogrify(int x); //将x值做一些处理，返回一个新的值

vector<int> values;

vector<int> results;

//... //初始化values

results.resize(values.size()); //想想对于results.size() > values.size() 和results.size() < values.size()两种情况
transform(values.begin(),values.end(),results.begin(),transformogrify);
int transformogrify(int x); //将x值做一些处理，返回一个新的值

vector<int> values;
vector<int> results;

//... //初始化values

results.clear(); //results.size()为，results.capacity()不变
results.reserve(values.size()); //相对于上一种方式，如果values.size()小于原来的results.size(),那么会空余出一些元素的内存。
transform(values.begin(),values.end(),results.begin(),transformogrify);

第三十一条：了解各种与排序有关的选择

对vector、string、deque或数组中的元素执行一次完全排序，可以使用sort或stable_sort

vector<int> values;
values.push_back(4);
values.push_back(1);
values.push_back(2);
values.push_back(5);
values.push_back(3);
sort(values.begin(),values.end()); // 1,2,3,4,5

对vector、string、deque或数组中的元素选出前n个进行并对这n个元素进行排序，可以使用partial_sort

1	partial_sort(values.begin(),values.begin()+2,values.end()); // 1,2,4,5,3 注意第二个参数是一个开区间

对vector、string、deque或数组中的元素，要求找到按顺序排在第n个位置上的元素，或者找到排名前n的数据，但并不需要对这n个数据进行排序，这时可以使用nth_element

1	nth_element(values.begin(),values.begin()+1,values.end()); // 1,2,3,4,5 注意第二个参数是一个闭区间

这个返回的结果跟我期望的有些差距，期望的返回值应该是1，2，4，5，3。VC10编译器

对于标准序列容器(这回包含了list),如果要将其中元素按照是否满足某种特定的条件区分开来，可以使用partition或stable_partition

1
2

vector<int>::iterator firstIteratorNotLessThan3 = partition(values.begin(),values.end(),lessThan3); //返回值为 2,1,4,5,3
vector<int>::iterator firstIteratorNotLessThan3 = stable_partition(values.begin(),values.end(),lessThan3); //返回值为 1,2,4,5,3

对于list而言，它的成员函数sort保证了可以stable的对list中元素进行排序。对于nth_element和partition操作，有三种替代方案：

将list中的元素拷贝到提供随机访问迭代器的容器中，然后执行相应的算法
创建一个list::iterator的容器，在对容器执行相应的算法
利用一个包含迭代器的有序容器的信息，反复调用splice成员函数，将list中的成员调整到相应的位置。

第三十二条：如果确实要删除元素，请确保在remove这一类算法以后调用erase

remove算法接受两个迭代器作为参数，这两个迭代器指定了需要进行操作的区间。Remove并不知道它所操作的容器，所以并不能真正的将容器中的元素删除掉。

vector<int> values;

for(int i=0; i<10; i++) {
    values.push_back(i);
}

values[3] = values[5] = values[9] = 99;
remove(values.begin(),values.end(),99); // 0,1,2,4,6,7,8,7,8,99

从上面的代码可见，remove并没有删除所有值为99的元素，只不过是用后面元素的值覆盖了需要被remove的元素的值，并一一填补空下来的元素的空间，对于最后三个元素，并没有其他的元素去覆盖他们的值，所以仍然保留原值。

上图可以看出，remove只不过是用后面的值填补了空缺的值，但并没有将容器中的元素删除，所以在remove之后，要调用erase将不需要的元素删除掉。

1	values.erase(remove(values.begin(),values.end(),99),values.end()); // 0,1,2,4,6,7,8

类似于remove的算法还有remove_if和unique, 这些算法都没有真正的删除元素，习惯用法是将它们作为容器erase成员函数的第一个参数。List是容器中的一个例外，它有remove和unique成员函数，而且可以从容器中直接删除不需要的元素。

第三十三条：对于包含指针的容器使用remove这一类算法时要特别小心

class Widget{
public:
...
bool isCertified() const;
...
};

vector<Widget*> v;

for(int i=0; i<10; i++)
{
    v.push_back(new Widget());
}

v.erase(remove_if(v.begin(),v.end(),not1(mem_fun(&Widget::isCertified))),v.end());

上面的代码可能会造成内存泄漏

避免内存泄漏的方式有两种，第一种是先将需要被删除的元素的指针删除并设置为空，然后再删除容器中的空指针。第二种方式更为简单而且直观，就是使用智能指针。

方案1

void delAndNullifyUncertified(Widget*& pWidget)
{
    if(!pWidget->isCertified())
    {
        delete pWidget;
        pWidget = 0;
    }
}

vector<Widget*> v;

for(int i=0; i<10; i++)
{
    v.push_back(new Widget());
}

for_each(v.begin(),v.end(),delAndNullifyUncertified);

v.erase(remove(v.begin(),v.end(),static_cast<Widget*>(0)),v.end());

方案2

template<typename T>
class RCSP{...}; // Reference counting smart pointer

typedef RSCP<Widget> RSCPW;

vector<RSCPW> v;

for(int i=0; i<10; i++)
{
    v.push_back(RSCPW(new Widget()));
}

v.erase(remove_if(v.begin(),v.end(),not1(mem_fun(&Widget::isCertified))),v.end());

第三十四条：了解哪些算法要求使用排序的区间作为参数

用于查找的算法binary_search, lower_bound, upper_bound和equal_range采用二分法查找数据，所以数据必须是事先排好序的。对于随机访问迭代器，这些算法可以保证对数时间的查找效率，对于双向迭代器，需要线性时间
set_union, set_intersection, set_difference和set_symmetric_difference提供了线性时间的集合操作。排序的元素是线性效率的前提。
merge和inplace_merge实现了合并和排序的联合操作。读入两个排序的区间，合并成一个新的排序区间。具有线性时间的性能。
includes,判断一个区间中的元素是否都在另一个区间之中。具有线性的时间性能。
unique和unique_copy不一定需要排序的区间，但一般来说只有针对排序的区间才能删除所有的重复数据，否则只是保留相邻的重复数据中的第一个。

针对一个区间的进行多次算法的操作，要保证这些算法的排序方式是一致的。(比如都是升序或都是降序)

第三十五条：通过mismatch和lexicographical_compare实现简单的忽略大小写的字符串比较

Mismatch的作用在于找出两个区间中第一个对应值不同的位置。要实现忽略大小写的字符串比较，可以先找到两个字符串中第一个不同的字符，然后通过比较这两个字符的大小。

int ciStringCompareImpl(const string& s1, const string& s2)
{
    typedef pair<string::const_iterator, string::const_iterator> PSCI; //pair of string::const_iterator

    PSCI p = mismatch(s1.begin(),s1.end(),s2.begin(),not2(ptr_fun(ciCharCompare)));

    if(p.first == s1.end())
    {
        if(p.second == s2.end()) return 0;
        else return -1;
    }

    return ciCharCompare(*p.first,*p.second);
}

Lexicograghical_compare是strcmp的一个泛化的版本，strcmp只能与字符数组一起工作，而lexicograghical_compare可以与任何类型的值区间一起工作。

bool charLess(char c1, char c2);

bool ciStringCompair(const string& s1, const string& s2)
{
    return lexicographical_compare(s1.begin(),s1.end(),s2.begin(),s2.end(),charLess);
}

第三十六条：理解copy_if算法的正确实现

标准的STL中并不存在copy_if算法，正确的copy_if算法的实现如下所示：

template<typename InputIterator,
              typename OutputIterator,
              typename Predicate>
OutputIterator copy_if(InputIterator begin,
                                     InputIterator end,
                                     OutputIterator destBegin,
                                     Predicate p)
{
    while(begin != end)
    {
        if(p(*begin))
        {
            *destBegin++ = *begin;
            ++begin;
        }

        return destBegin;
    }
}

第三十七条：使用accumulate或者for_each进行区间统计

accumulate有两种形式，第一种接受两个迭代器和一个初始值，返回结果是初始值与两个迭代器区间的元素的总和。

1
2
3

vector<int> v;
...
accumulate(v.begin(),v.end(),0);

第二种方式加了一个统计函数，使得accumulate函数变得更加通用。

1
2
3

vector<string> v;
...
accumulate(v.begin(),v.end(),static_cast<string::size_type>(0), StringLegthSum);

accumulate的一个限制是不能产生任何的副作用，这时，for_each就是一个很好的补充。For_each接受三个参数，两个迭代器确定的一个区间，以及统计函数。For_each的返回值是一个函数对象，必须通过调用函数对象中的方法才能够取得统计的值。

struct Point
{
    Point(double _x, double _y):x(_x),y(_y)
    {
    }

    double x,y;
}

class PointAverge : public unary_function<Point,void>
{
public:
    PointAverage(): sum_x(0.0), sum_y(0.0),sum(0)
    {
    }

    void operator()(const Point& p) //可以产生副作用
    {
        sum++;
        sum_x += p.x;
        sum_y += p.y;
    }

    Point GetResult() //用于返回统计结果
    {
        return Point(sum_x/sum, sum_y/sum);
    }

private:

    double sum_x, sum_y;
    nt sum;
}

vector<Point> v;
...
Point result = for_each(v.begin(),v.end(),PointAverage()).GetResult();

函数子、函数子类、函数及其他

第三十八条遵循按值传递的原则来设计函数子类

c和C++中以函数指针为参数的例子，函数指针是按值传递的

1
2
3

void qsort(void* base, size_t nmemb, size_t size,

int(*cmpfcn)(const void *, const void *));

STL函数对象是对函数指针的抽象形式，在STL中函数对象在函数中的传递也是按值传递的。for_each算法的返回值就是一个函数对象，它的第三个参数也是函数对象。

template<class InputIterator,
class Function>
Function //按值返回
for_each(InputIterator first, InputIterator second, Function f); //按值传递

因为STL函数对象按值传递的特性，所以在设计函数对象时要：

将函数对象要尽可能的小，以减少拷贝的开销。
函数对象尽量是单态的(不要使用虚函数)，以避免剥离问题。

对于复杂的设计而言，具有包含很多信息的和含有继承关系的函数对象也可能难以避免，这时可以采用Bridge Pattern来实现

template<typename T>
class functorImp :
public unary_function<T,void> {
private :
    Widget w;
    int x;

public :
    virtual ~functorImp();
    virtual void operator() (const T& val) const;
    friend class functor<T>;
};

template<typename T>
class functor :
public unary_function<T,void> {
private:
    functorImp<T> *pImp; //唯一的一个数据成员

public:
    void operator() (const T& val) const
    {
        pImp->operator()(val); //调用重载的operator
    }
};

函数对象本身只包含一个指针，而且是不含虚函数的单态对象。真正的数据和操作都是由指针所指向的对象完成的。对于这个实现，要注意的是在函数对象拷贝的过程中，如何维护这个指针成员。既能避免内存泄漏而且可以保证指针有效性的智能指针是个不错的选择。

1	shared_ptr<functorImp<T> *> pImp;

第三十九条确保判别式是纯函数

判别式的一些基本概念：

判别式 - 返回值为bool类型或者可以隐式转换为bool类型的函数
纯函数 - 返回值仅与函数的参数相关的函数
判别式类 – operator()函数是判别式的函数子类。 STL中凡是能接受判别式的地方，就可以接受一个判别式类的对象。

对于判别式不是纯函数的一个反例

class Remove3rdElement 
: public unary_function<int,bool> {
public:

    Remove3rdElement():i(0){}

    bool operator() (const int&)
    {
        return ++i == 3;
    }

    int i;
};
...
vector<int> myvector;
vector<int>::iterator it;

myvector.push_back(1);
myvector.push_back(2);
myvector.push_back(3);
myvector.push_back(4);
myvector.push_back(5);
myvector.push_back(6);
myvector.push_back(7);
myvector.erase(remove_if(myvector.begin(), myvector.end(), Remove3rdElement()),myvector.end()); // 1，2，4，5，7 remove_if之后的结果为 1，2，4，5，7，6，7。 返回值指向的是第六个元素。

第四十条如果一个类是函数子，应该使它可配接

STL中四个标准的函数配接器(not1, not2, bind1st, bind2nd)要求其使用的函数对象包含一些特殊的类型定义，包含这些类型定义的函数对象称作是可配接的函数对象。下面的代码无法通过编译：

bool isWanted(const int i)；

...

vector<int> myvector;
vector<int>::iterator it = find_if(myvector.begin(), myvector.end(), not1(isWanted)); // error C2955: 'std::unary_function' : use of class template requires template argument list

从上面的错误可以看出，这个isWanted函数指针不能被not1使用，因为缺少了一些模板参数列表。ptr_fun的作用就在于给予这个函数指针所需要的类型定义从而使之可配接。

1	vector<int>::iterator it = find_if(myvector.begin(), myvector.end(), not1(ptr_fun(isWanted)));

这些特殊的类型定义包括: argument_type``first_argument_type``second_argument_type``result_type，提供这些类型定义最简单的方式是是函数对象的类从特定的模板继承。

如果函数子类的operator方法只有一个实参，那么应该从unary_function继承；如果有两个实参，应该从binary_function继承。对于unary_function和binary_function，必须指定参数类型和返回值类型。

template<typename T>
class functor : public unary_function<int, bool>
{
public :
    bool operator()(int);
};

template<typename T>
class functor2 : public binary_function<int, double, bool>
{
public :
    bool operator()(int, double, bool);
};

对于operator方法的参数:

operator的参数如果是非指针类型的，传递给unary_function和binary_function的参数需要去掉const和引用&符号
operator的参数如果是指针类型的，传递给unary_function和binary_function的参数要与operator的参数完全一致。

第四十一条理解ptr_fun、mem_fun和mem_fun_reference的来由

对于ptr_fun在第40条已经有了一些介绍，它可以用在任何的函数指针上来使其可配接。下面的例子，希望在myvector和myvector2的每一个元素上调用元素的成员函数。

class Widget
{
public :
    void test();
};

...

vector<Widget> myvector;
vector<Widget*> myvector2;

...

for_each(myvector.begin(),myvector.end(), &Widget::test); // 编译错误
for_each(myvector2.begin(),myvector2.end(), &Widget::test); //编译错误

而for_each的实现可能是这样的

template<typename InputIterator, typename Function>
Function for_each(InputIterator begin, InputIterator end, Function f)
{
    while (begin != end)
        f(*begin++);
}

对于mem_fun和mem_fun_reference, 就是要使成员方法可以作为合法的函数指针传递

1
2

for_each(myvector.begin(),myvector.end(), mem_fun_ref(&Widget::test)); // 当容器中的元素为对象时使用mem_fun_ref
for_each(myvector2.begin(),myvector2.end(), mem_fun(&Widget::test)); // 当容器中的元素为指针时，使用mem_fun

那么mem_fun是如何实现的呢？

1
2
3

template<typename R, typename C>
mem_fun_t<R,C>
mem_fun(R(C::*pmf)());

mem_fun接受一个返回值为R且不带参数的C类型的成员函数，并返回一个mem_fun_t类型的对象。mem_fun_t是一个函数子类，拥有成员函数的指针，并提供了operator()接口。operator中调用了通过参数传递进来的对象上的成员函数。

第四十二条确保less与operator<具有相同的语义

STL规定，less总是等价于operator<, operator<是less的默认实现。

应当尽量避免修改less的行为，而且要确保它与operator<具有相同的意义。如果希望以一种特殊的方式来排序对象，那么就去创建一个新的函数子类，它的名字不能是less.

在程序中使用STL

第四十三条：算法调用优先于手写的循环

算法往往作用于一对迭代器所指定的区间中的每一个元素上，所以算法的内部实现是基于循环的。虽然说类似于find和find_if的算法可能不会遍历所有的元素就返回了结果，但是在极端情况下，还是需要遍历全部的元素。

第四十四条：容器的成员函数优于同名的算法

成员函数速度优于同名算法
成员函数与容器的联系更加紧密

对于关联容器请看下面的例子:

1
2
3

set<int> s;
set<int>::iterator i1 = s.find(727);
set<int>::iterator i2 = find(s.begin(), s.end(), 727);

对于set而言，它的find成员函数的时间复杂度是log(n)，而算法find的时间复杂度是线性的n。明显，成员函数的效率要远高于算法。另外，算法是基于相等性而关联容器基于等价性，在这种情况下，调用成员函数和调用算法可能会得到不同的结果。(参见第19条)对于map以及multimap，成员函数之针基于key进行操作，而算法基于key-value pair进行操作。对于list而言，成员函数相对于算法的优势更加明显。算法是基于元素的拷贝的，而list成员函数可能只需要修改指针的指向。还有之前所提到的list的remove成员函数，同时起到了remove和erase的作用。

有些算法，例如sort并不能应用在list上，因为sort是基于随机访问迭代器的。还有merge算法，它要求不能修改源区间，而merge成员函数总是在修改源链表的元素的指针指向。

第四十五条：正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

count: 区间内是否存在某个特定的值，如果存在的话，这个值有多少个拷贝。
find: 区间内时候存在某个特定的值，如果存在的话，第一个符合条件的值在哪里。
binary_search：一个排序的区间内是否存在一个特定的值。
lower_bound：返回一个迭代器，或者指向第一个满足条件的元素，或者指向适合于该值插入的位置。切记lower_bound是基于等价性的，用相等性来比较lower_bound的返回值和目标元素是存在潜在风险的。
upper_bound：返回一个迭代器，指向最后一个满足条件元素的后面一个元素。
equal_range：返回一对迭代器，第一个指向lower_bound的返回值，第二个指向upper_bound的返回值。如果两个返回值指向同一位置，则说明没有符合条件的元素。Lower_bound与upper_bound的distance可以求得符合条件的元素的个数。

下表总结了在什么情况下使用什么样的算法或成员函数

对于multi容器来说，find并不能保证找出的元素是第一个具有此值的元素。如果希望找到第一个元素，必须通过lower_bound，然后在通过等价性的验证。Equal_range是另外一种方式，而且可以避免等价性测试，只是equal_range的开销要大于lower_bound。

第四十六条：考虑使用函数对象而不是函数作为STL算法的参数

函数对象优于函数的第一个原因在于函数对象的operator方法可以被优化为内联函数，从而使的函数调用的开销在编译器被消化。而编译器并没有将函数指针的间接调用在编译器进行优化，也就是说，函数作为STL算法的参数相对于函数对象而言，具有函数调用的开销。

第二个理由是某些编译器对于函数作为STL的参数支持的并不好。

第三个理由是有助于避免一些微妙的、语言本身的缺陷。比如说实例化一个函数模板，可能会与其他已经预定义的函数产生冲突。

第四十七条：避免产生“直写型”(write-only)的代码

根据以往的经验，代码被阅读的次数要远远多于被编写的次数，所以要有意识的写出具备可读性的代码。对于STL而言，则是尽量避免“直写型”的代码。

直写型的代码是这样的，对于程序的编写者而言，它显得非常的直接，并且每一步都符合当初设计的逻辑。但是对于程序的阅读者来说，在没有全面了解程序编写者动机的前提下，这样的代码往往让人一头雾水。

1	v.erase(remove_if(find_if(v.rbegin(),v.rend(),bind2nd(greater_equaql<int>(),y)).base()),v.end(),bind2nd(less<int>(),x));

比较易读的写法最好是这样的

// 初始化range_begin，使它指向v中大于等于y的最后一个元素之后的那个元素
// 如果不存在这样的元素，则rangeBegin被初始化为v.begin()
// 如果这个元素恰好是v的最后一个元素，则range_begin将被初始化为v.end()
VecIt rangeBegin = find_if(v.rbegin(),v.rend(),bind2nd(greater_equal<int>(),y)).base();

// 从rangeBegin到v.end()的区间中，删除所有小于x的值
v.erase(remove_if(rangeBegin,v.end(),bind2nd(less<int>(),x)),v.end());

第四十八条总是include正确的头文件

与STL头文件相关的一些总结

几乎所有的STL容器都被声明在与之同名的头文件之中
除了accumulate、inner_product、adjacent_difference和partial_sum被声明在<numeric>中之外，其他都所有算法都声明在<algorithm>中
特殊类型的迭代器，例如isteam_iterator和istreambuf_iterator，都被声明在<iterator>中
标准的函数子，比如less<T>，和函数子配接器，比如not1、bind2nd都被声明在<functional>中。

第四十九条学会分析与STL相关的编译器诊断信息

STL的编译错误信息往往冗长而且难以阅读，通过文本替换将复杂的容器名称替换为简单的代号，可以使得错误信息得到简化。

例如，将std::basic_string<char, std::char_traits<char>, std::allocator<char>>替换为可读性更强的string。

下面列举一些常见的STL错误，以及可能的出错原因

Vector和string的迭代器通常就是指针，当错误的使用iterator的时候，编译器的错误信息中可能会包含指针类型的错误。
如果诊断信息提到了back_insert_iterator, front_insert_iterator和insert_iterator，则几乎意味着程序中直接或间接地调用了back_inserter, front_inserter或者是inserter。
输出迭代器以及inserter函数返回的迭代器在赋值操作符内部完成输入或者插入操作，如果有赋值操作符有关的错误信息，可以关注这些迭代器。
如果错误信息来自于算法的内部实现，往往意味着传递给算法的对象使用了错误的类型。
如果在使用一个常见的STL组件，但编译器却不认知，可能是没有包含合适的头文件。

第一章 容器

第一条： 慎重选择容器类型

第二条： 不要编写试图独立于容器的代码

第三条： 确保容器内对象的拷贝正确而高效

第四条： 调用empty()而不是检查size()是否为0

第五条： 区间成员函数优先于与之对应的单元素成员函数

第六条：当心C++编译器最烦人的分析机制

第七条：如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

第八条：切勿创建包含auto_ptr对象的容器

第九条：慎重选择删除元素的方法

第十条：了解分配子的约定和限制

第十一条：理解自定义分配子的合理用法

第十二条：切勿对STL容器的线程安全性有不切实际的依赖

vector和string

第十三条： vector和string优先于动态分配的数组

第十四条： 使用reserve来避免不必要的内存分配

第十五条： string实现的多样性

第十六条： 了解如何把vector和string数据传给旧的API

第十七条： 使用swap去除多余容量

第十八条： 避免使用vector

关联容器

第十九条： 理解相等(equality)和等价(equivalence)的区别

第二十条： 为包含指针的关联容器指定比较类型

第二十二条： 切勿直接修改set或multiset的键

第二十三条： 考虑使用排序的vector替代关联容器

第二十四条： 当效率至关重要时，请在map:operator[]和map:insert之间谨慎作出选择

第二十五条： 熟悉非标准的哈希容器

迭代器