Effective STL：杂记（一）

1. 避免使用vector<bool>

    vector<bool>实际上并不能算是一个STL容器，实际上也并不存储bool。因为一个对象要成为STL容器，就必须满足C++标准的第23.1节列出的所有条件，其中一个条件是，如果 c 是包含对象T的容器，而且 c 支持operator[]，则必须能够编译下面代码：

T *p = &c[0];

    也就是说容器中应该是存储对象 T，这样子 operator[] 才能返回容器中实际存储的对象，你也可以通过取它的地址得到一个指向该对象的指针。（这里需要假定 T 没有用非常规的方式对 operator & 做重载。）但是对于vector<bool>，底层是用类似于位图的方式存储的。

    对于vector<bool>的operator[]，返回的是一个代理对象（proxy project），这个对象表现得像是一个指向单位的引用。为这个代理对象添加一个隐式转向bool的函数就可以让 operator[] 返回一个bool值。所以对于 operator[] 返回值做 operator&，得到的并不是一个bool指针，所以将其赋给bool指针显然是编译不过的。

#include <iostream>
#include <map
#include <vector>

using namespace std;

int main() {
	vector<bool> vb;
	vb.push_back(false);
	vb.push_back(true);
	vb.push_back(false);
	// bool *pb = &vb[0];
	bool pb1 = vb[1];
	cout << pb1 << endl;
	cout << *vb.begin() << endl;
	return 0;
}

    上面的代码输出分别为1和0。但是如果去掉被注释语句的注释符号，则编译是无法通过的。这里vb[1]和*vb.begin()能正常工作应该是对返回值进行了特殊处理。详细的情况需要分析源代码了。

    可以替代vector<bool>的有deque<bool>和bitset，deque<bool>就的确是存储bool的，bitset不是STL容器，是标准C++库的一部分，但是它的大小在编译时就确定了。

2. swap技巧除去多余的容量

    我们知道，随着vector元素的增加，存在一个翻倍扩容的操作，此时会导致vector的长度越来越大，即使我们调用pop_back将元素弹出，其容量也不会变小。最终我们可能需要用resize操作来减少容量。比起resize操作，我们可以用更简单的方式来除去多余的容量，那就是用swap函数来交换两个vector的内容。

#include <iostream>
#include <vector>

using namespace std;

int main() {
	vector<int> vi;
	for (int i = 0; i < 10; ++i) 
		vi.push_back(i);
	vi.pop_back();
	cout << vi.capacity() << endl;        // 输出 16
	vector<int>(vi).swap(vi);
	cout << vi.capacity() << endl;        // 输出 9
	return 0;
}

     上面的代码分别输出 16 和 9。最主要的语句是“vector<int>(vi).swap(vi)”，这里用 vi 的内容来初始化一个临时vector<int>临时变量，则该临时变量将只含有 vi 中实际存在的元素，没有被设置的容量内容并不会被赋值过去，即该临时变量只含有 9 个元素。然后再将其与 vi 交换内容，这个时候 vi 中便仅有9个元素了，不存在多出来的容量。

3. map中operater[]与insert

     map::operator[] 的设计目的是为了提供“添加和更新”（add or update）的功能。operator[] 会返回一个引用，它指向与 k 相关联的值对象。然后 v 被赋给该引用（operator[] 返回那个引用）所指向的对象。如果键 k 已经有了先关联的值，则该值被更新，但问题在于如果 k 还没有在映射表中，它会使用值类型的默认构造函数创建一个新的对象，然后 operator[] 就能返回一个指向该新对象的引用了。

     也就是说，如果键 k 对应的 v 不存在，operator[] 会导致新的对象被创建，不管有没有新的 v 被赋给。

#include <iostream>
#include <map>

using namespace std;

int main() {
	map<int, int> m;
	cout << m.size() << endl;   // 输出：0
	m[10];
	cout << m.size() << endl;   // 输出：1
	if (m.find(10) != m.end()) {
		cout << "has 10" << endl;   // 输出：has 10
	}
	return 0;
}

      通过上面的输出，可以看到虽然在执行了 m[10] 后，m 中新增了一个对象。

      而对于 operator[] 与 insert ，《Effective STL》中讲到对于新增对象，insert函数的效率要高，而更新操作，则是 operator[] 效率要高。书中有讲到一些例子，还没完全消化好，所以直接不分析了。

     通过上面的例子，我们也可以知道不能通过 operator[] 去判断某个键是否存在对应的值，而是应该用 find 函数来判断。