c++ premier -- 容器

 呵呵，两个星期没有更新博客了。这两个星期基本一心一意都在做实验室的事，现在终于把算法写完了，测试效果也不错，总算有了自己原创的算法出来。不负我两个星期望着c++ premier却不敢翻开来看。今天早上把容器这两章给看了，我想整理一下，然后自己把它后面的综合应用给实现了。看完这一part就开始进入类方面的设计了，其实看这本书的目的就是要看类，然后实现一些数据结构。只剩两个星期了，希望能把这个目标完成，回家希望可以继续学法语吧。

 

有关顺序容器，指的是窗口内的元素按其位置存储和访问。顺序容器的元素排列次序与元素值无关，而是由元素添加到窗口里的次序决定。标准库定义了三种顺序容器类型：vector, list和deque。

适配器是根据原始容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。顺序容器适配器包括stack、queue和priority_queue类型。

容器所能盛放的元素的类型必须满足以下两个约束：

1. 元素类型必须支持赋值运算

2. 元素类型的对象必须可以复制。

顺序容器这一章的主要内容包括容器的初始化、跟容器关联的迭代器、容器相关的操作以及顺序容器的适配器。

 

1. 容器的初始化

 

 

2. 容器的迭代器及迭代器的范围

 迭代器所提供的操作包括引用(*iter)、解引用(iter->mem)、自增自减、比较相等或不等。

对于vector、deque中的迭代器，还能像指针那样，进行如下操作：iter+n、iter-n、iter1 += iter2、iter2 -= iter2，以及比较大小。

迭代器的范围：[begin, end)，是一个左闭合区间。

 

3. 顺序容器的操作

 这里不大理解的是value_type、reference、const_reference这三个类型别名有什么意义呢？

 

每种顺序容器都提供了类似于如下的操作：

1. 添加元素 insert、push_back(t)、list和deque的push_front(t)，insert可在指定位置添加一个、一段、n个元素。

2. 删除元素 erase、clear、pop_back以及list和deque的pop_front。

3. 设置容器大小 size、max_size、empty、resize

4. （如果有的话）获取容器内的第一个和最后一个元素。c.begin()、c.end()返回指向首尾的迭代器，而c.front()、c.back()返回首尾的元素。

5. 元素访问，除了c.front()、c.back()之外，还有下标操作、c.at()操作可以随机访问元素，不过只限于vector和deque。

6. 赋值与swap。swap让我意识到，容器的迭代器是跟容器的元素绑定在一起的，例如：

vector<int> vec1, vec2;
vector<int>::iterator iter1, iter2;
for( int i=0; i<10; i++ )
     vec1.push_back(i);
for( int i=0; i<15; i++ )
      vec2.push_back(i+15);
//iter1指向vec1的第一个元素，iter2指向vec2的第二个指针
iter1 = vec1.begin();
iter2 = vec2.begin();
//vec1与vec2的内容交换，iter1指向vec2的第一个元素，iter2指向vec1的第一个元素
vec1.swap(vec2);

7. 所有的容器还都支持关系操作符

 

4. 容器适配器

适配器以顺序容器为基础设备，提供了另外一套特别的操作来使用数据结构，因此适配器的初始化除了元素类型外，还需要一个顺序容器。

默认的stack和queue都基于deque容器实现，而priority_queue则在vector容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型实参，可以覆盖其关联的基础容器类型：

//deq中的元素复制到stk中来。deq 是一个deque
stack<int> stk(deq); 
//基础容器为vector的空stack
stack< string, vector<string> > str_stk;
//将svec中的元素复制到stack中来
stack< string, vector<string> >str_stk2(svec);

对于给定的适配器，其关联的容器必须满足一定约束条件。stack适配器所关系的基础容器可以是任意一种顺序容器类型，因此stack可以建立在vector、list或deque容器之上。而queue适配器要求其关联的基础容器必须提供pos_front(书里写的是push_front，但其实应该是指的pop_front)运算，因此只能建立在list、queue容器上，而不能建立在vector容器上。priority_queue适配器要求提供随机访问功能，因此可以建立在vector或deque上，而不能建立在list上。

 

关联容器和顺序容器的本质差别在于：关联容器通过键(key)存储和读取元素，而顺序容器通过元素在容器中的位置顺序存储和访问元素。

 

5. pair类型

pair类型有两个数据成员，分别为first、second，map中的元素便是pair。可以通过makpair( first, second)来成生一个pair。如：

pair<string, string> author;
string first, last;
while( cin>>first>>last ){
     author = makepair( first, last );
     //process author
}

 

6. map类型

首先看一下map中定义的一些类型。

 

map比较神奇的地方在于可以用下标操作来获取元素。例如下面一段代码：

map<string, int> word_count;
word_count["anna"] = 1;

 将发生以下事情：

（1）在word_count中查找键为"anna"的元素，没有找到（word_count目前是个空map）；

（2）生成一个新的键-值对，它的键是const string类型的对象，保存anna，而它的值 则采用值初始化，即int的值初始化为0；

（3）将这个新的键-值对插入到word_count中；

（4）读取新插入的元素，并将它的值赋为1.

使用下标存在一个很危险的副作用：如果该键不在map容器中，那么下标操作会插入一个具有该键的新元素。而使用insert成员则可避免使用下标操作所带来的副作用。

insert单个pair的时候，其返回值为一个pair，该pair的first成员为指向插入元素的map的迭代器，second成员为一个布尔变量，标识是否添加了新的键。

insert还可以添加一段由迭代器指示的范围，返回void类型。

 

 

7. set类型

set类型只是单纯的键的集合，当我们只想知道一个值是否存在时，用set容器是最适合的。在set中，每个键只能出现一次。

 

8. multimap和multiset

在map或set容器中查找一个元素很简单——该元素要么在要么不在容器中，但对于multimap和multiset，某键对应的元素可能出现多次，要找出与某键对应的所有元素，有三种策略可以解决，而且这三种策略都基于一个事实——在multimap中，同一个键所关联的元素必须相邻存放。

策略1：使用find和count操作(假设contactor是一个以人名为键，电话号码为值的map）

string search_item( "eva xiao" );
typedef multimap<string, string>::size_type sz_type;
sz_type entries = contactors.count(search_item);
multimap<string, string>::iterator iter = contactors.find(search_item);
for( sz_type cnt = 0; cnt!=entries; ++cnt, ++iter )
    cout<<iter->second<<endl;

 策略2、3：使用返回迭代器的关联容器操作

 

也就是说，可以使用lower_bound(k)各upper_bound(k)来确定包含健k的范围，或者直接使用equal_range(k)。