烈性果汁 - STL
type: channel
link: https://www.nhyilin.cn/tag/STL/
items: 《Effective STL》 Chapter 1: Containers（7-12）
items: 《Effective STL》 Chapter 1: Containers（1-6）

《Effective STL》 Chapter 1: Containers（7-12）
type: item
date: 2025-01-22T22:40:00+08:00
description: 50 Specific Ways to Improve Your Use of the Standard Template Library.《Effective STL》 Chapter 1: Containers（1-6）Item 7: 在使用存储new出来的指针的容器时，记得在容器销毁之前delete这些指针When using containers of newed pointers, remember to delete the pointers before the container is destroyed.STL中的容器非常智能。它们可以提供用于正向和反向遍历的迭代器（通过begin、end、rbegin等函数）；它们可以告诉你容器中存储了什么类型的对象（通过它们的value_type typedef）；在插入和删除元素时，它们会自动处理必要的内存管理；它们可以报告容器中当前有多少元素以及最多可以容纳多少元素（分别通过size和max_size）；当然，当容器本身被销毁时，它们会自动销毁它们所包含的每个对象。考虑到这些智能容器，许多程序员就不再为清理资源而担忧了。他们会想：“嘿，我的容器会替我处理这些问题。” 在很多情况下，他们是对的，但当容器中存储的是通过new动态分配的指针时，他们的想法就不够正确了。是的，指针容器会在它们（容器）被销毁时销毁它们所包含的每个元素，但指针的“析构函数”什么都不会做！它当然不会调用delete。因此，以下代码会导致资源泄漏：void doSomething() { vector<Widget*> vwp; for (int i = 0; i < SOME_MAGIC_NUMBER; ++i) vwp.push_back(new Widget); ... // 使用vwp } // 在这里，Widget对象会泄漏！当vwp超出作用域时，它的每个元素都会被销毁，但这并不能改变这样一个事实：new出来的对象从未被delete。这种删除操作是你的责任，而不是容器的责任。这其实是特意设计的功能。只有你知道这些指针是否需要被删除。通常情况下，你希望它们被删除。当确实需要删除时，实现这一点看起来似乎很简单：void doSomething() { vector<Widget*> vwp; ... // 如前所述 for (vector<Widget*>::iterator i = vwp.begin(); i != vwp.end(); ++i) delete *i; }这段代码是可以工作的，但前提是你对“工作”并没有太高的要求。这里有两个问题。一个问题是，这个新的for循环实际上与for_each的功能几乎相同，但它并不像直接使用for_each那么清晰（参见第43条）。另一个问题是，这段代码并不是异常安全的。如果在填充vwp的指针到删除它们之间抛出了异常，资源仍然会泄漏。幸运的是，这两个问题都可以解决。要将你的类似for_each的循环变成真正的for_each调用，你需要将delete转化为一个函数对象。这是小菜一碟，假设你有一个喜欢玩STL的孩子：template<typename T> struct DeleteObject : public unary_function<const T*, void> { void operator()(const T* ptr) const { delete ptr; } };现在你可以这样写：void doSomething() { ... // 如前所述 for_each(vwp.begin(), vwp.end(), DeleteObject<Widget>()); }不幸的是，这样做需要你显式地指定DeleteObject将删除的对象的类型（在这里是Widget）。这很烦人。vwp已经是一个vector<Widget*>，所以显然DeleteObject会删除Widget*指针！这显得很多余。这种冗余不仅令人厌烦，还可能导致难以追踪的错误。例如，假设有人不明智地决定从string继承：class SpecialString : public string { ... };从一开始这就是危险的，因为string（和所有标准STL容器一样）没有虚析构函数，而从没有虚析构函数的类继承是C++中的一个重大禁忌。（详细信息可以参考任何一本好的C++书。在《Effective C++》中，可以参考第14条。）尽管如此，有些人仍然会这样做，所以让我们看看以下代码会如何表现：void doSomething() { deque<SpecialString*> dssp; ... for_each(dssp.begin(), dssp.end(), De…

《Effective STL》 Chapter 1: Containers（1-6）
type: item
date: 2025-01-08T22:12:00+08:00
description: 50 Specific Ways to Improve Your Use of the Standard Template Library.本文作为读书的记录，后续会陆续更新。Item 1: 谨慎选择你的容器Choose your containers with care您知道 C++ 提供了多种容器供您使用，但您是否意识到这些容器种类繁多？为了确保您没有忽略任何选项，下面简要回顾一下。标准 STL 序列容器、vector、string、deque 和 list。标准 STL 关联容器，set、multiset、map 和 multimap。非标准序列容器 slist 和 rope。slist 是单链表，而 rope 本质上是重载string。（“rope” 是重载“string”。明白了吗？）您可以在 Item 50 中找到这些非标准（但常用）容器的简要概述。非标准关联容器 hash_set、hash_multiset、hash_map 和 hash_multimap。我在 Item 25 中研究了这些广泛使用的基于哈希表的标准关联容器变体。vector<char> 替代了 string。第 13 条描述了这种替代在哪些条件下是合理的。vector 可以替代标准的关联容器。正如 Item 23 所明确指出的，有时 vector 在时间和空间上的表现都优于标准的关联容器。几个标准的非 STL 容器，包括arrays、bitset、valarray、stack、queue,和priority_queue。由于这些都是非 STL 容器，因此本书中我很少谈论它们，不过第 16 条提到了数组优于 STL 容器的情况，第 18 条解释了为什么位集可能比 vector<bool> 更好。还值得一提的是，arrays可以与 STL 算法一起使用，因为指针可以用作array迭代器。关于容器的选项非常丰富，选择时需要考虑的因素也非常多。遗憾的是，大多数关于 STL 的讨论都对容器世界持相当狭隘的看法，忽略了许多与选择最合适的容器相关的问题。甚至STL也参与其中，为在 vector、deque 和 list 之间进行选择提供了以下指导：vector、list 和 deque 为程序员提供了不同的复杂性权衡，应相应地使用它们。vector 是默认应使用的序列类型。当在序列中间频繁插入和删除时，应使用 list。当大多数插入和删除发生在序列的开头或结尾时，deque 是首选的数据结构。如果您主要关心的是算法复杂性，我想这是一个合理的建议，但还有很多值得关注的事情。首先我需要介绍一种对 STL 容器进行分类的方法，这种方法讨论得并不多。这就是连续内存容器和基于节点的容器之间的区别。连续内存容器（也称为基于数组的容器）将其元素存储在一个或多个（动态分配的）内存块中，每个内存块包含多个容器元素。如果插入新元素或删除现有元素，则同一内存块中的其他元素必须上移或下移，以便为新元素腾出空间或填充以前被删除元素占用的空间。这种移动会影响性能（参见第 5 和 14 条）和异常安全性（我们很快就会看到）。标准的连续内存容器是 vector、string 和 deque。非标准 rope也是连续内存容器。基于节点的容器每块（动态分配的）内存仅存储一个元素。插入或删除容器元素只会影响指向节点的指针，而不会影响节点本身的内容，因此插入或删除某些内容时无需移动元素值。表示链接列表的容器（如 list和slist）是基于节点的，所有标准关联容器也是如此。（它们通常实现为平衡树。）非标准哈希容器使用不同的基于节点的实现，如您将在条目 25 中看到的那样。您是否需要能够在容器中的任意位置插入新元素？如果是，则需要一个序列容器；关联容器不行。您是否关心元素在容器中的排序方式？如果不关心，散列容器将是一个可行的选择。否则，您将希望避免使用散列容器。容器必须是标准 C++ 的一部分吗？如果是，那就排除了散列容器、slist 和rope。你需要哪一类迭代器？如果它们必须是随机访问迭代器，那么从技术上讲，你只能使用 vector、deque 和 string，但你也许还想考虑 rope。有关rope的信息，请参阅。）如果需要双向迭代器，你必须避免使用 slist（参见 Item 50）以及散列容器的一种常见实现（参见 Item 25）。在进行插入或删除时，避免移动现有的容器元素是否重要？如果重要，你需要远离连续内存容器（参见条款 5）。在插入或删除时避免移动现有容器元素是否重要？如果重要，则需要远离连续内存容器（参见条目 5）。容器中的数据是否需要与 C 兼容布局？如果重要，则只能使用vector（参见条目 16）。查找速度是否是关键考虑因素？如果重要，则需要查看散列容器（参见条目 25）、…