vector<bool>与vector<T>

vector<bool> 不像其他容器一样按Byte存储的，它是按bit存储的，也就是说一个正常的bool类型的空间可以存放vector<bool>中的8个，空间上确实优化了很多，然而，c++是不能直接取对bit操作的（因为C++的最小可寻址值通常以byte为单位），对其使用operator[]其实返回的不是bool的引用而是一个”proxy reference”是”std::vector< bool>:reference”类型的对象。

正因为如此，vector<bool>通过代理对象进行存取访问时需要执行逐位处理，访问通常比int之类的普通类型操作要慢很多。

因此，对vecotr<bool>的使用需慎重考虑以下几点：
(1)是否需要牺牲速度来获取空间上的优化
(2)算法中会否有对vecotr地址进行解引用操作的可能。

如果不满足以上条件，建议使用deque<bool>来取代vector<bool>，功能基本相同，但deque<bool>未对其进行特殊处理。

下面是vector<bool>与vector<T>简单的对比例子：

int main(){
	vector<char> ch;
	vector<int> in;
	vector<bool> bo;
 
	int m = 1e6;
	clock_t t1, t2, t3;
 
	t1 = clock();
	for (int i = 0; i < m; i++){
		ch.push_back('0');
	}
	t1 = clock() - t1;
 
	t2 = clock();
	for (int i = 0; i < m; i++){
		in.push_back(0);
	}
	t2 = clock() - t2;
 
	t3 = clock();
	for (int i = 0; i < m; i++){
		bo.push_back(true);
	}
	t3 = clock() - t3;
 
	cout <<"vector<char> "<< t1 << "\n vector<int> " << t2 << "\nvector<bool> " << t3 << endl;
	cout << endl;
 
	system("pause");
	return 0;
}

运行结果：

vector<char> 216
vextor<int> 229
vector<bool> 16535

这里发现vector<bool>相较于其他vector<T>速度要慢的多！

参考资料

(65条消息) 【C++】vector＜bool＞的特别之处_小陶同学_的博客-CSDN博客

(65条消息) 不使用vector的原因和替代方法_jackycmu的博客-CSDN博客