lalala
首页
时间轴
标签
分类
友链
关于
娱乐
清单
avatar
文章
80
标签
61
分类
16
首页
时间轴
标签
分类
友链
关于
娱乐
清单
目录
Effective STL 笔记
|读书笔记
阅读量:

  1. 慎重选择容器类型

  2. 确保容器中的对象拷贝正确而高效
    当(通过如insert或push_back之类的操作)向容器中加入对象时，存入容器的是你所指定的对象的拷贝。当(通过如front或back之类的操作)从容器中取出一个对象时，你所得到的是容器中所保存的对象的拷贝。进去的是拷贝，出来的也是拷贝(copy in, copy out)。这就是STL的工作方式。

  3. 调用empty而不是检查size()是否为0
    empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗费线性时间。

  4. 慎重选择删除元素的方法
    删除vector中值为x的元素

c++
1
2
3
std::vector<int> c1;
	c1.erase(std::remove(c1.begin(), c1.end(), 1963), c1.end()); // 当c1是vector, string或deque时，erase-remove习惯用法是删除特定值的元素的最好办法
	//这句的意思是，取得"1963"的位置（位于结尾），然后删除"be"到原vector结尾的所有元素

对于list

c++
1
2
std::list<int> c2;
	c2.remove(1963); // 当c2是list时，remove成员函数是删除特定值的元素的最好办法

当c是标准关联容器，使用任何名为remove的操作都是完全错误的。这样的容器没有名为remove的函数
对于关联容器

c++
1
2
std::set<int> c3;
	c3.erase(1963); // 当c3是标准关联容器时，erase成员函数是删除特定值元素的最好办法

如果要在循环中操作，总结如下：

  1. 如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次调用erase时，要用它的返回值更新迭代器；
c++
1
2
3
4
5
6
7
std::ofstream logFile;
for (std::vector<int>::iterator i = c1.begin(); i != c1.end();) {
		if (badValue(*i)) {
			logFile << "Erasing " << *i << '\n';
			i = c1.erase(i); // 把erase的返回值赋给i，使i的值保持有效
		}
		else ++i;

因为对于这类容器，调用erase会使被删除元素和他之后的所有迭代器失效，而erase的返回值正是我们所需要的，一旦erase完成，它的返回值是指向被删除元素的下一个元素的有效迭代器。

  1. 如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对迭代器做后缀递增。
c++
1
2
3
4
5
6
7
8
std::ofstream logFile;
	for (std::set<int>::iterator i = c3.begin(); i != c3.end();) {
		if (badValue(*i)) {
			logFile << "Erasing " << *i << '\n'; // 写日志文件
			c3.erase(i++); // 对坏值，把当前的i传给erase，递增i是副作用
		}
		else ++i;              // 对好值，则简单第递增i
	}

因为对于这类容器，调用erase会使被删除元素的所有迭代器失效，而对于关联容器，erase的返回值是void(c11也返回下一个位置的迭代器啦)。我们采用后缀递增的技术。我们要确保在调用erase之前，有一个迭代器指向容器中的下一个元素。我们采用了c3.erase(i)，这个过程可以分为三个部分(https://blog.csdn.net/yousss/article/details/80077758)
1、先把i的值赋值给一个临时变量做为传递给erase的参数变量

2、因为参数处理优先于函数调用，所以接下来执行了i++操作，也就是i现在已经指向了下一个地址。

3、再调用erase函数，释放掉第一步中保存的要删除的it的值的临时变量所指的位置。

  1. 使用reserve来避免不必要的重新分配
c++
1
2
3
4
std::vector<int> v;
	v.reserve(1000); // 如果不使用reserve,下面的循环在进行过程中将导致2到10次重新分配;加上reserve，则在循环过程中,将不会再发生重新分配
	for (int i = 1; i <= 1000; ++i) 
		v.push_back(i);

  • 对于vector和string，增长过程是这样来实现的：每当需要更多空间时，就调用与realloc类似的操作。这一类似于realloc的操作分为四部分：(1).分配一块大小为当前容量的某个倍数的新内存。在大多数实现中，vector和string的容量每次以2的倍数增长，即，每当容器需要扩张时，它们的容量即加倍。
    (2).把容器的所有元素从旧的内存拷贝到新的内存中。
    (3).析构掉就内存中的对象。
    (4).释放旧内存。

  • resize()函数（强迫容器改变到n个元素的状态）：
    -如果 n < size 容器末尾的元素被析构
    -如果 n > size 通过默认构造函数创建的新元素将被添加到容器的末尾
    -如果 n > capacity 则在添加元素前，将重新分配

  • reserve函数（强迫容器把它的容量至少变为n）：
    如果 n < capacity 忽略操作

  • reserve成员函数能使你把重新分配的次数减少到最低限度，从而避免了重新分配和指针/迭代器/引用失效带来的开销。避免重新分配的关键在于，尽早地使用reserve，把容器的容量设为足够大的值，最好是在容器刚被构造出来之后就使用reserve。

  • 大小(size)和容量(capacity)的关系使我们能够预知什么时候插入操作会导致vector或string执行重新分配动作，进而使我们有可能预知一个插入操作什么时候会使容器中的迭代器、指针和引用失效。

c++
1
2
3
4
string s
if(s.size() < s.capacity()){
	s.push_back(x);
}
  • 通常有两种方式来使用reserve以避免不必要的重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少元素，则此时可以使用reserve。第二种方式是，先预留足够大的空间(根据你的需要而定)，然后，当把所有数据都加入以后，再去除多余的容量。

  1. 注意string实现的多样性
    (1).string的值可能会被引用计数，也可能不会。很多实现在默认情况下会使用引用计数，但它们通常提供了关闭默认选择的方法，往往是通过预处理宏来做到这一点。
    (2).string对象大小的范围可以是一个char* 指针大小的1倍到7倍。
    (3).创建一个新的字符串值可能需要零次、一次或两次动态分配内存。
    (4).string对象可能共享，也可能不共享其大小和容量信息。
    (5).string可能支持，也可能不支持针对单个对象的分配子。
    (6).不同的实现对字符内存的最小分配单位有不同的策略。

  2. 了解如何把vector和string数据传给旧的API

c++
1
2
3
4
5
6
std::vector<int> v;
	if (!v.empty()) {
		doSomething(&v[0], v.size());
		// doSomething(v.begin(), v.size()); // 错误的用法
		doSomething(&*v.begin(), v.size()); // 可以，但不易于理解
	}

C++标准要求vector中的元素存储在连续的内存中，就像数组一样。string中的数据不一定存储在连续的内存中，而且string的内部表示不一定是以空字符结尾的。

  1. 使用”swap技巧”除去多余的容量
c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<Contestant> contestants;
	// ... // 让contestants变大，然后删除它的大部分元素
	// vector<Contestant>(contestants)创建一个临时矢量，vector的拷贝构造函数只为所拷贝的元素分配所需要的内存
	std::vector<Contestant>(contestants).swap(contestants);
 
	contestants.shrink_to_fit(); // C++11
 
	std::string s;
	// ... // 让s变大，然后删除它的大部分字符
	std::string(s).swap(s);
 
	s.shrink_to_fit(); // C++11
 
	std::vector<Contestant>().swap(contestants); // 清除contestants并把它的容量变为最小
 
	std::string().swap(s); // 清除s并把它的容量变为最小

  1. 避免使用vector
    作为一个STL容器，vector只有两点不对。首先，它不是一个STL容器；其次，它并不存储bool。除此以外，一切正常。

  2. 理解相等(equality)和等价(equivalence)的区别
    相等的概念是基于operator==的。等价关系是以”在已排序的区间中对象值的相对顺序”为基础的。标准关联容器是基于等价而不是相等。

标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数(默认为less)来决定保持怎样的顺序。等价的定义正是通过该比较函数而确定的，因此，标准关联容器的使用者要为所使用的每个容器指定一个比较函数(用来决定如何排序)。如果该关联容器使用相等来决定两个对象是否有相同的值，那么每个关联容器除了用于排序的比较函数外，还需要另一个比较函数来决定两个值是否相等。(默认情况下，该比较函数应该是equal_to，但equal_to从来没有被用作STL的默认比较函数。当STL中需要相等判断时，一般的惯例是直接调用operator==)。

C++标准对于等价的值(对multiset)或键(对multimap)的相对顺序没有什么限制。

  1. 为包含指针的关联容器指定比较类型
    每当你要创建包含指针的关联容器时，一定要记住，容器将会按照指针的值进行排序。绝大多数情况下，这不会是你所希望的，所以你几乎肯定要创建自己的函数子类作为该容器的比较类型(comparison type)。
    比如：
c++
1
2
3
4
5
6
7
8
9
vector<string*>ssp;
ssp.insert(new std::string("Anteater"));
	ssp.insert(new std::string("Wombat"));
	ssp.insert(new std::string("Lemur"));
	ssp.insert(new std::string("Penguin"));
for (set<string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
{
	count << *i << endl;
}

然而这个打印出来的不会是字符串，而是4个十六进制数—他们是指针的值。
即使我们改成

c++
1
count << **i << endl;

这个打印出来不是我们期待的首字母排序的那样,因为ssp会按指针的值排序。
为了解决这个问题，请记住

c++
1
set<string*> ssp;

是如下代码的缩写

c++
1
set<string*, less<string*>, allpcator<string*> ssp;

分配子与当前问题无关，所以不考虑。

那么如何创建函数子类？
最直观的是写一个比较函数，比如：

c++
1
2
3
4
5
bool stringPtrLess()(const std::string* ps1, const std::string* ps2) const
	{
		return *ps1 < *ps2;
	}
set<string, stringPtrLess>

但是这样无法通过编译，stringPtrLess不是一个类型，所以我们需要创建一个类，并在内部为它创建一个函数，如下就可以啦

c++
1
2
3
4
5
6
7
8
struct DereferenceLess {
	template<typename PtrType>
	bool operator()(PtrType pT1, PtrType pT2) const
	{
		return *pT1 < *pT2;
	}
};
std::set<std::string*, DereferenceLess> ssp; // 与std::set<std::string*, StringPtrLess> ssp;的行为相同

如果你有一个包含智能指针或迭代器的容器，那么你也要考虑为它指定一个比较类型。对指针的解决方案同样也适用于那些类似指针的对象。就像DereferenceLess适合作为包含T*的关联容器的比较类型一样，对于容器中包含了指向T对象的迭代器或智能指针的情形，DereferenceLess也同样可用作比较类型。

  1. 总是让比较函数在等值情况下返回false

  2. 切勿直接修改set或multiset中的键
    对于map和multimap尤其简单，因为如果有程序试图改变这些容器中的键，它将不能通过编译。这是因为，对于一个map<K, V>或multimap<K, V>类型的对象，其中的元素类型是pair<const K, V>。因为键的类型是const K，所以它不能被修改。(如果利用const_cast，你或许可以修改它。)

  3. 考虑用排序的vector替代关联容器
    对于许多应用，哈希容器可能提供常数时间的查找能力优于set、multiset、map和multimap的确定的对数时间查找能力。

比如我们需要一个容器来存储Widget对象，如果我们用关联容器，则每个节点不仅包含了一个Widget，而且还包含了几个指针：一个指向左儿子，另一个指向右儿子，通常还有一个指向它的父节点，至少3个指针。

在排序的vector中可能在标准关联容器中存储同样的数据耗费更少的内存，考虑到页面错误的因素，通过二分搜索法查找一个排序的vector可能比查找一个标准关联容器更快一些。

查找操作几乎从不跟插入和删除操作混在一起时，再考虑使用排序的vector而不是关联容器才是合理的。否则，使用排序的vector而不是标准关联容器几乎肯定是在浪费时间。

  1. 当效率至关重要时，请在map::operator[]与map::insert之间谨慎做出选择
    map的operator[]函数与众不同。它与vector、deque和string的operator[]函数无关，与用于数组的内置operator[]也没有关系。相反，map::operator[]的设计目的是为了提供”添加和更新”(add or update)的功能。map::operator[]返回一个引用。

对效率的考虑使我们得出结论：当向映射表中添加元素时，要优先选用insert，而不是operator[]；而从效率和美学的观点考虑，结论是：当更新已经在映射表中的元素的值时，要优先选择operator[]。

文章作者: Sunxin
文章链接: https://sunxin18.github.io/2020/10/03/effective-stl/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lalala！
STL
打赏
  • 微信
    微信
  • 支付宝
    支付宝
评论
繁