C++ Primer读书笔记–第九章

标准库容器类型:vector,list,deque。这些容器提供了许多完全一样或者相似的接口。

适配器类型:stack,queue,priority_queue。适配器是使用上述容器,对接口进行重新包装的容器类型。

9.1 顺序容器的定义

vector<string> svec;
list<int> ilist;
deque<MyClass> classes;

初始化

C<T> c;  //默认初始化
C<T> c(c2); //用其他容器做副本初始化,容器类型和元素类型都必须相同
C<T> c(b,e); //使用两个迭代器之间的元素初始化,容器类型可不同,元素类型兼容即可
C<T> c(n,t); //创建n个值为t的数值
C<T> c(n);   //创建n个元素的容器,每个都为默认值

可作为容器类型<T>的元素类型约定

1、元素支持赋值运算
2、元素必须可以复制

简而言之,除了引用类型和I/O类型之外,都可以作为<T>容器类型
另外,T最好有默认的构造函数,如果需要c(n) 这种形式的构造。

容器中嵌套容器请注意使用空格。
vector< vector<string> > vecvec;

9.2 迭代器和迭代器范围

*itr  返回迭代器指向元素的引用
itr->mem  对iter进行解引用,获取指定元素中名为mem的成员。等效于(*itr).mem
++itr或者itr++ 使迭代器指向下一个
itr1!=itr2  比较两个迭代器不等
itr1==itr2  比较两个迭代器相等

另外vector和deque的迭代器提供了额外的运算
itr+n,itr-n
itr+=n,itr-=n
> >= < <=

迭代器范围

[first,last)
begin开始,end结束

会使迭代器失效的操作

erase

9.3顺序容器的操作

size_type  用以存储容器长度
iterator   容器类型的迭代器
const_iterator  只读迭代器
reverse_iterator  逆序迭代器
const_reverse_iterator  只读逆序迭代器
difference_type  迭代器差值,可为负值
value_type  元素类型
reference  左值类型
const_reference  常量左值类型

begin 指向第一个成员
end  指向最后一个成员的下一个

添加元素

push_back   在最后面插入,都支持
push_front  在前面插入,只适用于list和dequeue
insert  在指定位置插入,可以是一个,也可以是多个
向容器中添加的元素都是副本
添加会使迭代器失效

关系操作符

容器之间的比较都是针对其中元素的比较,所有元素必须定义了比较函数(<)才行。

容器大小的操作

size()  返回容器大小
max_size()  返回容器最多容纳的数量
empty()
resize(n)  重新设定容器大小,超过n的被删掉
 

访问元素

front()  调用前务必确定容器非空!
back()   调用前务必确定容器非空!
c[n]  只能vector和deque
c.at(n)  只能vector和deque

删除元素

erase(p)  删除某个具体元素(可根据key或者迭代器)
erase(b,e)  删除一段迭代器之间的元素
clear()  清空
pop_back()  删除最前,返回void
pop_front() 删除最前,返回void

寻找元素

标准库中的find()算法函数

给容器赋值

c1 = c2;
先删除c1中的元素,再添加上c2所有的元素

assign

首先删除容器中所有的元素,然后将其参数所指定的新元素插入到该容器中。与赋值=的区别是,根据迭代器进行assign,可以支持不同容器类型,兼容元素间的操作

swap

首先删除左边容器中的元素,然后将右边的插入到左边容器,只是交换指针

9.4 vector容器的自增长

    为了支持快速的随机访问,vector容器中的元素以连续的方式存放。如果连续空间中不够容纳新元素,必须重新delete new出更大的空间,如果每增长一个元素就来一次new delete,会很慢,因此vector容器实现了快速的内存分配策略,即实际分配容量要大于所需要的容量(是所需容量的两倍)。

 capacity操作获取当前空间能容纳多少元素,一般是>=size()的。
 reserve(n)强制把容器大小改为不小于n的容量,一般会导致容器重新分配空间,使得容量变大,以进一步减少new delete等重新分配内存的次数。

9.5 容器的选用

vector和deque提供了元素的快速随机访问,代价是在中间插入元素耗费巨大。
list在任何位置可以O(n)插入,代价是随机访问耗费巨大。
deque比之于vector的区别是,可以在头部高效插入,删除。

容器选择法则:
(1)如果程序要求随机访问,使用vector或者deque
(2)如果必须在中间插入元素,使用list
(3)如果只需要在首部插入,使用deque
(4)如果只在一开始要中间插入,后来都随机访问,可以一开始使用list插入,完成后复制给一个vector。

最后的法则:如果随机访问、中间插入都需要,那么判断哪种操作占优势,优先满足占优势的操作。

9.6 string again

string : Another 容器

除了定义在string类型之上的操作之外,可以将string视为char类型的容器。
string支持如下:
1、typedef 如size_type,各种iterator,difference_type,value_type,reference(左值类型)
2、各种构造函数
3、push_back,insert操作(同样不支持push_front!
4、size , empty,resize,max_size等长度操作
5、下标at操作等
6、begin、end等操作
7、erase、clear等操作,不支持pop_back和pop_front等操作
8、支持各种复制如assign,swap,=操作
9、支持capacity和reserve操作

string的额外操作

另外string支持一些特有操作(不被其他容器共享):
substr函数,返回子串
append和replace函数,用于修改string对象
find、find_first_of,find_last_of,如果找不到,返回str.npos()

find(c,pos),从第pos个字符开始,查找字符c,pos默认为0,
find_first_of(string,pos),从pos开始,查找string中包含的第一个出现的任意字符

使用find_first_of的例子:

string num("0123456789");
string name("r2d2");
string::size_type pos = 0;
while((pos = name.find_first_of(num,pos))!=string::npos)
{
  cout<<"Find at index"<<pos<<endl;
  pos++;
}
其余的find_last,rfind类似上述,不写了。

string对象的比较

string定义了所有关系运算,可以比较两个string是否相等(==),不等(!=),大于,小于运算等。
采用字典序比较:逐个字符比较字符串,直到比较到某个位置上,两个string的该位置字符不等。

另外,string应用字典序实现了compare函数,返回类似c语言compare函数的结果(<0 =0 >0)

9.7 容器适配器

让已经存在的容器以另外的抽象方式工作,例如栈,队列等。通俗来看就是STL中的类型

常用容器适配器stack,queue,都给予deque实现

stack

1、stack声明:
stack<int> stk; 或者 stack<int> stk(deq);或者stack<string,vector<string> > stk;
最后面这个可以覆盖默认容器类型,修改为vector
2、可以进行各种关系比较如< > ==等,都是给予栈内元素的
3、操作
empty() size() push() pop()–删除栈顶不返回 top()–返回栈顶不删除
 

queue priority_queue

priority_queue,优先队列,也就是堆。
priority_queue<int> 默认使用<的比较
想自定义比较有很多方法:
priority_queue<int,vector<int>,cmp>,cmp使用下面的两个方法均可

 

 

例子1:
struct cmp{
    bool operator() ( Node a, Node b ){
        if( a.x== b.x ) return a.y> b.y;
        return a.x> b.x; }
};

 

 

 

例子2:

struct myCmp : binary_function<Node,Node,bool>{
    bool operator () (const Node& a,const Node& b)
    {
        return a.data < b.data;
    }
};

队列就不多说了,他们支持的操作有:
队列:empty() size() pop() push() front() back()
优先队列:empty() size() pop() top() push()  

Leave a Reply

Your email address will not be published.