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");
}