Atela

第9章   sequential container

顺序容器: vector 快速随机访问    list快速插入删除   deque双端，随机访问

C<T> c;

C c(c2);

C c(b,e);  //迭代器,数组,指针，不要求两个容器类型相同

C<T> c(n,t); //只适用与顺序容器

C<T> c(n); //只适用与顺序容器

char *words[]={"a","b","c"};

list<string>::size_type list_size=sizeof(words)/sizeof(char*);

list<string> slist(words, words+list_size);

 

容器元素类型必须满足：1) 支持赋值运算(引用不支持)  2)可复制

除IO标准库类型及auto_ptr类型外，其他所有标准库类型都是有效的容器类型。容器本身也满足。

vector<Foo> empty;//ok

vector<Foo> bad(10);// error， Foo无默认构造函数但有int参数的构造函数

vecotr<Foo> ok(10,1);//ok

 

容器的容器 vector<vector<string> > lines;   //   >>之间必须有空格

 

iter->mem等价于 (*iter).mem;

 

list容器不支持算术运算(iter+n,iter-n,iter+=n,iter-=n), 也不支持关系运算(<=,<,>=,>),

只提供前置后后置自增自减，以及相等不等运算。vector和deque都支持。

list<int> ilist(vec.begin(), vec.end());

ilist.begin()+ilist.size()/2; // error:no addition on list iterators

 

容器定义的类型别名:

size_type  

difference_type//迭代器差值的有符号类型

iterator                 const_iterator  

reverse_iterator  const_reverse_iterator

value_type

reference  //元素的左值类型，value_type&同义词

const_reference  //const value_type&同义词

 

c.begin(); c.end();

c.rbegin(); //返回reverse_iterator,指向c的最后一个元素

c.rend();//返回reverse_iterator,指向第一个元素前面的位置

容器c为const则返回const_reverse_iterator

 

c.push_back(t);

c.push_front(t); //只适用于list和deque

c.insert(p,t);//迭代器p前面插入t,返回新元素的迭代器

c.insert(p,n,t);//返回void

c.insert(p,b,e);//返回void

 

容器的关系运算：容器类型和元素类型都完全相同。

容器大小操作：

c.size(); //返回c::size_type

c.max_size();

c.empty();

c.resize(n);//n<c.size()删除多余，n>c.size(),值初始化新元素

c.resize(n,t);//新元素值为t

 

c.front();c.back();//返回引用,若c为空则未定义

c[n];c.at(n);// vector,deque

 

c.erase(p);//返回迭代器，指向被删元素后面的元素,若p指向超出末端的下一位置，则未定义。

c.erase(b,e);//返回迭代器,若e指向超出末端的下一位置,则也返回超出末端的下一位置。

c.clear();//void

c.pop_back();//void,若c为空，则未定义

c.pop_front();//void,若c为空，则未定义，只适用于list或deque

 

c1=c2;//c1和c2类型要完全相同,类型不同则使用assign

c1.swap(c2);//c1和c2类型要完全相同,速度比赋值快,不会使迭代器失效

c.assign(b,e);//b和e必须不指向c中元素,执行后迭代器失效

c.assign(n,t);

 

v.capacity();//vector在必须分配新的存储空间前可以存储的元素总数。

v.reverse(n);//预留存储空间大小,改变capacity的值

 

容器的选择:

1.随机访问:vector,deque

2.在中间位置插入 list

3.只在头部或尾部插入，deque

4.只在读取输入时在容器中间插入元素，然后随机访问，则先list，后复制到vector

5.如果既要随机访问，又要在中间位置插入删除元素，则考虑两者的使用的频率

 

string支持大部分vector操作，除了栈操作：不能使用front,back,pop_back,pop_front

string s1;

string s2(5,’a’);

string s3(s2);

string s4(s3.begin(), s3.end());

string s5(cp);//cp指向以null结尾的C风格字符串

string s6(cp, n);

string s7(s2, pos2);//从pos2开始

string s8(s2, pos2, len2);//从pos2开始的len2个字符，无论len2值多少，最多只能复制s2.size()-pos2个字符

 

与容器共有的string操作:

s.insert(p, t);

s.insert(p, n, t);

s.insert(p, b, e);

s.assign(b, e);

s.assign(n, t);

s.erase(p);

s.erase(b, e);

 

string特有的版本:

s.insert(pos, n, c);

s.insert(pos, s2);

s.insert(pos, s2, pos2, len);

s.insert(pos, cp, len);

s.insert(pos, cp);

s.assign(s2);

s.assign(s2, pos2, len);

s.assign(cp, len);

s.assign(cp);

s.erase(pos, len);

 

string特有操作

s.substr(pos, n);

s.substr(pos);

s.substr();

 

s.append(args);//追加,返回引用

s.replace(pos, len, args);//删除，用args替换，返回引用

s.replace(b, e, args);

append和replace的参数args

s2

s2, pos2, len2

cp                             // cp指向以null结束的数组

cp, len2                  // cp指向以null结束的数组

n, c

b2, e2

 

find操作都返回string::size_type,没找到则返回string::npos

s.find(args);

s.rfind(args);

s.find_first_of(args);

s.find_last_of(args);

s.find_first_not_of(args);

s.find_last_not_of(args);

find操作的参数args

c, pos                         //从下标pos开始查找字符c，pos默认值为0

s2, pos                       //从下标pos开始查找string对象上，pos默认值为0

cp, pos                      //cp指向null结尾的C风格字符串,pos默认值为0

cp, pos, n                 //pos和n无默认值,从pos开始查找cp指向的前n个字符

 

string::size_type pos=0;

while ((pos = name.find_first_of(numerics, pos)) != string::npos)

{

//…

++pos;}

 

s.compare(s2);

s.compare(pos1, n1, s2);

s.compare(pos1, n1 ,s2, pos2, n2);

s.compare(cp);  //cp指向以null结尾的字符串

s.compare(pos1, n1, cp);

s.compare(pos1, n1, cp, n2);

 

顺序容器适配器:stack  queue   priority_queue有优先级管理的队列

适配器通用操作和类型：

size_type

value_type

container_type

A a;

A a(c);

关系操作符: == != <  <=  >  >=

支持关系运算

 

覆盖基础容器类型：stack,queue都基于deque，priority_queue基于vector

创建适配器时，通过指定适配器的第二个类型实参覆盖基础容器类型

stack可任意，queue的基础容器要有push_front运算,因此不能建立在vector上

priority_queue需要随机访问，因此可建立在vector和deque上

 

stack适配器操作

s.empty();

s.size();

s.pop();

s.top();

s.push(item);

 

队列queue和优先级队列priority_queue支持的操作：

q.empty();

q.size();

q.pop();

q.front();           //只适用于queue

q.back();           //只适用于queue

q.top();             //返回最高优先级的元素值,只适用于priority_queue

q.push(item);  //对于queue在队尾压入，对于priority_queue放在优先级比它低的元素前面

 

 

 

第10章 associative container 关联容器

map         set

multimap//支持同一个键多次出现的map类型

multiset//支持同一个键多次出现的set类型

 

#inlcude<ultility> pair类型

pair<T1, T2> p1;  //值初始化

pair<T1, T2> p1(v1,v2);

make_pair(v1,v2);

p1 < p2

p1 == p2

p.firist

p.second

 

关联容器支持的操作:

1.关联容器共享大部分顺序容器操作，但不支持front,back,push_front,pop_front,push_back,pop_back.

2. C<T> c;

    C<T> c1(c2);

    C<T> c(b,e);

3. 关系运算

4.begin,end,rbegin,rend;

5.容器类型别名: map的value_type是pair类型

6.swap和赋值操作，但不支持assign

7.clear和erase,但关联容器的erase返回void

8.size，max_size,empty,但不支持resize

 

map<k, v> m;

map<k, v> m(m2);

map<k, v> m(b, e); //元素的类型必须能转换为pair<const k, v>

键类型k必须定义<操作符，严格弱排序 strict weak ordering

 

map<k, v>::key_type                       //键类型

map<k, v>::mapped_type              //关联的值类型

map<k, v>::value_type                   //pair<const k,v>类型，即first元素为const map<k,v>::key_type，second元素为map<k,v>::mapped_type.

                                                   //值可改，键不可改，对迭代器解引用获得指向value_type的引用

用下标访问不存在的元素将导致在map容器中添加新元素,它的键即为下标值,并对值类型值初始化。

 

m.insert(e); //若e.first不在m中则插入，反之m不变。返回pair类型对象,包含指向e.first元素的map迭代器,及bool对象表示是否插入了该元素.

m.insert(beg, end);//返回void

m.insert(iter, e); //以iter为起点搜索，查找是否有e.first对应的键元素，如果没有，则插入e。返回一个迭代器，指向具有e.first键的元素

 

使用insert可避免使用下标操作符带来的副作用:不必要的初始化。

word_count["Anna"]=1;    //查找Anna,若没有则创建，值初始化，插入map对象中, 最后读取并将值赋为1

pair<map<string, int>::iterator, bool> ret = word_count.insert(map<string, int>::value_type("Anna",1);

word_cound.insert(make_pair("Anna",1);

 

查找或读取map中元素,下标会自动插入新元素,考虑使用

m.count(k);   //返回k出现的次数,map中只能为0或1

m.find(k);      //返回指向k的迭代器,若k不存在则返回超出末端的迭代器

 

if (word_count.count("foobar"))  occurs = word_count["foobar"];    //对元素两次查找

map<string, int>::iterator it = word_count.find("foobar");

if (it != word_count.end()) occurs = it->second;                                   //一次查找

 

m.erase(k);  //返回size_type类型的值,表示删除的元素个数

m.erase(p);//p不能等于m.end(),  返回void

m.erase(b, e);//返回void

 

 

set容器支持的操作基本与map容器一致，构造函数，insert count find erase

除了不支持下标操作符,没有定义mapped_type类型，value_type不是pair类型而等价于key_type。

与map一样,带有一个键参数的insert返回pair类型，包含一个指向该键元素的迭代器和是否插入元素的bool。

set的键元素与map一样，不能修改。

 

mutimap multiset 头文件也是 map和set

带有一个键参数的erase删除拥有该键的所有元素并返回删除的个数。

查找元素:

1)typedef mutimap<string, string>::size_type sz_type;

   sz_type entries = authors.count(k);

mutimap<string, string>::iterator iter = authors.find(k);

for (sz_type cnt = 0; cnt != entries; ++cnt, ++iter)

               cout <<iter->second << endl;

2)map,set,mutimap,multiset都使用

   m.lower_bound(k);   //返回指向键不小于k的第一个元素的迭代器

   m.upper_bound(k); //返回指向键大于k的第一个元素的迭代器

   m.equal_range(k);  //返回pair对象，包含两个迭代器，first等价于m.lower_bound(k), second等价于m.upper_bound(k).

   typedef multimap<string, string>::iterator author_it;

   author_it beg = authors.lower_bound(k), end=authors.upper_bound(k);

   while (beg != end){cout<<beg->second<<endl; ++beg;}

   

   pair<author_it, author_it> pos = authors.equal_range(k);

    while(p->first != pos->second){cout<<pos.first->second<<endl; ++pos.first;}

 

第11章 泛型算法  generic algorithm

#include<algorithm>

#include<numeric>

accumulate(v.begin(), v.end(),a);   //累加初值a与容器元素类型匹配

fill(v.begin(), v.end(), t);  //将t的副本分别写入,要保证输入范围有效

fill_n(v.begin(), n, t);  //写入n个t的副本,要保证输入范围有效，n个元素必须已经存在

back_inserter迭代器适配器,back_inserter(container);生成一个绑定在容器上的插入迭代器,

试图通过这个迭代器给元素赋值时,赋值运算将调用push_back来添加元素。

vector<int> ivec; //empty

fill_n (back_inserter(ivec),10,0);  //ok

copy (ilst.begin(), ilst.end(), back_inserter(ivec));  //效率差,一般直接vector<int> ivec(ilst.begin(), ilst.end());

replace(ilst.begin(), ilst.end(), a, b);//将所有等于a的元素替换为b

如果不想改变原序列则用replace_copy

vector<int> ivec;

replace_copy(ilst.begin(), ilst.end(), back_inserter(ivec), a, b);

 

sort(words.begin(), words.end());       //使用<操作符比较,

vector<string>::iterator end_unique =

                             unique(words.begin(),words.end());  //"删除"相邻的重复元素，把重复的元素移动到序列末尾，返回的迭代器指向超出无重复的元素范围末端的下一位置

words.erase(end_unique,words.end());

stable_sort(words.begin(), words.end(), isShorter);  //稳定排序,重复元素相对位置不变,第3个参数使用谓词predicate

// bool isShorter(const string &s1, const string &s2){return s1.size() < s2.size();}

//bool GT6(const string &s){return s.size()>=6;}

vector<string>::size_type wc= count_if (words.begin(), words.end(), GT6); //返回谓词函数返回条件成立的元素个数

 

插入迭代器

1)back_inserter : push_back实现插入的迭代器

2)front_inserter: push_front实现插入，vector不能用

3)inserter: insert实习插入，第二个实参指向插入起始位置的迭代器

  list<int> ilst,ilst2,ilst3;

for (list<int>::size_type i=0; i!=4; ++i) ilst.push_back(i);

copy (ilst.begin(), ilst.end(), front_inserter(ilst2);   // 0123

copy(ilst.begin(),ilst.end(), inserter(ilst3, ilst3.begin()); //3210

 

iostream 迭代器: 自增，解引用，赋值。 istream提供==，！=运算，ostream不提供比较运算

都是类模板，任何定义<<操作符的类型都可以定义istream_iterator,定义>>的类型都可以定义ostream_iterator

istream_iterator<T> in(strm);  // 创建从输入流strm中读取T类型对象的istream_iterator对象

istream_iterator<T> in;            //istream_iterator对象的超出末端迭代器

ostream_iterator<T> in(strm);  //创建将T类型的对象写到输出流strm的ostream_iterator对象, ostream_iterator不提供超出末端迭代器

ostream_iterator<T> in(strm, delim);//创建将T类型的对象写到输出流strm的ostream_iterator对象,在写入过程中使用delim作为元素的分隔符,delim是以空字符结束的字符数组

 

istream_iterator<int> in_iter(cin);

istream_iterator<int> eof;

while(in_iter != eof) vec.push_back(*in_iter++);  //vector<int> vec(in_iter, eof);读cin,直到文件结束或输入的不是int为止

 

ostream_iterator<string> out_iter(cout,"\n");

istream_iterator<string> in_iter(cin), eof;

while(in_iter !=eof) *out_iter++ = *in_iter++;

 

一旦给ostream_iterator对象赋值,写入就提交了,没法改变这个值

ostream_iterator没有->操作符

 

从标准输入读取一些数,将不重复的数写到标准输出

istream_iterator<int> cin_it(cin),eof;

vector<int> ivec(cin_it, eof);

sort(ivec.begin(), ivec.end());

ostream_iterator<int> out_it(cout," ");

unique_copy(ivec.begin(), ivec.end(), out_it);

 

反向迭代器：需要使用自减操作符，流迭代器没有。

sort(vec.rbegin(), vec.rend());  //实现降序

find(vec.rbegin(),vec.rend(),',');//反向开始搜索

 

const迭代器

使用时注意迭代器范围

find_first_of(it, roster1.end(), roster2.begin(), roster2.end());

//如果it为const_iterator, 而roster为非const容器end()返回非const迭代器,用来指定迭代器范围的两个迭代器类型不同，将无法编译

 

迭代器种类：低级别迭代器可使用任意更高级迭代器替代

1.输入迭代器   == != ++ * –>           find accumulate   istream_iterator

2.输出迭代器  ++ *    只能写一次       copy  ostream_iterator

3.前向迭代器:读写指定同期,以一个方向遍历序列，支持输入输出迭代器的所有操作，还支持对同一元素的多次读写  replace

4.双向迭代器: --   reverse  标准库容器提供的迭代器至少达到双向迭代器的要求   list map set

5.随机访问迭代器:关系操作符< <= > >= iter+n, iter-n, iter1-iter2,iter[n]              sort  vector deque string      所以list不能用sort排序

 

算法的形参模式

alg (beg, end, other parms);

alg (beg, end, dest, other parms);

alg (beg, end, beg2, other parms); //假定以beg2开始的范围与beg end一样大

alg (beg, end, beg2, end2, other parms);

 

sort (beg, end);  //  <操作符

sort (beg, end, cmp);

find (beg, end, val);   //==操作符   带谓词形参加_if,因形参个数相同导致二义性

find_if (beg, end, pred);

reverse(beg, end);

reverse_copy(beg, end, dest);

 

list特有操作：对list容器应优先使用特有的成员版本，而不是泛型算法

lst.merge(lst2);

lst.merge(lst2, comp); //两个版本都要先排序, 合并后lst2为空，返回void

 

lst.remove(val);

lst.remove_if(unaryPred);//调用lst.erase实现,返回void

 

lst.reverse();

lst.sort();

lst.sort(comp);

 

lst.splice(iter, lst2);

lst.splice(iter, lst2, iter2);

lst.splice(iter, beg, end);//将lst2的元素移到lst中迭代器iter指向元素的前面,在lst2中删除移出的元素

 

lst.unique();

lst.unique(binaryPred);//调用erase删除同一个值的连续副本,第一个用==判断，第二个用指定谓词函数判断

 

list特有版本与其泛型算法两个重要区别:

1.remove和unique真正删除了指定元素

2.merge和splice会破坏实参

使用merge的泛型算法时将合并的序列写入目标迭代器指向的对象，两个输入序列不变。