众所周知,C++ = C + STL

map

功能:

灵活的开桶容器,能够让各种类型的变量作为数组下标,空间要求较低,可以不离散化而开桶之类的

原理:

Map是基于树（红黑树）的实现方式，即添加到一个有序列表，在$\Theta(log\ n)$的复杂度内通过key值找到value,但是常数大.

头文件及定义

#include <map>
...
map<Typename1, Typename2> mp;

其中$Typename1$是第一关键字,$Typename2$是第二关键字,使用时相当于$mp[Typename1] = Typename2$

成员函数

/*定义*/
map<string, string> mp;
/*插入元素*/
mp.insert(pair<string, string>("Monday", "星期一"));
mp.insert(pair<string, string>("Tuesday", "星期二"));
/*删除元素*/
map<string, string>::iterator point;
point = mp.find("Tuesday");//使用迭代器删除
mp.erase(point);
mp.clear();mp.erase(mp.begin(), mp.end());//全部删除
/*查找并输出元素*/
point=mp.find("Monday");
if (point != mp.end())
    cout << point->first << " " << point->second;
/*其他操作*/
mp.count("Tuesday");//返回指定元素的出现次数
mp.empty();//判断是否为空
mp.size();//返回元素个数

set

功能

能够在插入元素时自动排序,同时set中没有重复的元素,能够进行高效查找.

原理

set同map一样是基于红黑树的,插入时间复杂度为$\Theta(log\ n)$,但是常数较大

头文件及定义

#include <set>
...
set<Typename> s;

成员函数

#include <set>
...
set<int> s;
/*插入元素*/
s.insert(514);
s.insert(1919);
s.insert(114);//这些数字插入后会自动排序
/*删除元素*/
s.erase(iterator);//删除迭代器指向的值
s.erase(l, r);//删除迭代器指定区间内部的值
s.erase(key);//删除键值为key的元素的值
/*查找元素*/
pair<set<int>::const_iterator, set<int>::const_iterator> point;
point = s.equal_range(514);//返回第一个>=给定值的元素位置和第一个>的元素位置.
cout << *point.first << " " << *point.second;
s.find(114);//返回给定值的迭代器,否则返回s.end()
s.lower_bound(514);//返回第一个大于等于给定值的迭代器
s.upper_bound(514);//返回最后一个大于等于给定值的迭代器
/*其他操作*/
s.begin();s.end();//返回首尾迭代器
s.empty();s.size();//判断是否为空和记录大小
s.clear();//清空set
s.count(1919);//返回出现次数(其实只有0或者1)
set<int, cmp> s;//支持比较函数

string

功能

string是功能强大的字符串容器,类似于C语言的char数组,但是又有所不同,可以支持大量的操作.

原理

相当于储存着字符的vector容器,其部分操作虽然复杂度相当于暴力,但是非常方便

头文件与定义

#include <string>
...
string s = "2333333";//直接赋值字符串
string t = s;//字符串间的赋值
string s(10, '6');//长度为10,每一个字符都是'6'
string t(s, 6);//把s的第6个字符到结尾拷贝到t中.
string t = string(s, 6);
string t(s, 0, 5);//把s从0开始的5个字符拷贝到t中
string s = string(str1, 0, 5);
char c[11] = "hello world";
string s(c, 6);//把c数组的前6个字符拷贝到s中
string s = string(c, 6);
string s = string("2333333", 5);//这里的"2333333"应该视为char数组,所以是拷贝前5个字符而不是第五个往后的字符

成员函数

/*字符串信息*/
s.size();s.length();//返回字符串的长度
s.substr(x);//返回字符串的x到结尾
s.substr(x, 10);//返回字符串下标为x处开始的10个字符
s.reverse(l, r);//翻转字符串中两个指针规定区间的字符
s.begin();s.end();//返回开头位置或者结尾位置的后一个位置
/*查找*/
s.find(t);//查找t在s中第一次出现的位置
s.find(t, l);//查找t在s的[l, end()]中第一次出现的位置
s.find(ch, l, n);//查找字符数组ch的前n个字符在s的[l, end]中第一次出现的位置
s.find(c, l);//查找字符c在s的[l, end()]中第一次出现的位置
//rfind系列可以进行反向操作
/*删除内容*/
s.erase(l, n);//将s中从l开始的n个字符删掉
/*赋值*/
s.assign(n,ch);//n个字符ch赋值给字符串s
s.assign(t);//将字符串t赋值给字符串s
s.assign(t, l, n);//将字符串t从l开始的n个字符赋值给字符串s
s.assaign(ch, n);//将字符数组ch的前n个字符赋值给字符串s
/*替换*/
s.replace(p, n, m, ch);//删除p开始的n个字符，然后在p处插入m个字符ch
s.replace(p, n, t);//删除从p开始的n个字符，然后在p处插入字符串t
s.replace(p, n, t, l, m);//删除p开始的n个字符，然后在p处插入字符串t中从l开始的m个字符
s.replace(p, n, ch, m);//删除p开始的n个字符，然后在p处插入字符数组ch的前m个字符
/*添加*/
s.append(n, c);//在当前串结尾添加n个字符c
s.append(t);//把字符串t接到当前串的结尾
s.append(t, l, n);//把字符串t中从l开始的n个字符连接到当前字符串的结尾
append(ch, n);//把字符数组ch的前n个字符连接到当前字符串结尾
/*插入*/
s.append(n, ch);//在当前字符串结尾添加n个字符c
s.append(t);//把字符串t连接到当前字符串的结尾
s.append(t, l, n);//把字符串t中从l开始的n个字符连接到当前串的结尾
append(ch, n);//把字符数组ch的前n个字符连接到当前串的结尾

——Gensokyo