|
一.现有哪些标准容器？按照什么标准分类？
● 标准STL序列容器：vector、string、deque和list。
序列式容器的共性：
构造函数可以指定个数及初始值
增加了resize(len)或resize(len, fillVal)
增加了insert(position, num, data)
增加了assign(num, data)
增加了取首尾函数：front(), back() （返回引用）
增加了后增删函数：push_back(data), pop_back() 关注的重点是位置。 ● 标准STL关联容器：set、multiset、map和multimap
关联式容器的共性：
实质为二叉查找树
可自动排序（要求容器元素的类型必须支持小于运算符）
每个元素都有一个key值
增加了insert(data)（不需指定位置）
增加了find(key)（返回第一个；若查不到，返回end()）
增加了erase(key)（删除所有关键字为key的元素）
增加了count(key)
增加了lower_bound(key), upper_bound(key)
增加了equal_range(key) 关注的重点是key，实际上，前面所讲的所谓序列化容器，也可以归为特殊的关联容器：key为position（位置）的关联容器！
回忆一下，许多脚本里都提供下标不为int的泛化数组，我们是不是可以反过来看：通常意义上的数组只是泛化世界的一个实例呢？ 前面我们从用户的角度，将容器分为序列性与关联性两种，现在，从设计者的角度，具体来说，也就是从内存分配的角度，将容器分为连续内存容器和基于节点的容器两种： ● 连续内存容器（也叫做基于数组的容器）：vector、string和deque
在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被插入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率和异常安全。 ● 基于节点的容器：list和slist，所有的标准关联容器
在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。所以当有东西插入或删除时，元素值不需要移动。 二.选择容器的原则是什么？有什么道理？
标准中提到的原则：
vector、list和deque提供给程序员不同的复杂度，因此应该这么用：vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构 实际采用的原则：
● 你需要“可以在容器的任意位置插入一个新元素”的能力吗？如果是，你需要序列容器，关联容器做不到。
● 你关心元素在容器中的顺序吗？如果不，散列容器就是可行的选择。否则，你要避免使用散列容器。
● 必须使用标准C++中的容器吗？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一类迭代器？如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string。
● 当插入或者删除数据时，是否非常在意容器内现有元素的移动？如果是，你就必须放弃连续内存容器。
● 容器中的数据的内存布局需要兼容C吗？如果是，你就只能用vector。
● 查找速度很重要吗？如果是，你就应该看看散列容器，排序的vector和标准的关联容器——大概是这个顺序。
● 你介意如果容器的底层使用了引用计数吗？如果是，你就得避开string，因为很多string的实现是用引用计数。于是你得重新审核你的string，你可以考虑使用vector<char>。
●
你需要插入和删除的事务性语义吗？也就是说，你需要有可靠地回退插入和删除的能力吗？如果是，你就需要使用基于节点的容器。如果你需要多元素插入（比如，
以范围的方式）的事务性语义，你就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对于有兴趣写异常安全代码的程序
员来说非常重要。
● 你要把迭代器、指针和引用的失效次数减到最少吗？如果是，你就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
●
你需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？这个一个非常
特殊的情况，但如果你遇到这种情况，deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是唯一
一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。） 三.使用new得指针的容器时，需要做些什么？
在销毁容器前delete那些指针。例如：
struct DeleteObject {
template<typename T> // 模板化加在这里
void operator()(const T* ptr) const
{
delete ptr;
}
} void doSomething()
{
deque<SpecialString*> dssp;
...
for_each(dssp.begin(), dssp.end(),
DeleteObject()); // 啊！良好定义的行为！
} 四.容量与重新分配
STL通常会比要求的多分配一些内存，元素erase后也不立即释放内存，这样的好处是不必频繁得“申请->释放->申请”，不仅影响效率，而且增加内存碎片。
当预先分配得内存不够时，会有一个重新分配得过程，例如：
对于vector和string，是以realloc等价的思想来增长。这个类似于realloc的操作有四个部分：
1. 分配新的内存块，它有容器目前容量的几倍。在大部分实现中，vector和string的容量每次以2为因数增
长。也就是说，当容器必须扩展时，它们的容量每次翻倍。
2. 把所有元素从容器的旧内存拷贝到它的新内存。
3. 销毁旧内存中的对象。
4. 回收旧内存。
重新分配导致两个后果：
1.分配，回收，拷贝和析构，那些步骤都很昂贵
2.所有指向vector或string中的迭代器、指针和引用都会失效，因为新内存并不是旧内存在物理上得延续，它可能是在内存中任何一个位置。
所以，如何尽量减少重新分配的机会，非常重要，STL提供reserve，可以做到这一点。例如：
vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
期间，可以保证不会有重新分配。 相关函数：
● size()告诉你容器中有多少元素。它没有告诉你容器为它容纳的元素分配了多少内存。
● capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。
● resize(Container::size_type n)强制把容器改为容纳n个元素。
● reserve(Container::size_type n)强制容器把它的容量改为至少n，提供的n不小于当前大小。 五.如何修改容器占用内存？
只能用swap，例如：
vector<Contestant>(contestants).swap(contestants);
表
达式vector<Contestant>(contestants)建立一个临时vector，它是contestants的一份拷
贝：vector的拷贝构造函数做了这个工作。但是，vector的拷贝构造函数只分配拷贝的元素需要的内存，所以这个临时vector没有多余的
容量。然后我们让临时vector和contestants交换数据，这时我们完成了，contestants只有临时变量的修整过的容
量，而这个临时变量则持有了曾经在contestants中的发胀的容量。在这里（这个语句结尾），临时vector被销
毁，因此释放了以前contestants使用的内存。 如果你想几乎完全删除已分配的内存：
vector<Contestant> tmp;
tmp.swap(contestants);
等到临时变量tmp被销毁，contestants就只占用个数级的内存了(sizeof(vector>)。
|
