01 仔细选择你的容器
02 小心对“容器无关代码”的幻想
- 序列容器支持push_front、push_back，但关联容器不支持
- 关联容器提供logN复杂度的lower_bound、upper_bound和equal_range，但序列容器没有
- 不同的容器是不同的，优缺点有重大不同。它们不被设计成可互换的，而且你做不了什么包装的工作
- 若有必要改变容器类型，使用封装简化改变，最简单的就是通过自由地对容器和迭代器类型使用typedef
- 不要这样写
class Widget {...};
vector<Widget> vw;
Widget bestWidget;
... // 给bestWidget一个值
vector<Widget>::iterator i = // 寻找和bestWidget相等的Widget
find(vw.begin(), vw.end(), bestWidget);
class Widget { ... };
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw;
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget);
- 如果问题的改变是简单的加上用户的allocator时特别方便
class Widget { ... };
template<typename T> // 关于为什么这里需要一个template
SpecialAllocator { ... }; // 请参见条款10
typedef vector<Widget, SpecialAllocator<Widget> > WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw; // 仍然能用
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget); // 仍然能用
- typedef不能阻止用户使用（或依赖）任何他们不应该用的（或依赖的）。使用class避免把容器类型暴露给用户，比如建立一个客户列表不要直接用list，建立一个CustomerList类，把list隐藏在private
class CustomerList {
private:
typedef list<Customer> CustomerContainer;
typedef CustomerContainer::iterator CCIterator;
CustomerContainer customers;
public: // 通过这个接口
... // 限制list特殊信息的可见性
};
03 使容器里对象的拷贝操作轻量而正确
- 如果给基类类型容器插入派生类对象，拷入容器时派生类的特有部分会被删除
- 分割问题表明把派生类对象插入基类对象的容器几乎总是错的，解决办法是是建立指针而非对象的容器，拷贝指针很快，不过指针的容器也有STL相关的问题，智能指针的容器是一个好的选择
04 用empty来代替检查size()是否为0
- 事实上empty的典型实现是一个返回size是否返回0的内联函数，对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费线性时间。
05 尽量使用区间成员函数代替他们的单元素兄弟
v1.assign(v2.begin() + v2.size() / 2, v2.end());
- assign对于所有标准序列容器（vector，string，deque和list）都有效，完全代替一个容器内容应该想到赋值
- 不用区间成员函数来解决这个问题，就必须写一个循环遍历赋值，损失效率
vector<Widget> v1, v2; // 假设v1和v2是Widget的vector
v1.clear();
for (vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end(); ++ci)
v1.push_back(*ci);
- 避免循环的一个做法是用copy算法，但其实copy中也存在一个循环，效率损失仍然存在
v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));
v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());
- 使用区间成员函数代码更少也更清晰明确，不仅仅是编程风格的区别，实际上存在效率问题。再比如要把一个int数组拷贝到vector前端，使用insert的区间形式，只有一次调用
int data[numValues]; // 假设numValues在其他地方定义
vector<int> v;
...
v.insert(v.begin(), data, data + numValues); // 把data中的int插入v前部
- 如果用循环迭代调用插入，需要调用numValues次insert，每次insert一个元素到v，插入点以上的每个元素都必须向上移动一次，如果v在插入前有n个元素，则一共会发生n*numValues次移动，如果元素类型为类，则有n*numValues次函数调用：(n-1)*numValues次赋值操作符和numValues次拷贝构造函数
vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
insertLoc = v.insert(insertLoc, data[i]);
++insertLoc;
}
// 或者用copy，本质上和上面代码是一样的
copy(data, data + numValues, inserter(v, v.begin()));
- 区间insert函数直接把现有元素移到最后的位置，开销是每个元素一次移动，共n次移动，numValues次拷贝构造函数，n-numValues次赋值操作符，比单元素插入少n*(numValues-1)次，如果numValues是100，insert的区间形式就少了99%移动
- 用区间版本代替单元素插入的方法时，不要忘记有些单元素变量采用不同的函数名伪装自己。如果一个循环调用push_front或push_back，或一个算法，如copy，参数是front_inserter或者back_inserter，采用insert的区间形式作为优先策略。常见的区间成员函数用法如下
// 区间构造
container::container(InputIterator begin, // 区间的起点
InputIterator end); // 区间的终点
// 区间插入，所有序列容器提供
void container::insert(iterator position, // 区间插入的位置
InputIterator begin, // 插入区间的起点
InputIterator end); // 插入区间的终点
// 关联容器使用比较函数决定元素位置，省略了position参数
void container::insert(lnputIterator begin, InputIterator end);
// 序列容器区间删除
iterator container::erase(iterator begin, iterator end);
// 关联容器区间删除
void container::erase(iterator begin, iterator end);
// 区间赋值
void container::assign(InputIterator begin, InputIterator end);
06 警惕C++最令人恼怒的解析
- 假设有一个int文件，将这些int拷贝到一个list中
ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());
- 想法看上去合理，但实际上编译器会把这句话分析为一个名为data的函数。解决办法是在数据声明中从使用匿名istream_iterator对象后退一步，仅仅给迭代器名字
ifstream dataFile("ints.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd;
list<int> data(dataBegin, dataEnd);
07 当使用new得指针的容器时，记得在销毁容器前delete那些指针
- 当一个指针的容器被销毁时，会销毁每个元素，但new的对象不会调用delete
void f()
{
vector<A*> v;
for (int i = 0; i < 10; ++i)
v.push_back(new A);
...
} // 出了作用域A泄漏！
void f()
{
vector<A*> v;
...
for (vector<A*>::iterator i = v.begin(); i != v.end(); ++i) delete *i;
}
- 但这比for_each代码多且不够清晰，另外这段代码也不是异常安全的，如果删除前抛出异常仍然有资源泄露，所以要把delete放到一个函数对象中
template<typename T>
struct DeleteObject : public unary_function<const T*, void> {
void operator()(const T* ptr) const
{
delete ptr;
}
};
void f()
{
...
for_each(v.begin(), v.end(), DeleteObject<A>);
}
- 然而，这里需要指定删除的对象类型为A，既然v的元素类型已经是A，这里再指出就显得冗余，而且易出错，解决办法是把模板化从DeleteObject移到内部的operator()，编译器知道DeleteObject::operator()的指针类型，通过指针类型自动实例化一个operator()
struct DeleteObject {
template<typename T> // 模板化加在这里
void operator()(const T* ptr) const
{
delete ptr;
}
};
// 使用时无需再指定类型
for_each(v.begin(), v.end(), DeleteObject());
- 但仍不是异常安全的，解决方案是用智能指针容器代替指针容器
void f()
{
vector<shared_ptr<A>> v;
for (int i = 0; i < 10; ++i) v.push_back(shared_ptr<A>(new A));
...
} // 这里没有泄漏
08 永不建立auto_ptr的容器
09 在删除选项中仔细选择
- 删除容器Container<int> c中的所有值为1963的对象，删除方法因容器类型不同而不同，没有通用方法
// 连续内存容器（vector、deque、string）最好的删除方法是erase-remove惯用法
c.erase(remove(c.begin(), c.end(), 1963), c.end());
// list的成员函数直接remove更高效
c.remove(1963);
// 关联容器没有remove，方法是调用erase，只花费对数时间（序列容器为线性时间）
c.erase(1963);
- 如果问题修改为删除bool f(int x)返回值为true的对象，序列容器只要把remove替换为remove_if
c.erase(remove_if(c.begin(), c.end(), f), c.end());
c.remove_if(f); // c为list
- 关联容器有两种方法，一种容易编码但效率低的方法是用remove_copy_if把需要的值拷贝到一个新容器，然后把原容器的内容和新的交换
remove_copy_if(c.begin(), c.end(),
inserter(c2, c2.end()), f);
c.swap(c2);
for (AssocContainer<int>::iterator it = c.begin(); it!= c.end(); ++i) {
if (badValue(*it)) c.erase(it);
}
- 但这样会出现未定义行为，当元素被删除，对应的迭代器就失效了，erase返回时it已经失效，for循环里的++it就是错的。解决方法是erase前得到下一个元素的迭代器
for (AssocContainer<int>::iterator it = c.begin(); it != c.end();) {
if (f(*it)) c.erase(it++);
else ++it;
}
- 再增加问题，每次删除后要把一条消息写到日志文件中，对关联容器很简单，只要加个打印
ofstream logFile;
AssocContainer<int> c;
for (AssocContainer<int>::iterator it = c.begin(); it !=c.end();) {
if (f(*it)) {
logFile << "Erasing " << *it <<'\n';
c.erase(it++); // 删除元素
}
else ++it;
}
- 但vector、string和deque不能再使用erase-remove惯用法，因为没有办法让erase或remove写日志文件，也不能仿照关联容器用erase，因为erase会使序列容器的被删元素和之后所有的元素迭代器失效，再用自增显然会出错。解决方法是使用erase的返回值保持迭代器有效
for (SeqContainer<int>::iterator it = c.begin(); it != c.end();) {
if (f(*it)){
logFile << "Erasing " << *it << '\n';
it = c.erase(i);
}
else ++it;
}
10 注意分配器的协定和约束
- 分配器最初被设想为抽象内存模型，在定义的内存模型中提供指针和引用的typedef才有意义。C++标准中类型T的对象的默认分配器（allocator<T>）提供typedef allocator<T>::pointer和allocator<T>::reference，而且也希望用户定义的分配器也提供这些typedef，问题是在C++里没有办法捏造引用
- 标准允许库实现假设每个分配器的pointer typedef是T*的同义词，每个分配器的reference typedef与T&相同。库实现可以忽视typedef并直接使用原始指针和引用，所以写出提供新指针和引用类型的分配器的方法也没用，因为STL实现将忽视typedef
- 标准允许STL实现认为相同类型的分配器等价，原因是，假设有两个容器v1和v2，把v2赋值到v1，销毁v1时v1的分配器要能回收由v2的分配器分配的内存，如果两者不等价，接合操作就很难实现
- 相同类型的分配器等价是十分严厉的约束，这代表如果要可移植，分配器就不能有状态，即不能有任何非静态数据成员，这表明不能有从两个不同的堆分配的SpecialAllocator<int>，它们是不等价的
- 分配器在分配原始内存方面类似operator new，但它们的接口不同，两者都带有一个指定要分配多少内存的参数，但对于operator new，这个参数指定的是字节数，而对于allocator<T>::allocate指定的是内存里能容纳多少个T对象。在sizeof(int) == 4的平台上，容纳一个int的内存得把4传给operator new，把1传给allocator<int>::allocate
void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);
// 本质上pointer就是T*的typedef
- 大多数标准容器从未调用它们例示的分配器，对list和所有标准关联容器都是如此（set、multiset、map和multimap）。原因是这些是基于节点的容器，这些容器所基于的数据结构是每当值被储存就动态分配一个新节点
// list的可能实现
template<typename T, typename Allocator = allocator<T>>
class list {
private:
Allocator alloc; // 用于T类型对象的分配器
struct ListNode { // 链表里的节点
T data:
ListNode *prev;
ListNode *next;
};
...
};
- 添加一个新节点到list时需要从分配器获取内存，需要的不是T的内存而是包含了一个T的ListNode的内存，那使Allocator对象没用了，因为它为T分配内存而不为ListNode分配内存。list需要的是从它的分配器类型那里获得用于ListNode的对应分配器的方法，而分配器不能提供list需要的，这就是list不让Allocator做任何分配的原因
- 分配器模板A（例如，std::allocator，SpecialAllocator，等）都被认为有一个叫做rebind的内嵌结构体模板。rebind带有一个类型参数U，并且只定义一个typedef，other。 other是A<U>的一个简单名字。list<T>可以通过Allocator::rebind<ListNode>::other从它用于T对象的分配器（Allocator）获取对应的ListNode对象分配器
template<typename T>
class allocator {
public:
template<typename U>
struct rebind {
typedef allocator<U> other;
}
...
};
- 如果你想要写自定义分配器，必须
- 把分配器做成一个模板，模板参数T代表要分配内存的对象类型。
- 提供pointer和reference的typedef，让pointer是T*，reference是T&。
- 不要给你的分配器对象状态，分配器不能有非静态的数据成员
- 传给分配器的allocate成员函数需要分配的对象个数而不是字节数，函数返回T*指针（通过pointer typedef），即使还没有T对象被构造
- 提供标准容器依赖的内嵌rebind模板
11 理解自定义分配器的正确用法
- 假如有一个仿效malloc和free的程序，用于管理共享内存的堆
void* mallocShared(size_t bytesNeeded);
void freeShared(void *ptr);
template<typename T>
class SharedMemoryAllocator {
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 vector<double, SharedMemoryAllocator<double>> SharedDoubleVec;
...
{ // 开始一个块
SharedDoubleVec v; // 建立一个元素在共享内存中的vector
...
}
- v分配来容纳它元素的内存将来自共享内存，但v本身只是一个普通的基于堆的对象，所以它将被放在运行时系统为基于堆的对象使用的任何内存，而非共享内存。为了把v的内容放进共享内存，必须这样
// 分配足够的共享内存
void *pVectorMemory = mallocShared(sizeof(SharedDoubleVec));
// 用placement new建立一个SharedDoubleVec对象
SharedDoubleVec *pv = new (pVectorMemory) SharedDoubleVec;
...
pv->~SharedDoubleVec(); // 销毁共享内存中的对象
freeShared(pVectorMemory); // 销毁原来的共享内存块
- 除非真的要让一个容器（与它的元素相反）在共享内存里，否则避免手工的分配/建造/销毁/回收的过程。另外上述代码忽略了mallocShared可能返回一个null指针，产品代码必须考虑这种可能性。共享内存中的vector的建立由placement new完成而不是基本的new
- 再举一个例子，有两个堆，命名为Heap1和Heap2类。每个堆类有用于进行分配和回收的静态成员函数
class Heap1 {
public:
...
static void* alloc(size_t numBytes, const void *memoryBlockToBeNear);
static void dealloc(void *ptr);
...
};
class Heap2 { ... }; // 有相同的alloc/dealloc接口
- 要在不同的堆里联合定位一些STL容器的内容，首先，设计一个分配器，使用像Heap1和Heap2那样用于真实内存管理的类
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);
}
...
};
- 然后使用SpecificHeapAllocator来把容器的元素集合在一起
// 把v和s的元素放进Heap1
// 把L和m的元素放进Heap2
vector<int, SpecificHeapAllocator<int, Heap1>> v;
set<int, SpecificHeapAllocator<int Heap1>> s;
list<Widget,
SpecificHeapAllocator<Widget, Heap2>> L;
map<int, string, less<int>,
SpecificHeapAllocator<pair<const int, string>, Heap2>> m;
12 对STL容器线程安全性的期待现实一些
- SGI定义的STL对多线程支持的黄金规则
- 多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能
有任何写入者操作这个容器
- 对不同容器的多个写入者是安全的。多线程可以同时写不同的容器
- 下列代码查找vector<int>中第一次出现5的位置，如果找到了，就把这个值改为0
vector<int> v;
vector<int>::iterator first5(find(v.begin(), v.end(), 5)); // 行1
if (first5 != v.end()){ // 行2
*first5 = 0; // 行3
}
- 多线程环境中，另一个线程可能在行1完成后修改v中的数据，这样行2对first5和v.end的检测就没有意义，同理行3中对*first5的赋值是不安全的，因为另一个线程可能在行2和行3之间执行并以某种方式使first5失效。要让上述代码线程安全，v必须从行1到行3保持锁定，STL实现很难，同步原语（如信号灯，互斥量）通常开销很大。不能期望任何STL实现解决问题，必须手工对付这些情况中的同步控制
vector<int> v;
...
getMutexFor(v);
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if (first5 != v.end()) { // 这里现在安全了
*first5 = 0; // 这里也是
}
releaseMutexFor(v);
- 更面向对象的解决方案是创建一个Lock模板类，在构造函数里获得互斥量并在析构函数里释放，使getMutexFor和releaseMutexFor的调用不匹配的机会减到最小。使用一个类（像Lock）来管理资源的生存期（例如互斥量）的办法通常称为资源获得即初始化，即RAII
// 获取和释放容器的互斥量的类的模板核心
// 忽略了很多细节
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;
}
}
网友评论