首页 思维导图 详情

16章 string类和标准模板库

2020-02-24 10:29:02 9 举报
AI智能生成
C++ Plus 笔记
C++
作者其他创作
大纲/内容
标准模板库
内容
容器、迭代器、函数对象和算法的模板
模板类vector
条件
头文件
#include<vector>
名称空间
using namespace std;
声明
vector<double> v1;
初始化
vector<double> v2(5);
包含5个元素的vector数组
vector<int> vec; //声明一个int型向量 
vector<int> vec(5); //声明一个初始大小为5的int向量 
vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量 
vector<int> vec(tmp); //声明并用tmp向量初始化vec向量 
vector<int> tmp(vec.begin(), vec.begin() + 3); //用向量vec的第0个到第2个值初始化tmp 
int arr[5] = {1, 2, 3, 4, 5}; 
vector<int> vec(arr, arr + 5); //将arr数组的元素用于初始化vec向量 
//说明：当然不包括arr[4]元素，末尾指针都是指结束元素的下一个元素， //这个主要是为了和vec.end()指针统一。 
vector<int> vec(&arr[1], &arr[4]); //将arr[1]~arr[4]范围内的元素作为vec的初始值
子主题
访问元素
下标 v1[0]//和数组一样
vector<int>rating(5)
for(int i=0;i<5;i++)
       cout<<rating[i]<<endl;
迭代器
声明
vector<double>::iterator pd;
相当于一个指针一样
赋值
vector<double>scores;
pd=score.begin();
....
初始化
vector::iterator pd=score.begin();
C++11中可以
auto pd=score.begin();
基本操作
前提
vector::iterator pd;
vector<double>scores;
pd=score.begin();
*(解析运算符)
*pd=22.3
scores数组第一个元素值为22.3
++/--
++pd;
指向scores数组的下一个元素
应用
遍历容器内容
for( pd=score.begin() ; pd != scores.end() ; pd++ )
         cout<<*pd<<endl;
基本的方法
几乎所有
STL容器都有
size()
swap()
vector<double>vec1;
vector<double>vec2;

vec1.swap(vec2);//交换vec1与vec2的内容
begin()
end() //标识超过结尾的位置。不是最后一个元素
其他
push_back()
vec.push_back( elem );//在末尾添加新元素
erase()
格式
vec.erase(vec.begin()+2);删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j);删除区间  [i,j）;区间从0开始
注意STL区间用[ p1,p2 )来表示从p1到p2(不包括)的区间
说明
删除后，后面的字母会自动向前移
insert()
格式
vec.insert(  vec.begin()+i , a );//在第i-1个元素前插入a元素
vec.insert(  vec.begin()+i , n , a );//在第i-1个元素前插入n 个 a元素
vector<double> vec1;
vector<double>vec2;

vec1.insert( vec1.begin() , vec2.begin()+1 , vec2.end()  )  //将vec2 的除第一个元素插入到vec1中
STL方法
（非成员函数）
for_each()
格式
vector<Review>book;//Review 是一个结构体
for_each( book.begin() , book.end() , ShowReview );  // ShowReview 是一个普通函数，显示Review中的内容
struct Review{
     std::string title;
     int rating;
};
void ShowReview( const Revie & rr)
{
      std:cout<<rr.rating<<" "<<rr.title<<std::endl;
}
作用
代替for循环，可替换一下代码
vector<Review>::iterator pr;
for(pr = book.begin() ;pr != book.end() , pr++ )
     ShowReview( *pr );
为什么很多时候不直接用
for(int i=0;i<book.size();i++)
          Show(book[i]);
//而用迭代器呢？
random_shuffle()
格式
random_shuffle(book.begin() , book.end() );
作用
随机排列该区间的元素
sort()
第一种版本
（两个参数）
作用
只能按升序对vector类对象进行排列
格式
基本数据
vector<int> coolstuff;
...
sort(coolstuff.begin() , coolstuff.end() );
说明
会自动从小到大（升序）排列
用户自定义类
(结构，类)
sort（book.begin() , book.end()）;// 只是这样还不行，必须定义能够处理
                                                              该类型对象的operator<()函数 
bool operator<(const Review &r1, const Review &r2 )
{
         return r1.title < r2.title;
}
说明
bool operator< （）直接在main外部声明即可，不需要什么限定域
上版本operator<(）函数按title成员的字母排序，如果title相同，则
按rating排序。
第二种版本
作用
不想按升序排序，或者其它。vector对象是用户自定义类型，
除了上面方法，也可以用这个方法
格式
sort（book.begin() , book.end() ,Comp）;
bool Comp( const Review & r1 , const Review & r2)
{
    return r1.rating<r2.rating;
}
说明
sort（）把book.begin() ... 中的元素传递给Comp
bool Comp()也是直接在main()外部即可
与operator<()相比，Comp（）函数排序不太完整。
两个对象中的title成员相同，operator<()将按rating进行排序，
Comp（）视它们为一样。
operator<——全排序
Comp()——完整弱排序
问题！！如果自定义类型是类，需要按它的私有成员排序怎么办？
按类对象私有数据排序
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Text{

public:
Text(int aa,int bb):a(aa),b(bb){}
int & Geta(){ return a;}
int & Getb(){ return b;}
void show(){ cout<<a;
}
//protect:
private:
int a;
int b;

};  
bool Comp(Text &T1,Text &T2);
int main()
{
vector<Text>  vec;
Text t1(1,1);
Text t2(2,2);
Text t3(3,3);
vec.push_back(t1);
vec.push_back(t3);
vec.push_back(t2);
vec[0].show();vec[1].show();vec[2].show();
cout<<endl;
sort(vec.begin(),vec.end(),Comp);
vec[0].show();vec[1].show();vec[2].show();
cout<<endl;
}
bool Comp(Text &T1,Text &T2)
{
return (T1.Geta()<T2.Geta());
}
说明
在devC++上运行不了、
在visualC++6.0上可以运行
copy算法
1.
作用
将数据从一个容器复制到另一个容器中。算法以迭代器方式实现。
可以在数组之间复制。
格式
copy( cats , cats+10 , dice.begin() );
说明
前两个参数表示要复制的范围。（最好是输入迭代器）
最后一个参数表示要将第一个元素复制到什么位置。（最好是输出迭代器）
例子
int cats[10] = { 6,7,2,9,4,11,8,7,10,5};
vector<int> dice（10）;
copy( cast , cast + 10 ,dice.begin() );
copy会覆盖原来迭代器的内容。
不能使用copy()将数据放到空矢量中。vector<int>dice(10) 一定要有10；
2
作用
将信息复制到显示器上。把第三个参数表示输出流的迭代器。
输出流迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
该模板是输出迭代器概念的一个模型，也是一个适配器——一个类或函数。
创建
声明
ostream_iterator<int,char> out_iter(cout , " " );
说明
模板参数
第一个参数
指出被发送给输出流的数据类型
第二个参数
指出了输出流使用的字符类型
//!!!可以省略，默认和前面的相同。哪个可以省略？？不知道
构造函数参数
第一个参数
要使用输出流//可是是cout，可以是文件
第二个参数
在发送给输出流的每个数据项后显示的分隔符
例子
*out_iter++ = 15;
说明
将15由空格组成的字符串发送到cout管理的输出流中，并为下一个输出操作做好了准备。（指针+1）
相当于cout<<15<<" ";
例子
int cats[10] = { 6,7,2,9,4,11,8,7,10,5};
vector<int> dice（10）;
copy( cast , cast + 10 ,dice.begin() );

ostream_iterator out_iter<int , char>(cout , " " );
copy（dice.begin() , dice.end() , out_iter);
//显示器输出6 7 2 9 4 11 8 7 10 5（有空格）
//不创建命名迭代器
copy（dice.begin() , dice.end() , ostream_iterator<int,char>(cout," "));
3
作用
把输入流的信息复制到数组上
输入流迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
创建
声明
istream_iterator<int,char> in_iter1(cin);
istream_iterator<int,char> in_iter2()；
说明
模板参数
第一个参数
指出要读取的数据类型
第二个参数
输入流使用的字符类型
构造函数参数
使用参数cin表示由cin管理的输入流。//可以是文件
不用参数表示输入失败
例子
istream_iterator in_iter1<int,char>(cin);
istream_iterator in_iter2<int,char>()；

copy(in_iter1,in_iter2,dice.begin());
表示代码从输入流中读取，直到文件结尾、类型不匹配或出现其他输入故障。
copy(istream_iterator <int,char>(cin),stream_iterator<int,char>(),dice.begin());
基于范围的for循环
格式
double price[5] = {4.99 , 10.99 , 6.99 , 6.87 , 7.99 , 8.49};
for ( double x:prices )
       cout<<x<<std::endl;
说明
price的那个位置要求是一种容器。
x前面的类型与容器存储的类型相同。
foreach改成基于范围的for循环
for_each( book.begin() , book.end() , Showview);
相当于
for( auto x ： books ) ShowReview(x);
说明
for_each()中的函数（上是Showview）不能修改容器中的数据；
基于范围的for循环可以修改。
eg:有
viod InflateReview( Review & r){  r.rating++; }

只能是：
for( auto & x: books ) InflateReview(x);//注意有&！！！
泛型编程
前言
STL是一种泛型编程
面向对象编程——关注编程数据方面
泛型编程——关注算法
泛型编程旨在独立于数据类型的代码。完成独立于数据类
型的工具——模板、模板基础+STL（通过算法）。
但必须对元素进行仔细的设计。（如何设计？）
迭代器
为何使用迭代器
作用
模板使算法独立于存储的数据类型。
迭代器使算法独立于容器的类型。
泛型编程旨在使用同一个find函数来处理数组,链表或任何其他容器类型.
首先是处理容器的算法,应尽可能用通用的术语来表达算法,使之独立于数据类型和容器类型.
为使通用算法能够适用于具体情况,应定义能够满足算法需求的迭代器(迭代器正是这样的通用表示),
并把要求加到容器设计上.
即基于算法的要求,设计基本迭代器的特征和容器特征.
如何为两种不同数
据实现find函数
double数组
Double *find_ar( double * ar , int n , const double & val )
{
for(int i=0 ; i<n ; i++)
if( ar[i] == val )
return &ar[i];
return 0;
}

改进（设计迭代器）
//改进1
Typedef double *iterator;
iterator find_ar(iterator ar,int n , const double &val )
{
for(int i = 0 ; i < n; i++ ,ar++  )
if( *ar == val)
return ar;
return 0;
}
//改进2
Typedef double *iterator;
iterator find_ar(iterator begin ,iterator end , const double &val )
{
iterator ar;
for(ar = begin ; ar != end ; ar++ )
if( *ar == val)
return ar;
return end;
}
Node结构
struct Node
{
double item;
Node * p->next;
};

Node* find_ll( Node *head, const double &val )
{
Node * start;
for (start = head; start != 0; start = start->next)
if( start -> item == val )
return start;
return 0;
}
改进（设计迭代器）
//改进1
struct Node
{
double item;
Node * p->next;
};
//迭代器设计
class iterator
{
Node * pt;
Public:
Iterator() :pt(0) {}
Iterayor( Node * pn ) : pt(pn){}
Double operator*() {return pt->item;}
Iterator& operator()
{
Pt = pt -> p_next;
Return *this;
}
Iterator operator++(int)
{
iterator tmp = *this;
Pt = pt->p_next;
Return temp;
}
// …..operator==(),….
};

//设计迭代器后的方程
Interator find_ll( iterator head, const double & val)
{
Iterayor start;
For(start = head; start != 0 ; ++start)
If( *start == val)
Return start;
Return 0;
}
//改进2
设计超尾元素，使与double的改进2差不多
迭代器简要介绍
http://www.cnblogs.com/besty/p/4039264.html
1. 迭代器(iterator)是一中检查容器内元素并遍历元素的数据类型。

(1) 每种容器类型都定义了自己的迭代器类型，如vector:
vector<int>::iterator iter;这条语句定义了一个名为iter的变量，它的数据类型是由vector<int>定义的iterator类型。

(2) 使用迭代器读取vector中的每一个元素：

①iterator 可修改元素
vector<int> ivec(10,1);
for(vector<int>::iterator iter=ivec.begin();iter!=ivec.end();++iter)
{
*iter=2; //使用 * 访问迭代器所指向的元素
}
②const_iterator:
只能读取容器中的元素，而不能修改。
for(vector<int>::const_iterator citer=ivec.begin();citer!=ivec.end();citer++)
{
cout<<*citer;
//*citer=3; error
}
③vector<int>::const_iterator 和 const vector<int>::iterator的区别
const vector<int>::iterator newiter=ivec.begin();
*newiter=11; //可以修改指向容器的元素
//newiter++; //迭代器本身不能被修改 

(3) iterator的算术操作：
①iterator进行++,--操作，
②可以将iter+n,iter-n赋给一个新的iteraor对象。
③使用一个iterator减去另外一个iterator.
const vector<int>::iterator newiter=ivec.begin();
vector<int>::iterator newiter2=ivec.end();
cout<<"\n"<<newiter2-newiter; 

(4)一個很典型使用vector的STL程式:
#include <vector>
#include <iostream>

using namespace std;

int main() {
 vector<int> ivec;
 ivec.push_back(1);
 ivec.push_back(2);
 ivec.push_back(3);
 ivec.push_back(4);
 
 for(vector<int>::iterator iter = ivec.begin();  iter != ivec.end(); ++iter)
  cout << *iter << endl;
 }
迭代器的类型
不同迭代器的区别
重载的运算符不一样，能执行的操作不一样。
eg：有些迭代器可以修改数据，有些不可以
类型
输入迭代器
操作
*iter
读取元素实际的值，只能作为左值
iter->member    
读取实际元素的成员（如果有的话）
++iter 
向前步进（传回新位置）
iter++
   向前步进（传回旧位置）
iter1 == iter2  
判断两个迭代器是否相同
iter1 != iter2   
判断两个迭代器是否不相等
TYPE(iter) 
复制迭代器（copy 构造函数）    
说明
  • 输入迭代器可被程序用来读取容器中的信息.
对迭代器解除引用也不能修改值
  • 并不能保证输入迭代器第二次遍历容器时,顺序不变.另外,输入迭代器被递增后,也不能保证其先前的值仍然可以被解除引用.基于输入迭代器的任何算法都应当是单通行(single-pass)的,不依赖于前一次遍历时的迭代器值,也不依赖于本次遍历汇总前面的迭代器值.
不理解，例子？
  • 注意,输入迭代器是单向迭代器,可以递增,但不能倒退.
输出迭代器
操作
表达式                  功能表述
*iter = value      将元素写入到迭代器所指位置
++iter             向前步进（传回新位置）
iter++             向前步进（传回旧位置）
iter1 == iter2      判断两个迭代器是否相同
iter1 != iter2      判断两个迭代器是否不相等
TYPE(iter)         复制迭代器（copy 构造函数）    

说明
  • 输出指将信息从程序传输给容器的迭代器
  • 输出迭代器与输入迭代器相似,知识解除引用让程序能修改容器值,而不能读取.
  • 简而言之,对于单通行,只读算法,可以使用输入迭代器;而对于单通行,只写算法,则可以使用输出迭代器.
正向迭代器
操作
表达式                 功能表述

*iter               存取实际元素
*iter = value      将元素写入到迭代器所指位置
iter->member        存取实际元素的成员
++iter              向前步进（传回新位置）
iter++              向前步进（传回旧位置）
iter1 == iter2      判断两个迭代器是否相同
iter1 != iter2      判断两个迭代器是否不相等
TYPE()              产生迭代器（default构造函数）
TYPE(iter)          复制迭代器（copy构造函数）      
说明
  • 正向迭代器有输入/输出迭代器的全部功能
  • 与输入和输出迭代器不同的是,它总是按相同的顺序遍历一系列值.
  • 另外,将正向迭代器递增后,仍然可以对前面的迭代器值解除引用(如果保存了它),并可以得到相同的值.这些特征使得多次通行算法称为可能.
按顺序遍历？和前有什么区别？
可以对前面的迭代器解除引用？
双向迭代器
操作
正向迭代器
表达式                 功能表述
*iter               存取实际元素
iter->member        存取实际元素的成员
++iter              向前步进（传回新位置）
iter++              向前步进（传回旧位置）
iter1 == iter2      判断两个迭代器是否相同
iter1 != iter2      判断两个迭代器是否不相等
TYPE()              产生迭代器（default构造函数）
TYPE(iter)          复制迭代器（copy构造函数） 
+
--p                 前置自减迭代器
p--                 后置自减迭代器   
说明
  • 双向迭代器具有正向迭代器的所有特性,同时支持两种(前缀和后缀)递减运算符.
随机访问迭代器
操作
双向迭代器
+
表达式                     功能表述
p+=i                       将迭代器递增i位
p-=i                       将迭代器递减i位
p+i                        在p位加i位后的迭代器
p-i                        在p位减i位后的迭代器
p[i]                       返回p位元素偏离i位的元素引用
p<p1                       如果迭代器p的位置在p1前，返回true，否则返回false
p<=p1                      p的位置在p1的前面或同一位置时返回true，否则返回false
p>p1                       如果迭代器p的位置在p1后，返回true，否则返回false
p>=p1                      p的位置在p1的后面或同一位置时返回true，否则返回false   
说明
像a+n这样的表达式仅当a和a+n都位于容器区间(包括超尾)内时才合法.
迭代器的层次结构
  • 正向迭代器具有输入迭代器和输出迭代器的全部功能,同时还有自己的功能;
  • 双向迭代器具有正向迭代器的全部功能,同时还有自己的功能;
  • 随机访问迭代器具有正向迭代器的全部功能,同时还有自己的功能.
  • 为何需要这么多迭代器呢?
    目的是为了在编写算法尽可能使用要求最低的迭代器,并让它适用于容器的最大区间.
  • 注意,各种迭代器的类型并不是确定的,而只是一种概念性描述.//?
  • vector<int>类的迭代器的类型为vector<int>::interator;vector迭代器是随机访问迭代器
  • list迭代器是双向迭代器。
子主题
概念，改进和模型
（迭代器）
前言
  • STL文献使用术语概念concept来描述一系列的要求.
  • 如果所设计的容器类需要迭代器,可考虑STL,它包含用于标准种类的迭代器模板.
  • 概念可以具有类似继承的关系.然而,不能将C++继承机制用于迭代器.有些STL文献使用术语改进refinement来表示这种概念上的继承,因此,双向迭代器是对正向迭代器概念的一种改进.
  • 概念的具有实现被称为模板model.
看不懂。。
将指针用作迭代器
原因
迭代器是广义的指针，指针满足所有迭代器的要求
应用
迭代器是STL算法的接口，而指针是迭代器。
因此STL算法可以使用指针来对基于指针的非STL容器进行操作。
STL算法可用于常规数组，也可用于自己设计的数组形式，
只要提供适当的迭代器和超尾指示器就可以了。
例子
sort()用于常规数组
const int SIZE = 100;
double Receipts[SIZE];
sort( Receipts , Receipts + SIZE );
预定义迭代器
//??
copy算法
1.
作用
将数据从一个容器复制到另一个容器中。算法以迭代器方式实现。
可以在数组之间复制。
格式
copy( cats , cats+10 , dice.begin() );
说明
前两个参数表示要复制的范围。（最好是输入迭代器）
最后一个参数表示要将第一个元素复制到什么位置。（最好是输出迭代器）
例子
int cats[10] = { 6,7,2,9,4,11,8,7,10,5};
vector<int> dice（10）;
copy( cast , cast + 10 ,dice.begin() );
copy会覆盖原来迭代器的内容。
不能使用copy()将数据放到空矢量中。vector<int>dice(10) 一定要有10；
2
作用
将信息复制到显示器上。把第三个参数表示输出流的迭代器。
输出流迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
该模板是输出迭代器概念的一个模型，也是一个适配器——一个类或函数。
创建
声明
ostream_iterator<int,char> out_iter(cout , " " );
说明
模板参数
第一个参数
指出被发送给输出流的数据类型
第二个参数
指出了输出流使用的字符类型
构造函数参数
第一个参数
要使用输出流//可是是cout，可以是文件
第二个参数
在发送给输出流的每个数据项后显示的分隔符
例子
*out_iter++ = 15;
说明
将15由空格组成的字符串发送到cout管理的输出流中，并为下一个输出操作做好了准备。（指针+1）
相当于cout<<15<<" ";
例子
int cats[10] = { 6,7,2,9,4,11,8,7,10,5};
vector<int> dice（10）;
copy( cast , cast + 10 ,dice.begin() );

ostream_iterator out_iter<int , char>(cout , " " );
copy（dice.begin() , dice.end() , out_iter);
//显示器输出6 7 2 9 4 11 8 7 10 5（有空格）
//不创建命名迭代器
copy（dice.begin() , dice.end() , ostream_iterator<int,char>(cout," "));
3
作用
把输入流的信息复制到数组上
输入迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
创建
声明
istream_iterator<int,char> in_iter1(cin);
istream_iterator<int,char> in_iter2()；
说明
模板参数
第一个参数
指出要读取的数据类型
第二个参数
输入流使用的字符类型
构造函数参数
使用参数cin表示由cin管理的输入流。//可以是文件
不用参数表示输入失败
例子
istream_iterator in_iter1<int,char>(cin);
istream_iterator in_iter2<int,char>()；

copy(in_iter1,in_iter2,dice.begin());
表示代码从输入流中读取，直到文件结尾、类型不匹配或出现其他输入故障。
copy(istream_iterator <int,char>(cin),stream_iterator<int,char>(),dice.begin());
其他有用迭代器
头文件
iterator
输出流迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
该模板是输出迭代器概念的一个模型，也是一个适配器——一个类或函数。
创建
声明
ostream_iterator<int,char> out_iter(cout , " " );
说明
模板参数
第一个参数
指出被发送给输出流的数据类型
第二个参数
指出了输出流使用的字符类型
//!!!可以省略，默认和前面的相同。哪个可以省略？？不知道
构造函数参数
第一个参数
要使用输出流//可是是cout，可以是文件
第二个参数
在发送给输出流的每个数据项后显示的分隔符
例子
*out_iter++ = 15;
说明
将15由空格组成的字符串发送到cout管理的输出流中，并为下一个输出操作做好了准备。（指针+1）
相当于cout<<15<<" ";
输入流迭代器
头文件
#include<iterator.h>
模板
ostream_iterator
创建
声明
istream_iterator<int,char> in_iter1(cin);
istream_iterator<int,char> in_iter2()；
说明
模板参数
第一个参数
指出要读取的数据类型
第二个参数
输入流使用的字符类型
构造函数参数
使用参数cin表示由cin管理的输入流。//可以是文件
不用参数表示输入失败
reverse_interator
功能
对reverse_interator执行递增会导致它被递减。
不对常规迭代器递减是为了简化对已有的函数的使用
例子
copy( dice.begin(),dice.end(),out_iter );
想要反向打印dice的内容
copy( dice.rbegin() , dice.rend() , out_iter );
说明
 rbegin(),rend()是vector的反向迭代器
rbegin()与end()的值相同，rend()与begin()的值相同，
但类型不同（一个是reverse_iterator,一个iterator）
反向指针先递减，再解除引用。
int cats[10] = { 6,7,2,9,4,11,8,7,10,5};
vector<int> dice（10）;
copy( cast , cast + 10 ,dice.begin() );

vector<int>::reverse_iterator ri;
for ( ri = dice.rbegin() ; ri != dice.rend()； ++ri)
        cout<<*ri<<" ";
cout<<endl;
如果可以在显式声明迭代器和使用STL函数来处理内部问题；
eg: 上通过将rbegin()返回值传递给函数和copy()函数到显示器中；
选择后者，工作少，出错少
如果想创建reverse_interator迭代器怎么办？？
insert_
作用
copy（）不能自动根据发送值调整目标容器的长度，前要将dice声明包含10个元素
如果预先不知道dice的长度？或者不是覆盖，是添加到dice中怎么办？
类型
back_insert_iterator
功能
将元素插入到容器尾部
说明
只能用于允许在尾部快速插入的容器（快速插入时一个时间固定的算法）
eg:vector允许
front_insert_iterator
功能
元素插入到容器前端
说明
只能用于允许在起始位置做时间固定插入的容器类型，
vector不能满足，queue满足
insert_iterator
功能
参数指定的位置前面
说明
没有限制
可以用insert_iterator将复制数据的算法转换为插入数据的算法//??
创建
back_insert_iterator<vector<int> > back_iter( dice );
表示在dice前插入的迭代器
*back_iter=3//？？？可行吗？是不是这样已经表示在dice前已经插入了元素？是的
insert_iterator<vector<int> > insert_iter(dice , dice.begin() );
表示在dice容器的dice.begin()插入的迭代器
说明
将容器类型作为模板参数，将实际的容器标示符作为构造函数参数。
必须声明容器类型：迭代器必须使用合适的容器方法。
对insert还需要一个指示插入位置的构造函数
应用
代码
// inserts.cpp -- copy() and insert iterators
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <algorithm>
void output(const std::string & s) {std::cout << s << " ";}
int main()
{
using namespace std;
string s1[4] = {"fine", "fish", "fashion", "fate"};
string s2[2] = {"busy", "bats"};
string s3[2] = {"silly", "singers"};
vector<string> words(4);
copy(s1, s1 + 4, words.begin());
for_each(words.begin(), words.end(), output);
cout << endl;

// construct anonymous back_insert_iterator object
copy(s2, s2 + 2, back_insert_iterator<vector<string> >(words));
for_each(words.begin(), words.end(), output);
cout << endl;
// construct anonymous insert_iterator object
copy(s3, s3 + 2, insert_iterator<vector<string> >(words, words.begin()));
for_each(words.begin(), words.end(), output);
cout << endl;
// cin.get();
return 0;
}
结果
fine fish fashion fate
fine fish fashion fate busy bats
silly singers fine fish fashion fate busy bats
说明
都是输出容器概念的模型
容器
容器概念
含义
  • 容器概念指定了所有STL容器类都必须满足的一系列要求.
特点
容器是存储其他对象的对象。被存储的对象必须是同一种类型的
存储在容器中的数据为容器所有,这意味着当容器过期时,存储在容器中的数据也将过期
(然而,如果数据是指针的化,则它指向的数据并不一定过期).
存储再容器中的对象的
要求
不能将任何类型的对象存储在容器中,具体地说,类型必须是可复制构造的和可赋值的.
基本类型满足这些要求;
只要类定义没有将复制构造函数和赋值运算符声明为私有或保护的,则也满足这种要求
C++改进了这些概念,添加了术语可复制插入copyInsertable和可移动插入MoveInsertable.//??
一些基本的容器特征
（几乎所有容器都有的）
（通用特征）
表格总结
  • 其中,X表示容器类型,a和b表示类型为X的值;r表示类型为X&的值;u表示类型为X的标识符.
  • 表达式返回类型说明复杂度
    X::iterator指向T的迭代器类型满足正向迭代器要求的任何迭代器编译时间
    X::value_typeTT的类型编译时间
    X u;创建一个名为u的空容器固定
    X();创建一个匿名的空容器固定
    X u(a);调用复制构造函数后u==a线性
    X u=a;作用同X u(a);线性
    r=a;X&调用赋值运算符后r==a线性
    (&a)->~X();void对容器中每个元素应用析构函数线性
    a.begin()迭代器返回指向容器第一个元素的迭代器固定
    a.end()迭代器返回超尾值迭代器固定
    a.size()无符号整型返回元素个数,等价于a.end()-a.begin()固定
    a.swap(b)void交换a和b的内容固定
    a==b可转换为bool如果a和b的长度相同,且a中每个元素都等于(==为真)b中相应的元素,则为帧线性
    a!=b可转换bool返回!(a==b)线性

表格内容详解
X::iterator 
创建X的迭代器
vector<int>::iterator t1;
迭代器的作用见上
X::value_type
创建以容器存储的数据类型的变量/对象
vector<C> vec;  //假设C是自定义类型
vector<C>::value_type x;
那么第二句定义的变量x的数据类型是C。
vector<int> vec;
vector<int>::value_type x;
//x的数据类型是int
X u
vector<int> vec;
X()
vector<int>()
应用？？
X u(a)
vector<int> vec(tmp); //声明并用tmp向量初始化vec向量
X u=a
=上
r=a
....
vector<int> vec1(arr,arr+5);
vector<int>vec2;
vec2=vec1;
容器之间的赋值。
（&a）->~X();
vector<int> vec1;
( &vec1 )->vector<int>();
迭代器
a.begin()
a.end()
a.size()
a.swap()
vector<int> a;
...
vector<int> b:
....

a.swap(b);
//a,b容器交换
a==b
判断两个容器是否相等，是返回true
a！=b
判断两个容器是否不相等
C++11新增的容器要求
表格
  • 表16.6 C++11新增的基本容器要求,在这个表中,rv表示类型为X的非常量右值,如函数的返回值.//右值？有区别吗？
  • 表达式返回类型说明复杂度
    X u(rv);调用移动构造函数后,u的值与rv的原始值相同线性
    X u=rv;作用同Xu(rv);
    a=rv;X&调用移动赋值运算符后,u的值与rv的原始值相同线性
    a.cbegin()const_iterator返回指向容器第一个元素的const迭代器固定
    a.cendconst_iterator返回超尾值const迭代器固定
说明
移动构造、移动赋值函数（印象笔记中有）
复制构造和复制赋值以及移动构造移动赋值的区别在于:
复制操作保留源对象，
而移动操作可修改源对象（因此不能用const）,还可能转让所有权，不做任何复制。
如果源对象是临时的，移动操作的效率将高于常规复制。
复杂度
含义
描述执行操作所需要的时间
从快到慢
编译时间
操作将在编译时执行，执行时间为0
固定时间
操作发生在运行阶段，但独立于对象中的元素数目
例子
有一个装满礼物的狭长盒子，包裹一字排开。只打开一端。
从打开一端取出一个礼物，这是固定时间的任务。
无论打开一端后面有10个还是1000个礼物，都没有区别。
线性时间
时间与元素数目成正比
例子
有一个装满礼物的狭长盒子，包裹一字排开。只打开一端。
拿出最末尾的礼物，时间与拿出礼物的数目相关。
如果a和b都是容器,则a==b具有线性复杂度,因为==操作必须用于容器中的每个元素.
其他
  • 复杂度要求是STL特征,虽然实现细节可以隐藏,但性能规格应公开,以便程序员能够指导完成特定操作的计算成本.
种类
序列
概念
序列概念增加了迭代器至少是正向迭代器这样的要求,
这保证了元素将按特定顺序排列,不会在两次迭代之间发生变化.
要求元素按严格的线性顺序排列。数组、链表都是序列，分支结构（类似于树）不是。
种类
vector、deque、list、forward_list(C++11)、queue、priority_queue()、stack、array（C++11）
基本操作
其他一定要完成的操作
关联容器
种类
set、multiset、map、multimap
序列
vector
优点
vector是数组的一种类表示,它提供了自动内存管理功能,可以动态地改变vector对象的长度,
并随着元素的添加和删除而增大和缩小
.它提供了对元素的随机访问.
在尾部添加和删除元素的时间是固定的,但在头部或中间插入和删除元素的复杂度为线性时间.
除序列外,vector还是可反转容器reversible container概念的模型.
....
....
印象笔记中
关联容器
简介
特点
关键容器将值与键关联在一起，并使用键来查找值。
表达式 X::value_type指出了存储在容器中得值的类型。
X：：value_tyoe指出了键的类型。
优点
提供对元素的快速访问。
关联容器允许插入新的元素，但不能指定元素的插入位置。
关联容器有用于确定数据放置位置的算法，以便能够快速检索信息。
实现方式
某种树实现
类型
set、multiset、map、multimap
前两种头文件set.h,(以前分别  set.h和multiset,h )后两种map.h
函数对象
/函数符
内容
函数名、指向函数的指针、重载了（）运算符的类对象
重载了（）运算符的类对象
class Linear
{
private:
double slope;
double y0;
public:
Linear(double s1_=1,double y_=0)
:slope(s1_),y0(y_){}
double operator()(double x){ return y0+slope*x;}
}

Linear f1;
Linear f2(2.5,10.0);
double y1 = f1(12.5);
double y2 = f2(0.4);
分类
  • 生成器generator是不用参数就可以调用的函数符.
  • 一元函数unary function是用一个参数可以调用的函数符
  • 二元函数binary function是用两个参数可以调用的函数符.
  • 当然,这些概念都有相应的改进版: 
    • 返回bool值的一元函数是谓词
    • 返回bool值的二元函数是二元谓词
图像
将接受两个参数的模板函数，
转换为单个参数的函数对象
格式
template<class T>
bool toobig(const T&val,const T & lim)
{
return val>lim;
}
template<class T>
class TooBig2
{
private:
T cutoff;
public:
TooBig2(const T &t):cutoff(t){}
bool operator()(const T & v){return tooBig<T>(v,cutoff);}
};

yadayada.remove_if(f100);
yadayada.remove_if(TooBig<int>(200));

应用代码
代码
// functor.cpp -- using a functor
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

template<class T>  // functor class defines operator()()
class TooBig
{
private:
    T cutoff;
public:
    TooBig(const T & t) : cutoff(t) {}
    bool operator()(const T & v) { return v > cutoff; }
};

void outint(int n) {std::cout << n << " ";}

int main()
{
    using std::list;
    using std::cout;
    using std::endl;
using std::for_each;
using std::remove_if;

    TooBig<int> f100(100); // limit = 100
    int vals[10] = {50, 100, 90, 180, 60, 210, 415, 88, 188, 201};
    list<int> yadayada(vals, vals + 10); // range constructor
    list<int> etcetera(vals, vals + 10);
 
 // C++11 can use the following instead
//  list<int> yadayada = {50, 100, 90, 180, 60, 210, 415, 88, 188, 201};
//  list<int> etcetera {50, 100, 90, 180, 60, 210, 415, 88, 188, 201};

    cout << "Original lists:\n";
    for_each(yadayada.begin(), yadayada.end(), outint);
    cout << endl;
    for_each(etcetera.begin(), etcetera.end(), outint);
    cout << endl;
    yadayada.remove_if(f100);               // use a named function object
    etcetera.remove_if(TooBig<int>(200));   // construct a function object
    cout <<"Trimmed lists:\n";
    for_each(yadayada.begin(), yadayada.end(), outint);
    cout << endl;
    for_each(etcetera.begin(), etcetera.end(), outint);
    cout << endl;
    // std::cin.get();
    return 0;
}

结果：
Original lists:
50 100 90 180 60 210 415 88 188 201
50 100 90 180 60 210 415 88 188 201
Trimmed lists:
50 100 90 60 88
50 100 90 180 60 88 188
子主题
评论
0 条评论
下一页
为你推荐
查看更多
16_facedown
16_facedown
9种UML类图合集模板
9种UML类图合集模板
任职资格标准
任职资格标准
Style4Read类和导入列信息
Style4Read类和导入列信息
类图
类图
清新配色流程图标准样式模板
清新配色流程图标准样式模板
16-1
16-1
L16
L16
类图
类图
类图
类图