STL笔记
注意：
所有不支持随机访问迭代器的容器，不可以用标准算法
string容器
本质上是一个类，内部封装了char*管理这个字符串，是一个char*型的容器。（char*是一个指针）
string管理char*所分配的内存，不用担心复制越界和取值越界等问题
内部成员方法：
| 操作 | 方法名 |
|---|---|
| 查找 | find |
| 拷贝 | copy |
| 删除 | delete |
| 替换 | replace |
| 插入 | insert |
构造原型：
| 原型 | 解释 |
|---|---|
| string(); | 创建一个空的字符串，例如：string str |
| string(const char* s); | 使用字符串s初始化 |
| string(const string& str); | 使用一个string对象初始化另一个string对象 |
| string(int n,char c); | 使用n个字符c初始化 |
赋值操作：
| 原型 | 解释 |
|---|---|
| string& operator=(const char* s); | char*类型字符串赋值给当前的字符串 |
| string& operator=(const string &s); | 把字符串s赋值给当前的字符串 |
| string& operator=(char c); | 字符c赋值给当前的字符串 |
| string& assign(const char* s); | 把字符串s赋值给当前的字符串 |
| string& assign(const char* s,int n); | 把字符串s的前n个字符赋值给当前的字符串 |
| string& assign(const string &s); | 把字符串s赋值给当前的字符串 |
| string& assign(int n,char c); | 把n个字符赋值给当前的字符串 |
拼接操作：
| 原型 | 解释 |
|---|---|
| string& operator+=(const char* str); | 字符串str拼接到末尾 |
| string& operator+=(const char c); | 字符c拼接到末尾 |
| string& operator+=(const string& str); | 字符串str拼接到末尾 |
| string& assign(const char* s); | 把字符串s拼接到末尾 |
| string& assign(const char* s,int n); | 把字符串s的前n个字符拼接到末尾 |
| string& assign(const string &s); | 同operator+=(const string& str) |
| string& assign(const string &s,int pos,int n); | 字符串s从pos开始的n个字符连接到字符串结尾 |
查找操作：
find从左往右查，rfind从右往左查
| 原型 | 解释 |
|---|---|
| int find(const string& str, int pos = 0) const; | 查找str第一次出现的位置，从pos开始查找 |
| int find(const char* s, int pos = 0) const; | 查找s第一次出现的位置，从pos开始查找 |
| int find(const char* s, int pos, int n) const; | 从pos位置查找s的前n个字符第一次出现的位置 |
| int find(const char c, int pos = 0) const; | 查找字符c第一次出现的位置 |
| int rfind(const string& str, int pos = npos) const; | 查找str最后一次出现的位置，从pos开始查找 |
| int rfind(const char* s, int pos = npos) const; | 查找s最后一次出现的位置，从pos开始查找 |
| int rfind(const char* s, int pos ,int n) const; | 从pos查找s的前n个字符最后一次出现的位置 |
| int rfind(const char c, int pos = 0) const; | 查找字符c最后一次出现位置 |
| string& replace(int pos, int n ,const string& str); | 替换从pos开始n个字符为字符串str |
| string& replace(int pos, int n ,const char* s); | 替换从pos开始n个字符为字符串s |
比较操作：
字符串比较会逐字符比较ASCII码，比较值为：
= 返回 0
> 返回 1
< 返回 -1
| 原型 | 解释 |
|---|---|
| int compare(const string& s) const; | 与字符串s比较 |
| int compare(const char* s) const; | 与字符串s比较 |
字符存取操作：
| 原型 | 解释 |
|---|---|
| char& operator[](int n); | 通过[]方式取字符 |
| char& at(int n); | 通过at方法获取字符 |
插入和删除：
| 原型 | 解释 |
|---|---|
| string& insert(int pos, const char* s); | 插入字符串 |
| string& insert(int pos, const string& str); | 插入字符串 |
| string& insert(int pos, int n, char c); | 在指定位置插入n个字符c |
| string& erase(int pos, int n = npos); | 删除从pos开始的n个字符 |
子串：
| 原型 | 解释 |
|---|---|
| string substr(int pos = 0,int n = npos) const; | 返回由pos开始的n个字符组成的字符串 |
vector容器
vector数据结构和数组非常相似，也称为单端数组。不同之处在于数组是静态空间，而vector可以动态扩展。扩展时会新找一片更大的存储空间，然后将原数据拷贝到新空间，并释放原空间。
构造原型：
| 原型 | 解释 |
|---|---|
| vector<T> v; | 采用模板实现类实现，默认构造函数 |
| vector<T> v1(v.begin(),v.end()); | 将v[begin(),end())区间中的元素拷贝给本身 |
| vector(n,elem); | 构造函数将n个elem拷贝给本身 |
| vector(const vector& vec); | 拷贝构造函数 |
赋值操作：
| 原型 | 解释 |
|---|---|
| vector& operator=(const vector& vec); | 重载等号操作符 |
| assign(beg, end); | 将[beg,end)区间中的数据拷贝赋值给本身 |
| assign(n,elem); | 将n个elem拷贝赋值给本身 |
vector容量和大小：
| 原型 | 解释 |
|---|---|
| empty(); | 判断容器是否为空 |
| capacity(); | 容器的容量 |
| size(); | 返回容器中元素的个数 |
| resize(int num); | 重新指定容器的长度为num,若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
| resize(int num,elem); | 重新指定容器的长度为num,若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
vector插入和删除：
| 原型 | 解释 |
|---|---|
| push_back(ele); | 尾部插入元素ele |
| pop_back(); | 删除最后一个元素 |
| insert(const_iterator pos, ele); | 迭代器指向位置pos插入元素ele |
| insert(const_iterator pos, int count,ele); | 迭代器指向位置pos插入count个元素ele |
| erase(const_iterator pos); | 删除迭代器指向的元素 |
| erase(const_iterator start, const_iterator end); | 删除迭代器从start到end之间的元素 |
| clear(); | 删除容器中所有元素 |
vector数据存取：
| 原型 | 解释 |
|---|---|
| at(int idx); | 返回索引idx所指的数据 |
| operator[]; | 返回索引idx所指的数据 |
| front(); | 返回容器中第一个数据元素 |
| back(); | 返回容器中最后一个数据元素 |
vector互换容器：
swap可以互换两个vector，达到实用的收缩内存的效果
| 原型 | 解释 |
|---|---|
| swap(vec); | 将vec与本身的元素互换 |
vector预留空间：
减少vector在动态扩展容量时的扩展次数
| 原型 | 解释 |
|---|---|
| reserve(int len); | 容量预留len个元素长度，预留位置不初始化，元素不可访问 |
deque容器
双端数组，头尾皆可进行增删操作。与vector的区别是：
vector对于头部的插入删除效率低，数据量越大，效率越低
deque相对而言，头操作比vector快
vector开辟的是一片连续的空间，所以访问元素时的速度会比deque快。deque则是由中控器负责记录开辟的地址，实际的地址中存放数据，中控器记录这些地址值。
构造原型：
| 原型 | 解释 |
|---|---|
| deque<T> deqT; | 默认构造形式 |
| deque(beg,end); | 构造函数将[beg, end)区间中的元素拷贝给本身 |
| deque(n,elem); | 构造函数将n个elem拷贝给本身 |
| deque(const deque& deq); | 拷贝构造函数 |
// 限制迭代器的参数为只读状态时要写成下面这样
void printDeque(const deque<int>& d){ // 这里的参数要用const修饰
for(deque<int>::const_iterator it = d.begin();it != d.end(); it++){
// 上面的迭代器使用了const_iterator
//...
}
}deque赋值
| 原型 | 解释 |
|---|---|
| deque& operator=(const deque& deq); | 重载等号操作符 |
| assign(beg, end); | 将[beg,end)区间中的数据拷贝赋值给本身 |
| assign(n,elem); | 将n个elem拷贝赋值给本身 |
deque容量和大小：
| 原型 | 解释 |
|---|---|
| empty(); | 判断容器是否为空 |
| size(); | 返回容器中元素的个数 |
| resize(int num); | 重新指定容器的长度为num,若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
| resize(int num,elem); | 重新指定容器的长度为num,若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
deque插入和删除：
两端插入操作：
| 原型 | 解释 |
|---|---|
| push_back(elem); | 在容器尾部添加一个数据 |
| push_front(elem); | 在容器头部添加一个数据 |
| pop_back(elem); | 删除容器最后一个数据 |
| pop_front(elem); | 删除容器第一个数据 |
指定位置操作：
| 原型 | 解释 |
|---|---|
| insert(pos,elem); | 在pos位置插入一个elem元素的拷贝，返回新数据的位置 |
| insert(pos,n,elem); | 在pos位置插入n个elem数据，无返回值 |
| insert(pos,beg,end); | 在pos位置插入[beg,end)区间的数据，无返回值 |
| clear(); | 清空容器所有的数据 |
| erase(beg,end); | 删除[beg,end)区间的数据，返回下一个数据的位置 |
| erase(pos); | 删除pos位置的数据，返回下一个数据的位置 |
deque数据存取：
| 原型 | 解释 |
|---|---|
| at(int idx); | 返回索引idx所指的数据 |
| operator[]; | 返回索引idx所指的数据 |
| front(); | 返回容器中第一个数据元素 |
| back(); | 返回容器中最后一个数据元素 |
deque排序
| 原型 | 解释 |
|---|---|
| sort(iterator beg,iterator end); | 对beg和end区间内元素进行排序 |
stack容器
stack是一种先进后出的数据结构（即栈结构）。由于只有栈顶元素可以被访问，所以栈不支持遍历。
构造函数
| 原型 | 解释 |
|---|---|
| stack<T> stk; | stack采用模板类实现，stack对象的默认构造形式 |
| stack(const stack& stk); | 拷贝构造函数 |
赋值操作
| 原型 | 解释 |
|---|---|
| stack& operator=(const stack& stk); | 重载等号操作 |
数据存取
| 原型 | 解释 |
|---|---|
| push(elem); | 向栈顶添加元素 |
| pop(); | 从栈顶移除第一个元素 |
| top(); | 返回栈顶元素 |
大小操作
| 原型 | 解释 |
|---|---|
| empty(); | 判断堆栈是否为空 |
| size(); | 返回栈的大小 |
queue容器
先进先出的数据结构，有两个出口，允许一端新增，另一端移除。由于只有队头和队尾的元素才能被外界使用，所以队列容器也不允许遍历。
构造函数
| 原型 | 解释 |
|---|---|
| queue<T> que; | queue采用模板类实现，queue对象的默认构造形式 |
| queue(const queue& que); | 拷贝构造函数 |
赋值操作
| 原型 | 解释 |
|---|---|
| queue& operator=(const queue& que); | 重载等号操作符 |
数据存取
| 原型 | 解释 |
|---|---|
| push(elem); | 往队尾添加元素 |
| pop(); | 从队头移除第一个元素 |
| back(); | 返回最后一个元素 |
| front(); | 返回第一个元素 |
大小操作
| 原型 | 解释 |
|---|---|
| empty(); | 判断堆栈是否为空 |
| size(); | 返回栈的大小 |
list容器
链表，是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
链表由结点组成，而所谓结点，由存储数据元素的数据域和存储下一个结点地址的指针域组成。
链表采用动态存储分配，不会造成内存浪费和溢出。可以对任意位置进行快速插入或删除元素，但是遍历速度没有数组快，且占用空间比数组大。
STL中的链表是一个双向循环链表，即存储下一个元素的地址，也存储上一个元素的地址。
构造函数
| 原型 | 解释 |
|---|---|
| list<T> lst; | list采用模板类实现，对象的默认构造形式 |
| list(beg,end); | 构造函数将[beg,end)区间中的元素拷贝给本身 |
| list(n,elem); | 构造函数将n个elem拷贝给本身 |
| list(const list& lst); | 拷贝构造函数 |
赋值和交换
| 原型 | 解释 |
|---|---|
| assign(beg,end); | 将[beg,end)区间中的数据拷贝赋值给本身 |
| assign(n,elem); | 将n个elem拷贝赋值给本身 |
| list& operator=(const list& lst); | 重载等号操作符 |
| swap(lst); | 将lst与本身的元素互换 |
大小操作
| 原型 | 解释 |
|---|---|
| size(); | 返回容器中元素的个数 |
| empty(); | 判断容器是否为空 |
| resize(int num); | 重新指定容器的长度为num,若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
| resize(int num,elem); | 重新指定容器的长度为num,若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除 |
插入和删除
| 原型 | 解释 |
|---|---|
| push_back(elem); | 在容器尾部加入一个元素 |
| pop_back(); | 删除容器中最后一个元素 |
| push_front(elem); | 在容器开头插入一个元素 |
| pop_front(); | 从容器开头移除第一个元素 |
| insert(pos,elem); | 在pos位置插elem元素的拷贝，返回新数据的位置 |
| insert(pos,n,elem); | 在pos位置插入n个elem数据，无返回值 |
| insert(pos,beg,end); | 在pos位置插入[beg,end)区间的数据，无返回值 |
| clear(); | 移除容器的所有数据 |
| erase(beg,end); | 删除[beg,end)区间的数据，返回下一个数据的位置 |
| erase(pos); | 删除pos位置的数据，返回下一个数据的位置 |
| remove(elem); | 删除容器中所有与elem值匹配的元素 |
数据存取
| 原型 | 解释 |
|---|---|
| front(); | 返回第一个元素 |
| back(); | 返回最后一个元素 |
翻转和排序
| 原型 | 解释 |
|---|---|
| reverse(); | 翻转链表 |
| sort(); | 链表排序 |
set/multiset容器
set中，所有元素都会在插入时自动被排序。set/multiset的本质是关联式容器，底层结构用二叉树实现。
set不允许容器中有重复的元素，而multiset允许。原因是：set插入数据的同时会返回插入结果，表示插入是否成功，而multiset不会去检测数据。
构造与赋值
| 原型 | 解释 |
|---|---|
| set<T> st; | 默认构造函数 |
| set(const set& st); | 拷贝构造函数 |
赋值
| 原型 | 解释 |
|---|---|
| set& operator=(const set& st); | 重载等号操作符 |
大小与交换
| 原型 | 解释 |
|---|---|
| size(); | 返回容器中元素的数目 |
| empty(); | 判断容器是否为空 |
| swap(st); | 交换两个集合容器 |
插入与删除
| 原型 | 解释 |
|---|---|
| insert(elem); | 在容器中插入元素 |
| clear(); | 清除所有元素 |
| erase(pos); | 删除pos迭代器所指的元素，返回下一个元素的迭代器 |
| erase(beg,end); | 删除区间[beg,end)的所有元素，返回下一个元素的迭代器 |
| erase(elem); | 删除容器中值为elem的元素 |
查找和统计
| 原型 | 解释 |
|---|---|
| find(key); | 查找key是否存在，存在则返回该键的元素的迭代器；不存在则返回set.end(); |
| count(key); | 统计key的元素个数 |
pair对组
成对出现的数据，利用对组可以返回两个数据
两种创建方式：
// pair<type,type> p (value1,value2);
// pair<type,type> p = make_pair(value1,value2);
pair<string, int> p (string("Tom"),20);
cout << "姓名：" << p.first << "年龄：" << p.second << endl;排序
set可以用仿函数改变排序规则
#include <iostream>
#include <set>
using namespace std;
class MyCompare {
public:
bool operator()(int v1,int v2) const{
return v1 > v2;
}
};
void test01()
{
set<int,MyCompare> s1;
s1.insert(1);
s1.insert(5);
s1.insert(4);
s1.insert(2);
s1.insert(3);
for (set<int,MyCompare>::iterator it = s1.begin(); it != s1.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main()
{
test01();
system("pause");
}