高效STL—关联容器

         标准关联容器中最重要的就是基于等价而不是相等。比如对于基本的函数库有find函数，但是对于set关联容器也是有find成员函数的。因为标准关联容器保持有序，所以每一个容器必须有一个定义了怎么保持东西有序的比较函数（默认是less）。等价是根据这个比较函数定义的，所以标准关联容器的用户只需要为他们要使用的任意容器指定一个比较函数

         必须为指针的关联容器指定比较类型

一定要明确对于一个容器来说，容器内的迭代器是存入该容器对象的指针，比如一个关联容器存入指针类型，那么使用这个容器的迭代器的取值仍然是该对象的指针。比如：

Set<string*> ssp;

Ssp.insert(newstring(“adfa”));

Ssp.insert(newstring(“bdfa”));

Ssp.insert(newstring(“cdfa”));

Ssp.insert(newstring(“ddfa”));

然后写一段程序希望打印字符串；

For(set<string*>::const_iteratorI = ssp.begin();i!=ssp.end();i++)

         Cout<<*i<<endl;

看到的是四个十六进制的数，*i不是一个string ,它是一个string的指针。如果将*i修改为**i，可能得到正确的答案。但是有可能不是，因为set中排序的标志是按照set中元素的性质来的，也就是按照string指针来排序的。

Set<string*,less<string*>,allocator<string*>>ssp;

如果想要string*指针以字符串值确定排序被存储在set中，不能使用默认的比较仿函数。需要自定义，它的对象带有string*指针并按照指向的字符串值来进行排序。也就是为关联容器定义自己的比较函数。

         避免原地修改set和multiset的键

所有的关联容器，set和multiset保持他们的元素有序，这些容器的正确行为依赖于他们保持的有序。如果你修改了关联容器里的一个元素的值，新值可能不在正确的位置，而且那将破坏容器的有序性。不要修改set和map中的键值部分，不然会影响set的排序

如果你改变关联容器里的元素，必须确保不改变键值部分，这会影响有序性的元素部分。对于非键值部分，可以随意修改。如果想修改关联容器中的元素，最好的办法就是将这个待修改的元素赋值给临时变量，然后在容器中删除这个元素，将修改后的临时变量插入到容器中。

使用有序的vector来代替关联容器，可以这么认为，对于一个vector，使用的是连续内存，对于一个关联容器，里面还有几个指针，一个页面可以存储比关联容器更多的对象，而且不会造成却也中断。当在vector中存储对象没有开销，但是对于关联容器有三个指针或两个指针和一个int。如果我们的数据结构足够大，他们可以分成多个内存页面，但是vector比关联容器需要的页面要少，因为关联容器给每个对象附加了三个之后做呢。

在有序vector中存储数据很有可能比在标准关联容器中保存相同的数据消耗更少的内存，当页面错误值得重视的时候，在有序vector中通过二分查找法查找可能比在一个标准关联容器中查找更快。但是一定要明白使用vector代替关联容器的前提。

字考虑效率的时候，在map::operator[]和map.insert()之间是有区别的，对于一个map容器，插入一个元素的操作：

Map<int,object>m;

M[1] = 1.50;    

表达式m[1]是m.operator[](1)的简化，所以这是一个map::operator[]的调用。那个函数必须返回一个object的引用，因为m的映射类型是object。在这里，m里面没有任何东西，所以键1在Map里没有入口。一次operator[]默认构造一个object来作为关联到1的值，然后返回到那个object的引用。最后，object成为赋值目标，被赋值的值是1.50。整个过程就是先默认构造一个object，然后我们立即赋给它新值。如果用想要的值构造object比默认构造object然后进行赋值显然更高效，我们就应该用直截了当的Insert调用来替换operator[]的使用。

Typedefmap<int,object> obj_map;

m.insert(obj_map::value_type(1,1.50));

上述代码利用了value_type,对于map和multimap这个很重要，容器元素的类型总是某种pair.

所以，当使用增加功能时，Insert比operator[]更高效。但是我们做更新时，情形正好相反。

M[k] = v; //使用operator[]来把k的值更新为v

m.insert(obj_map::value_type(k,v)).first->second= v; //使用insert来把v的值更新为v

insert的调用需要obj_map::value_type类型的实参（pair<int,object>）,所以当我们调用Insert时，我们必须析构和构造一个那种类型的对象。会造成一个析构函数和构造函数的调用，operator[]没有使用pair对象，所以没有构造和析构pair和object。

综述：当给map添加一个元素时，我们断定insert比operator[]好；当更新已经在map里的元素值时operator[]更好。

Effective STL --关联容器