Coursera Cpp程序设计 week 7
这周主要介绍SLT的内容。
课程地址：
coursera：C++程序设计
https://www.coursera.org/learn/cpp-chengxu-sheji
中国大学MOOC：程序设计与算法（三）C++面向对象程序设计
string类
基本使用
- string 类是模板类：typedef basic_string char string;
- 使用string类要包含头文件string
- string对象的初始化：
- string s1(“Hello”);
- string month = “March”;
- string s2(8,’x’);
- 错误的初始化方法：
- string error1 = ‘c’; // 错
- string error2(‘u’); // 错
- string error3 = 22; // 错
- string error4(8); // 错
- 可以将字符赋值给string对象
- string s;
- s = ‘n’;
来看一个具体例子：
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[ ]){
string s1("Hello");
cout << s1 << endl;
string s2(8,'x');
cout << s2 << endl;
string month = "March";
cout << month << endl;
string s;
s='n';
cout << s << endl;
return 0;
}
/*
输出：
Hello
xxxxxxxx
March
n
*/string 对象的长度用成员函数 length()读取；
string s("hello");
cout << s.length() << endl;string 支持流读取运算符
string stringObject;
cin >> stringObject;string 支持getline函数
string s;
getline(cin ,s);string 的赋值和连接
用 = 赋值
string s1("cat"), s2;
s2 = s1;用 assign 成员函数复制
string s1("cat"), s3;
s3.assign(s1);用 assign 成员函数部分复制
string s1("catpig"), s3;
s3.assign(s1, 1, 3);
//从s1 中下标为1的字符开始复制3个字符给s3 用at或者[]访问单个字符，其中at会检查下标是否越界
s2[5] = s1[3] = 'a';
string s1("Hello");
for(int i=0;i<s1.length();i++)
cout << s1.at(i) << endl;可以用+以及append函数连接两个string，其中append函数可以连接部分字符：
string s1("good "), s2("morning! ");
s1.append(s2);
cout << s1;
s2.append(s1, 3, s1.size());//s1.size()，s1字符数
cout << s2;
// 下标为3开始，s1.size()个字符，如果字符串内没有足够字符，则复制到字符串最后一个字符string s1("good "), s2("morning! ");
s1 += s2;
cout << s1;比较string
可以用== , >, >=, <, <=, !=比较两个string，返回类型都是bool型，大于小于符号根据字典序比较：
string s1("hello"),s2("hello"),s3("hell");
bool b = (s1 == s2);
cout << b << endl;
b = (s1 == s3);
cout << b << endl;
b = (s1 > s3);
cout << b << endl;
//输出：
//1 0 1还可以用compare比较string的大小，compare函数可以比较部分字符串的大小：
string s1("hello"),s2("hello"),s3("hell");
int f1 = s1.compare(s2);
int f2 = s1.compare(s3);
int f3 = s3.compare(s1);
int f4 = s1.compare(1,2,s3,0,3); //s1 1-2; s3 0-3
int f5 = s1.compare(0,s1.size(),s3);//s1 0-end
cout << f1 << endl << f2 << endl << f3 << endl;
cout << f4 << endl << f5 << endl;
/***
输出
0 // hello == hello
1 // hello > hell
-1 // hell < hello
-1 // el < hell
1 // hello > hell
***/子串
成员函数 substr
string s1("hello world"), s2;
s2 = s1.substr(4,5); // 下标4开始5个字符
cout << s2 << endl;
//输出：
//o wor交换string
成员函数 swap
string s1("hello world"), s2("really");
s1.swap(s2);
cout << s1 << endl;
cout << s2 << endl;
//输出：
//really
//hello world 寻找string中的字符
成员函数 find()
string s1("hello world");
s1.find("lo");在s1中从前向后查找 “lo” 第一次出现的地方，如果找到，返回 “lo”开始的位置，即 l 所在的位置下标。如果找不到，返回string::npos （string中定义的静态常量）
成员函数 rfind()
string s1("hello world");
s1.rfind("lo");在s1中从后向前查找 “lo” 第一次出现的地方，如果找到，返回 “lo”开始的位置，即 l 所在的位置下标。如果找不到，返回string::npos 。
成员函数 find_first_of()
string s1("hello world");
s1.find_first_of(“abcd");在s1中从前向后查找 “abcd” 中任何一个字符第一次出现的地方，如果找到，返回找到字母的位置，如果找不到，返回string::npos。
成员函数 find_last_of()
string s1("hello world");
s1.find_last_of("abcd"); 在s1中查找 “abcd” 中任何一个字符最后一次出现的地方，如果找到，返回找到字母的位置，如果找不到，返回
string::npos。
成员函数 find_first_not_of()
string s1("hello world");
s1.find_first_not_of("abcd");在s1中从前向后查找不在 “abcd” 中的字母第一次出现的地方，如果找到，返回找到字母的位置，如果找不到，返回string::npos。
成员函数 find_last_not_of()
string s1("hello world");
s1.find_last_not_of("abcd");在s1中从后向前查找不在 “abcd” 中的字母第一次出现的地方，如果找到，返回找到字母的位置，如果找不到，返回string::npos。
string s1("hello worlld");
cout << s1.find("ll") << endl;
cout << s1.find("abc") << endl;
cout << s1.rfind("ll") << endl;
cout << s1.rfind("abc") << endl;
cout << s1.find_first_of("abcde") << endl;
cout << s1.find_first_of("abc") << endl;
cout << s1.find_last_of("abcde") << endl;
cout << s1.find_last_of("abc") << endl;
cout << s1.find_first_not_of("abcde") << endl;
cout << s1.find_first_not_of("hello world") << endl;
cout << s1.find_last_not_of("abcde") << endl;
cout << s1.find_last_not_of("hello world") << endl;
/***
输出：
2
4294967295
9
4294967295
1
4294967295
11
4294967295
0
4294967295
10
4294967295
***/删除string中的字符
成员函数erase()
string s1("hello worlld");
s1.erase(5);
cout << s1;
cout << s1.length();
cout << s1.size();
// 去掉下标 5 及之后的字符
//输出：
//hello55替换string中的字符
成员函数 replace()
string s1("hello world");
s1.replace(2,3, "haha", 1,2);
cout << s1;
// 将s1中下标2 开始的3个字符换成“haha” 中下标1开始的2个字符
//输出：
//heah world在string中插入字符
成员函数insert()
string s1("hello world");
string s2(“show insert");
s1.insert(5,s2); // 将s2插入s1下标5的位置
cout << s1 << endl;
s1.insert(2,s2,5,3);
//将s2中下标5开始的3个字符插入s1下标2的位置
cout << s1 << endl;
//输出：
//helloshow insert world
//heinslloshow insert world 转换成C语言式char *字符串
成员函数 c_str()
string s1("hello world");
printf("%s\n", s1.c_str());
// s1.c_str() 返回传统的const char * 类型字符串，且该字符串以‘\0’结尾。
//输出：
//hello world 成员函数data()
string s1("hello world");
const char * p1=s1.data();
for(int i=0;i<s1.length();i++)
printf("%c",*(p1+i));
//s1.data() 返回一个char * 类型的字符串，对s1 的修改可能会使p1出错。
//输出：
//hello world字符串拷贝
成员函数copy()
string s1("hello world");
int len = s1.length();
char * p2 = new char[len+1];
s1.copy(p2,5,0);
p2[5]=0;
cout << p2 << endl;
// s1.copy(p2,5,0) 从s1的下标0的字符开始制作一个最长5个字符长度的字符串副本并将其赋值给p2。返回值表明实际复制字符串的长度。
//输出：
//hello 字符串流处理
除了标准流和文件流输入输出外，还可以从string进行输入输出；类似 istream和osteram进行标准流输入输出，我们用
istringstream 和 ostringstream进行字符串上的输入输出，也称为内存输入输出。
字符串输入流 istringstream
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
string input("Input test 123 4.7 A");
istringstream inputString(input);
string string1, string2;
int i;
double d;
char c;
inputString >> string1 >> string2 >> i >> d >> c;
cout << string1 << endl << string2 << endl;
cout << i << endl << d << endl << c <<endl;
long L;
if(inputString >> L) cout << "long\n";
else cout << "empty\n";
/***
输出：
Input
test
123
4.7
A
empty
***/字符串输出流ostringstream
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
ostringstream outputString;
int a = 10;
outputString << "This " << a << "ok" << endl;
cout << outputString.str();
//输出：
//This 10ok容器概述
可以用于存放各种类型的数据（基本类型的变量，对象等）的数据结构，都是类模版,分为三种：
- 1)顺序容器
vector, deque,list - 2)关联容器
set, multiset, map, multimap - 3)容器适配器
stack, queue, priority_queue
对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符。
顺序容器
容器并非排序的，元素的插入位置同元素的值无关。有vector,deque,list 三种
vector 头文件 vector
动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。
deque 头文件 deque
双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间）。
list 头文件 list
双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。 不支持随机存取。
关联容器
- 元素是排序的
- 插入任何元素，都按相应的排序规则来确定其位置
- 在查找时具有非常好的性能
- 通常以平衡二叉树方式实现，插入和检索的时间都是 O(log(N))
set/multiset 头文件set
set 即集合。 set中不允许相同元素，multiset中允许存在相同的元素。
map/multimap 头文件map
map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first,另一个名为second, map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。map同multimap的不同在于是否允许相同first值的元素。
容器适配器
stack :头文件stack
栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。
queue 头文件queue
队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。
priority_queue 头文件queue
优先级队列。最高优先级元素总是第一个出列。
顺序容器和关联容器中都有的成员函数
- begin 返回指向容器中第一个元素的迭代器
- end 返回指向容器中最后一个元素后面的位置的迭代器
- rbegin 返回指向容器中最后一个元素的迭代器
- rend 返回指向容器中第一个元素前面的位置的迭代器
- erase 从容器中删除一个或几个元素
- clear 从容器中删除所有元素
顺序容器和关联容器中都有的成员函数
- front :返回容器中第一个元素的引用
- back : 返回容器中最后一个元素的引用
- push_back : 在容器末尾增加新元素
- pop_back : 删除容器末尾的元素
- erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器
顺序容器的常用成员函数
迭代器
迭代器用于指向顺序容器和关联容器中的元素，用法和指针类似，有const 和非const两种，通过迭代器可以读取它指向的元素，通过非const迭代器还能修改其指向的元素。
定义一个容器类的迭代器的方法可以是：
- 容器类名::iterator 变量名;
- 容器类名::const_iterator 变量名;
访问一个迭代器指向的元素：
- *迭代器变量名
来看一个具体例子：
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v; //一个存放int元素的数组，一开始里面没有元素
v.push_back(1); v.push_back(2); v.push_back(3);
v.push_back(4);
vector<int>::const_iterator i; //常量迭代器
for( i = v.begin();i != v.end();++i )
cout << * i << ",";
cout << endl;
vector<int>::reverse_iterator r; //反向迭代
for( r = v.rbegin();r != v.rend();r++ )
cout << * r << ",";
cout << endl;
vector<int>::iterator j; //非常量迭代器
for( j = v.begin();j != v.end();j ++ )
* j = 100;
for( i = v.begin();i != v.end();i++ )
cout << * i << ",";
}
/***
输出结果：
1,2,3,4,
4,3,2,1,
100,100,100,10
0,
***/随机访问迭代器
若p和p1都是随机访问迭代器，则可对p、 p1可进行以下操作：
- 双向迭代器的所有操作
- p += i 将p向后移动i个元素
- p -= i 将p向向前移动i个元素
- p + i 值为: 指向 p 后面的第i个元素的迭代器
- p - i 值为: 指向 p 前面的第i个元素的迭代器
- p[i] 值为: p后面的第i个元素的引用
- p < p1, p <= p1, p > p1, p>= p1
- p – p1 : p1和p之间的元素个数
来看下常用容器的迭代器类型：
| 容器 | 容器上的迭代器类别 |
|---|---|
| vector | 随机访问 |
| deque | 随机访问 |
| list | 双向 |
| set/multiset | 双向 |
| map/multimap | 双向 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| priority_queue | 不支持迭代器 |
后续部分详细介绍各种容器
vector和deque
vector是动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）。
deque是双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间）。
来看两个例子：
#include <iostream>
#include <vector>
using namespace std;
template<class T>
void PrintVector( T s, T e)
{
for(; s != e; ++s)
cout << * s << " ";
cout << endl;
}
int main() {
int a[5] = { 1,2,3,4,5 };
vector<int> v(a,a+5); //将数组a的内容放入v
cout << "1) " << v.end() - v.begin() << endl;
//两个随机迭代器可以相减，输出 1) 5
cout << "2) "; PrintVector(v.begin(),v.end());
//2) 1 2 3 4 5
v.insert(v.begin() + 2, 13); //在begin()+2位置插入 13
cout << "3) "; PrintVector(v.begin(),v.end());
//3) 1 2 13 3 4 5
v.erase(v.begin() + 2); //删除位于 begin() + 2的元素
cout << "4) "; PrintVector(v.begin(),v.end());
//4) 1 2 3 4 5
vector<int> v2(4,100); //v2 有4个元素，都是100
v2.insert(v2.begin(),v.begin()+ 1,v.begin()+3);
//将v的一段插入v2开头
cout << "5) v2: "; PrintVector(v2.begin(),v2.end());
//5) v2: 2 3 100 100 100 100
v.erase(v.begin() + 1, v.begin() + 3);
//删除 v 上的一个区间,即 2,3
cout << "6) "; PrintVector(v.begin(),v.end());
//6) 1 4 5
return 0;
}所有适用于 vector的操作都适用于 deque，此外deque还有 push_front（将元素插入到前面）和pop_front(删除最前面的元素）操作，复杂度是O(1)
双向链表list
在任何位置插入删除都是常数时间，不支持随机存取。
除了具有所有顺序容器都有的成员函数以外，还支持8个成员函数：
- push_front: 在前面插入
- pop_front: 删除前面的元素
- sort: 排序 ( list 不支持 STL 的算法 sort)
- remove: 删除和指定值相等的所有元素
- unique: 删除所有和前一个元素相同的元素(要做到元素不重复，则unique之前还需要 sort)
- merge: 合并两个链表，并清空被合并的那个
- reverse: 颠倒链表
- splice: 在指定位置前面插入另一链表中的一个或多个元素,并在另
一链表中删除被插入的元素
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
class A {
private:
int n;
public:
A( int n_ ) { n = n_; }
friend bool operator<( const A & a1, const A & a2);
friend bool operator==( const A & a1, const A & a2);
friend ostream & operator <<( ostream & o, const A & a);
};
bool operator<( const A & a1, const A & a2) {
return a1.n < a2.n;
}
bool operator==( const A & a1, const A & a2) {
return a1.n == a2.n;
}
ostream & operator <<( ostream & o, const A & a) {
o << a.n;
return o;
}
template <class T>
void PrintList(const list<T> & lst) {
//不推荐的写法，还是用两个迭代器作为参数更好
int tmp = lst.size();
if( tmp > 0 ) {
typename list<T>::const_iterator i;
i = lst.begin();
for( i = lst.begin();i != lst.end(); i ++)
cout << * i << ",";
}
}// typename用来说明 list<T>::const_iterator是个类型
//在vs中不写也可以
int main() {
list<A> lst1,lst2;
lst1.push_back(1);lst1.push_back(3);
lst1.push_back(2);lst1.push_back(4);
lst1.push_back(2);
lst2.push_back(10);lst2.push_front(20);
lst2.push_back(30);lst2.push_back(30);
lst2.push_back(30);lst2.push_front(40);
lst2.push_back(40);
cout << "1) "; PrintList( lst1); cout << endl;
// 1) 1,3,2,4,2,
cout << "2) "; PrintList( lst2); cout << endl;
// 2) 40,20,10,30,30,30,40,
lst2.sort();
cout << "3) "; PrintList( lst2); cout << endl;
//3) 10,20,30,30,30,40,40,
lst2.pop_front();
cout << "4) "; PrintList( lst2); cout << endl;
//4) 20,30,30,30,40,40,
lst1.remove(2); //删除所有和A(2)相等的元素
cout << "5) "; PrintList( lst1); cout << endl;
//5) 1,3,4,
lst2.unique(); //删除所有和前一个元素相等的元素
cout << "6) "; PrintList( lst2); cout << endl;
//6) 20,30,40,
lst1.merge (lst2); //合并 lst2到lst1并清空lst2
cout << "7) "; PrintList( lst1); cout << endl;
//7) 1,3,4,20,30,40,
cout << "8) "; PrintList( lst2); cout << endl;
//8)
lst1.reverse();
cout << "9) "; PrintList( lst1); cout << endl;
//9) 40,30,20,4,3,1,
lst2.push_back (100);lst2.push_back (200);
lst2.push_back (300);lst2.push_back (400);
list<A>::iterator p1,p2,p3;
p1 = find(lst1.begin(),lst1.end(),3);
p2 = find(lst2.begin(),lst2.end(),200);
p3 = find(lst2.begin(),lst2.end(),400);
lst1.splice(p1,lst2,p2, p3);
//将[p2,p3)插入p1之前，并从lst2中删除[p2,p3)
cout << "10) "; PrintList( lst1); cout << endl;
//10) 40,30,20,4,200,300,3,1,
cout << "11) "; PrintList( lst2); cout << endl;
//11) 100,400,
return 0;
}函数对象
函数对象是个对象，但是用起来看上去象函数调用，实际上也执行了函数调用。
class CMyAverage {
public:
double operator()( int a1, int a2, int a3 ) {
//重载 () 运算符
return (double)(a1 + a2+a3) / 3;
}
};
CMyAverage average; //函数对象
cout << average(3,2,3); // average.operator()(3,2,3) 用起来看
上去象函数调用 输出 2.66667