Coursera Cpp程序设计 week 7

这周主要介绍SLT的内容。

课程地址:

coursera:C++程序设计

https://www.coursera.org/learn/cpp-chengxu-sheji

中国大学MOOC:程序设计与算法(三)C++面向对象程序设计

程序设计与算法(三)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’;

来看一个具体例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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()读取;

1
2
string s("hello");
cout << s.length() << endl;

string 支持流读取运算符

1
2
string stringObject;
cin >> stringObject;

string 支持getline函数

1
2
string s;
getline(cin ,s);
string 的赋值和连接

用 = 赋值

1
2
string s1("cat"), s2;
s2 = s1;

用 assign 成员函数复制

1
2
string s1("cat"), s3;
s3.assign(s1);

用 assign 成员函数部分复制

1
2
3
string s1("catpig"), s3;
s3.assign(s1, 1, 3);
//从s1 中下标为1的字符开始复制3个字符给s3

用at或者[]访问单个字符,其中at会检查下标是否越界

1
2
3
4
5
s2[5] = s1[3] = 'a';

string s1("Hello");
for(int i=0;i<s1.length();i++)
cout << s1.at(i) << endl;

可以用+以及append函数连接两个string,其中append函数可以连接部分字符:

1
2
3
4
5
6
string s1("good "), s2("morning! ");
s1.append(s2);
cout << s1;
s2.append(s1, 3, s1.size());//s1.size(),s1字符数
cout << s2;
// 下标为3开始,s1.size()个字符,如果字符串内没有足够字符,则复制到字符串最后一个字符
1
2
3
string s1("good "), s2("morning! ");
s1 += s2;
cout << s1;
比较string

可以用== , >, >=, <, <=, !=比较两个string,返回类型都是bool型,大于小于符号根据字典序比较:

1
2
3
4
5
6
7
8
9
10
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函数可以比较部分字符串的大小:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
string s1("hello world"), s2;
s2 = s1.substr(4,5); // 下标4开始5个字符
cout << s2 << endl;

//输出:
//o wor
交换string

成员函数 swap

1
2
3
4
5
6
7
8
string s1("hello world"), s2("really");
s1.swap(s2);
cout << s1 << endl;
cout << s2 << endl;

//输出:
//really
//hello world
寻找string中的字符

成员函数 find()

1
2
string s1("hello world");
s1.find("lo");

在s1中从前向后查找 “lo” 第一次出现的地方,如果找到,返回 “lo”开始的位置,即 l 所在的位置下标。如果找不到,返回string::npos (string中定义的静态常量)

成员函数 rfind()

1
2
string s1("hello world");
s1.rfind("lo");

在s1中从后向前查找 “lo” 第一次出现的地方,如果找到,返回 “lo”开始的位置,即 l 所在的位置下标。如果找不到,返回string::npos 。

成员函数 find_first_of()

1
2
string s1("hello world");
s1.find_first_of(“abcd");

在s1中从前向后查找 “abcd” 中任何一个字符第一次出现的地方,如果找到,返回找到字母的位置,如果找不到,返回string::npos。

成员函数 find_last_of()

1
2
string s1("hello world");
s1.find_last_of("abcd");

在s1中查找 “abcd” 中任何一个字符最后一次出现的地方,如果找到,返回找到字母的位置,如果找不到,返回
string::npos。

成员函数 find_first_not_of()

1
2
string s1("hello world");
s1.find_first_not_of("abcd");

在s1中从前向后查找不在 “abcd” 中的字母第一次出现的地方,如果找到,返回找到字母的位置,如果找不到,返回string::npos。

成员函数 find_last_not_of()

1
2
string s1("hello world");
s1.find_last_not_of("abcd");

在s1中从后向前查找不在 “abcd” 中的字母第一次出现的地方,如果找到,返回找到字母的位置,如果找不到,返回string::npos。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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()

1
2
3
4
5
6
7
8
9
string s1("hello worlld");
s1.erase(5);
cout << s1;
cout << s1.length();
cout << s1.size();

// 去掉下标 5 及之后的字符
//输出:
//hello55
替换string中的字符

成员函数 replace()

1
2
3
4
5
6
7
8
string s1("hello world");
s1.replace(2,3, "haha", 1,2);
cout << s1;

// 将s1中下标2 开始的3个字符换成“haha” 中下标1开始的2个字符

//输出:
//heah world
在string中插入字符

成员函数insert()

1
2
3
4
5
6
7
8
9
10
11
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()

1
2
3
4
5
6
string s1("hello world");
printf("%s\n", s1.c_str());
// s1.c_str() 返回传统的const char * 类型字符串,且该字符串以‘\0’结尾。

//输出:
//hello world

成员函数data()

1
2
3
4
5
6
7
8
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()

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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

1
2
3
4
5
6
7
8
9
10
11
12
#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 变量名;

访问一个迭代器指向的元素:

  • *迭代器变量名

来看一个具体例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。

来看两个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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: 在指定位置前面插入另一链表中的一个或多个元素,并在另
    一链表中删除被插入的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;
}

函数对象

函数对象是个对象,但是用起来看上去象函数调用,实际上也执行了函数调用。

1
2
3
4
5
6
7
8
9
10
11
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