这是个人阅读Effective STL所做的读书笔记第二部分，包含《Effective STL》条款11~条款20的笔记内容。

条款11：理解自定义分配器的正确用法

这一条款主要介绍了自定义分配器的使用，例如自定义共享内存分配器：

void* mallocShared(size_t bytesNeeded);    //分配共享内存函数
void freeShared(void *ptr);                //释放共享内存
template<typename T>
class SharedMemoryANocator {
public:
    ...
    pointer allocate(size_type numObiects, const void *localityHint = 0)
    {
        return static_cast<pointer>(mallocShared(numObiects * sizeof(T)));
    }
    void deallocate(pointer ptrToMemory, size_ type numObjects)
    {
        freeShared(ptrToMiemory);
    }
    ...
};

// 方便的typedef
typedef vector<double, SharedMemoryAllocator<double> >
SharedDoubleVec;
...
{
    // 开始一个块
    SharedDoubleVec v; // 建立一个元素在
    // 共享内存中的vector
    ... // 结束这个块
}

以上使用只是对于该例中的double分配于共享内存中，v这个SharedDoubleVec对象本身仍被分配在普通堆中，将v的内容double和v本身放进共享内存，可如下书写：

void *pVectorMemory =                                      // 分配足够的共享内存
                    mallocShared(sizeof(SharedDoubleVec)); // 来容纳一个
                                                           // SharedDoubleVec对象
SharedDoubleVec *pv =                                      // 使用“placement new”来
                    new (pVectorMemory) SharedDoubleVec; // 在那块内存中建立
                                                           // 一个SharedDoubleVec对象；
                                                           // 参见下面
                                                           // 这个对象的使用（通过pv）
...
pv->~SharedDoubleVec();     // 销毁共享内存
                            // 中的对象
freeShared(pVectorMemory);  // 销毁原来的
                            // 共享内存块

自定义内存分配堆类及使用该类的分配器的例子：

class Heap1 {
public:
    ...
    static void* alloc(size_t numBytes, const void *memoryBlockToBeNear);
    static void dealloc(void *ptr);
    ...
};
class Heap2 { ... }; // 有相同的alloc/dealloc接口

template<typenameT, typename Heap>
class SpecificHeapAllocator {
public:
    pointer allocate(size_type numObjects, const void *localityHint = 0)
    {
        return static_cast<pointer>(Heap::alloc(numObjects * sizeof(T),
                                                            localityHint));
    }
    void deallocate(pointer ptrToMemory, size_type numObjects)
    {
        Heap::dealloc(ptrToMemory);
    }
    ...
};

该分配器使用：

vector<int, SpecificHeapAllocator<int, Heap1 > > v;     // 把v和s的元素
set<int, SpecificHeapAllocator<int, Heap1 > > s;         // 放进Heap1
list<Widget, SpecificHeapAllocator<Widget, Heap2> > L;       // 把L和m的元素
map<int, string, less<int>,                             // 放进Heap2
SpecificHeapAllocator<pair<const int, string>,Heap2> > m;

条款12：对STL容器线程安全性的期待现实一些

STL容器关于多线程可以确定的内容：

多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能有任何写入者操作这个容器。
对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。

即在同一时间上允许在一个容器上有多个读者在不同容器上有多个写入者；
固在多线程场景使用STL容器时需要进行同步控制，这里书上写了个一个常见的mutex控制类：

template<typename Container>     // 获取和释放容器的互斥量
class Lock {                                            // 的类的模板核心；
public:                                                    // 忽略了很多细节
    Lock(const Containers container)
            : c(container)
    {
        getMutexFor(c); // 在构造函数获取互斥量
    }
    ~Lock()
    {
        releaseMutexFor(c); // 在析构函数里释放它
    }
private:
    const Container& c;
};

//使用
vector<int> v;
...
{ // 建立新块；
    Lock<vector<int> > lock(v); // 获取互斥量
    vector<int>::iterator first5(find(v.begin(), v.end(), 5));
    if (first5 != v.end()) {
        *first5 = 0;
    }
} // 关闭块，自动
// 释放互斥量

条款13：尽量使用vector和string来代替动态分配的数组

当在准备使用一个动态分配的数组时，可以停下来思考是否可以使用vector或者string来代替。vector和string的优势在于提供了诸如size、begin等成员方法，stl也提供一系列的算法支持，同时会自动管理动态分配的内存。
这里书上提到了一个使用string可能造成的问题，string的实现上会使用到引用计数来消除不必要的内存分配和字符拷贝，但是多线程环境下引用计数将带来并发控制上的消耗。所以当确定当前使用的STL实现中string使用了引用计数，而且在多线程环境下需要考虑性能，可以使用三种方法来规避。其一关闭STL中string引用计数功能开关，通常是使用预处理宏来控制；其二寻找或开发一个不适用引用计数的string实现替代品；其三，考虑使用vector<char>来代替string，vector实现不允许使用引用计数，多线程性能问题不会出现。

条款14：使用reserve来避免不必要的重新分配

vector和string做插入时，如果当前容量已满，新插入元素将导致以下四个动作：

分配新内存款，vector和string的容量每次翻倍；
将原有元素从旧内存拷贝至新内存；
销毁旧内存中的元素；
回收就内存。
这将带来很大时间开销，所以为了避免这些开销，应在vector和string构造后，调用其reserv方法预分配相应大小内存。

条款15：小心string实现的多样性

字符串值可能是或可能不是引用计数的，对于使用了引用计数的版本通常可以是用预处理器宏来关闭，引用计数只对频繁拷贝的字符串有帮助。
string对象的大小可能从1到7倍char*指针的大小
新字符串值的简历可能需要0、1或2次动态分配
string对象可能是或可能不共享字符串的大小和容量信息
string可能是或可能不支持每对象配置器
不同实现对于最小化字符缓冲区的配置器有不同策略

条款16：如何将vector和string的数据传给遗留的API

该条款关注点在于如何将vector和string的数据传给C风格api，对于vector由于vector的实现上使用的是数组，对于C风格数组函数调用可如下传递：

vector v;
void doSomething(const int* pInts, size_t numInts);
if (!v.empty()) {
    doSomething(&v[0], v.size());
}

这里提到了另外一个问题，关于为何应使用&v[0]而不是v.begin()，v.begin()返回的是vector::iterator而不是指针，虽然当前实现上的vector::iterator是指针，但是从语义上来说vector::iterator并不是指针。
对于string只需要使用string的c_str()方法即可：

1 2	void doSomething(const char *pString); doSomething(s.c_str());

需要注意的一点是这里的C风格api都是指向const的指针。对于vector，&v[0]将直接指向其实现连续内存，如果c风格api增加其大小将导致vector本身的size方法不准，特别当当前vector的大小和容量相等时，c风格api内新增元素将直接导致内存越界，另外一个关于vector的问题是对于有序的vector，C风格api可能会修改其顺序；对于string，c_str()方法返回的并不一定是其实现的char*地址，对其操作将导致未知的错误，而且c_str()返回的即是const char*。
这里书上还提到了另一个技巧，当手头上有C风格的api使用数组进行操作，可以利用vector来将各种容器传递给该api：

void doSomething(const int* pints, size_t numInts); // C API (同上)
set<int> intSet; // 保存要传递给API数据的set
...
vector<int> v(intSet.begin(), intSet.end()); // 拷贝set数据到vector
if (!v.empty()) doSomething(&v[0], v.size()); // 传递数据到API

或是反过来利用vector做中间容器：

size_t fillArray(double *pArray, size_t arraySize); // 同上
vector<double> vd(maxNumDoubles); // 一样同上
vd.resize(fillArray(&vd[0], vd.size()));
deque<double> d(vd.begin(), vd.end()); // 拷贝数据到deque
list<double> l(vd.begin(), vd.end()); // 拷贝数据到list
set<double> s(vd.begin(), vd.end()); // 拷贝数据到set

条款17：使用“交换技巧”来修整过剩容量

利用swap方法来“收缩到合适（shink to fit）”，当你的容器经过一系列操作后其容量可能远大于其真实容纳的对象数量，这时可利用swap方法缩小其容量：

1
2
3

class Contestant {...};
vector<Contestant> contestants;
vector<Contestant>(contestants).swap(contestants);

即调用拷贝构造构造一个临时vector，这时拷贝构造只分配需要拷贝元素的内存，在调用swap和原vector进行交换，这样原vector的容量将缩减到合适的大小。
注意这里也只是合适的大小，因为对于vector和string来说，实现上通常会分配保存应有对象数量2的整数次方的容量大小。
对于string可使用同样的方法，这个方法也可以用来清空容器并最小化其容量：

vector&lt;Contestant&gt; v;
string s;
... // 使用v和s
vector<Contestant>().swap(v); // 清除v而且最小化它的容量
string().swap(s); // 清除s而且最小化它的容量

条款18：避免使用vector

作为STL容器的一个必要条件是形如包含T类型的c容器的以下代码能通过编译：

1	T *p = &c[0];

而vector<bool>在上述代码里将无法通过编译，原因是在vector<bool>的实现里为了节省空间使用了bitfield等价的思想来表示它假装容纳bool，也就是说在vector<bool>的实现里真正容纳的并不是bool，vector<bool>operator[]返回的实质为容纳该bool的比特的引用。

vector<bool> v;
bool* pb = &v[0];        //错误！右边的表达式是
                         //vector<bool>::reference*类型，
                         //不是bool*

这里我大概测试了下，在gcc/g++ 8.0里以上取地址操作编译时报错：
cannot convert ‘std::vector<bool>::reference* {aka std::_Bit_reference*}’ to ‘bool*’ in initialization

这里书上没有写明为何STL中vector<bool>是作为一个伪容器的存在，而是转而给出了两个STL中vector<bool>的替代品：deque<bool>和bitset。deque<bool>提供了几乎所有vector所提供的，但其由于内存不连续，无法像vector一样传递给c api；bitset并不是一个容器，它的大小在编译期就已经确定，不支持插入和删除元素，不支持iterator，但它提供只有vector<bool>才有的flip函数和其他操作位集所特有的成员函数。

条款19：了解相等和等价的区别

最简单的相等和等价的例子是find和set的insert方法，find在查询元素时使用的是operator==，使用的是相等的概念；而set的insert方法在搜索插入位置时使用的是等价的概念，基于operator<来查找插入的位置。
标准关联容器使用等价的概念来对容器内元素进行排序（通常是less<key>），即当标准关联容器c：

1	!c.key_comp()(x,y) && !c.key_comp()(y,x)

时认为x和y等价，这在标准关联容器的find和insert方法时将用到；这里提到另一个问题，algorithm里的find和标准关联容器里的成员函数find可能因为使用比较方法不同而导致搜寻结果不同。

条款20：为指针的关联容器指定比较类型

包含指针的关联容器由于自动排序默认将使用指针（less<T>）进行排序，这将导致整个容器内元素的顺序变成一个不可预期的结果，所以对于这种容器最好提供比较方法，这里书上提供了一个仿函数模板示例：

struct DereferenceLess {
    template<typename PtrType>
    bool operator() (PtrType pT1, PtrType pT2) const
    {
        return *pT1 < *pT2;
    }
};

在声明关联容器时就可以像如下声明：

1	set<string*, DereferenceLess> ssp;

注意这里第二个类型参数必须是functor

Joshua's Blog

Effective STL 读书笔记（二）