前言

由于开学在即，竞赛也不远了，可我的算法却没学多少，所以我打算先整理STL

string 类

string 类是模板类，可以当作char的替代品，使用string类要包含头文件< string >

string对象的三种初始化方式：

1
2
3
string s1("Hello"); 
string month = "March"; //要以字符串的形势初始化
string s2(8,’x’);

可以将字符赋给string对象：

1
2
string s;
s = ‘n’;

string类可以用getline读入：

1
getline(cin,str);

string的赋值,连接与比较

• 用 = 赋值

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

• 用 assign 成员函数复制

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

• 用 assign 成员函数部分复制

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

• 单个字符复制

1
s2[5] = s1[3] = ‘a’;

• 逐个访问string对象中的字符

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

成员函数at会做范围检查，如果超出范围，会抛出 out_of_range异常，而下标运算符[]不做范围检查。

• 用 + 运算符连接字符串

1
2
3
string s1("good "), s2("morning! ");
s1 += s2;
cout << s1;

• 用成员函数 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()个字符，如果字符串内没有足够字符，则复制到字符串最后一个字符

• 用关系运算符比较string的大小

== , >, >=, <, <=, !=

返回值都是bool类型，成立返回true, 否则返回false

1
2
3
4
5
6
7
string s1("hello"),s2("hello"),s3("hell");
bool b = (s1 == s2); 
cout << b << endl;//1
b = (s1 == s3); //0
cout << b << endl;
b = (s1 > s3); //1
cout << b << endl;

• 用成员函数compare比较string的大小

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

string 类的成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
str.assign()//起复制作用，上文已提到
str.at()//起访问的作用，上文已提到
str.compare()//起比较的作用，上文已提到
str.length()//返回字符串长度
str.size()//返回字符串长度，和上面一样
str.substr()//返回指定范围的子串
str.swap()//交换字符串
/*以下带有find的成员函数在找不到时都会返回string::npos*/
str.find_first_of()//从前向后找字符串中任何一个字符第一次出现的地方
str.find_last_of()//从后往前找字符串中任何一个字符第一次出现的地方
str.find_first_not_of()//从前向后找非字符串中任何一个字符的第一个字符
str.find_last_not_of()//从后往前找非字符串中任何一个字符的第一个字符
str.find()//返回找到的字符串的首字母位置，rfind()则是从后往前找
str.erase()//删除指定范围的字符串
str.replace()//替换指定范围的字符串
str.insert()//在指定位置插入字符串
str.c_str()//转换成C语言式const char *字符串
str.data()//转换成C语言式char *字符串，不安全
str.copy()//拷贝指定范围的字符串

STL标准模板库

STL中的基本的概念

容器：可容纳各种数据类型的通用数据结构,是类模板

迭代器：可用于依次存取容器中元素，类似于指针

算法：用来操作容器中的元素的函数模板

通俗理解：

1
2
int array[100]; 
sort(array,array+70); //将前70个元素排序

该数组就是容器，而 int * 类型的指针变量就可以作为迭代器，sort算法可以作用于该容器上，对其进行排序

容器分为三种：

1)顺序容器 vector, deque(双向队列), list(链表)

2)关联容器 set, multiset, map, multimap

3)容器适配器 stack(栈), queue(队列), priority_queue(优先队列)

对象被插入容器中时，被插入的是对象的一个复制品。许多算法，比如排序，查找，要求对容器中的元 素进行比较，有的容器本身就是排序的，所以，放入容器的对象所属的类，往往还应该重载 == 和 < 运算符

顺序容器

vector

动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间）

deque

双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)

list

双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取

关联容器

• 元素是排序的

• 插入任何元素，都按相应的排序规则来确定其位置

• 在查找时具有非常好的性能

• 通常以平衡二叉树方式实现，插入和检索的时间都是 O(log(N))

set/multiset

set 即集合。set中不允许相同元素，multiset中允许存在相同的元素

map/multimap

map与set的不同在于map中存放的元素有且仅有两个成员变量，一个名为first(表示关键字),另一个名为second(表示值), map根据first值对元素进行从小到大排序，并可快速地根据first来检索元素。

map同multimap的不同在于是否允许相同first值的元素。

容器适配器

stack

栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项（栈顶的项）。后进先出。

queue

队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。先进先出。

priority_queue

优先级队列。最高优先级(自己定义)元素总是第一个出列

顺序容器和关联容器中都有的成员函数

begin 返回指向容器中第一个元素的迭代器

end 返回指向容器中最后一个元素后面的位置的迭代器

rbegin 返回指向容器中最后一个元素的迭代器

rend 返回指向容器中第一个元素前面的位置的迭代器

erase 从容器中删除一个或几个元素

clear 从容器中删除所有元素

顺序容器的常用成员函数

front :返回容器中第一个元素的引用

back : 返回容器中最后一个元素的引用

push_back : 在容器末尾增加新元素

pop_back : 删除容器末尾的元素

erase :删除迭代器指向的元素(可能会使该迭代器失效），或删除一个区间，返回被删除元素后面的那个元素的迭代器