STL
1 STL的诞生
长久以来,软件界一直希望建立一种可重复利用的东西;
C++的面向对象和泛型编程思想,目的是复用性的提升;
大多情况下,数据结构和算法都未能有一套标准,导致被迫从事大量重复工作;
为了建立数据结构和算法的一套标准,诞生了STL。
C++面向对象的三大特性:封装、继承、多态。
2 STL基本概念
STL(standard template library,标准模板库)
STL从广义上分为:容器(container)、算法(algorithm)、迭代器(iterator)
容器和算法之间通过迭代器进行无缝连接
STL几乎所有的代码都采用了模板类或模板类函数。
3 STL六大组件:容器、算法、迭代器、仿函数、适配器(配接器),空间配置器。
容器;各种数据结构,如vector、list、deque、set、map等,用来存放数据。
算法:各种常用的算法,如sort、find、copy、for_each等
迭代器:扮演了容器与算法之间的胶合剂
仿函数:行为类似函数,可作为算法的某种策略
适配器:一种用来修饰容器或仿函数或迭代器接口的东西
空间适配器:负责空间的配置与管理。
4 容器分为序列式容器和关联式容器两种。
序列式容器:强调值的排序,序列式容器中的每个元素均有固定的位置。
关联式容器:二叉树结构,各元素之间没有严格的物理上的顺序关系
5 算法分为质变算法和非质变算法。
质变算法:是指运算过程中会更改区间内的元素的内容,例如拷贝,替换,删除等等
非质变算法:是指运算过程中不会更改区间内的元素的内容,例如查找、计数、遍历、寻找极值等等。
6 迭代器:提供一种方法,使之能够依序寻访某个容器所含的各个元素,而又无需暴露该
容器的内部表示方式,每个容器都有自己专属迭代器; 迭代器使用非常类似于指针,初学阶段我们可以先理解迭代器为指针。
常用的容器迭代器种类为双向迭代器和随机访问迭代器。
Vector 容器
算法:for_each 迭代器:vector<int>::iterator
1 使用vector容器时,需要包含头文件include<vector>
2 创建一个容器vector<int>v;
3 使用尾插法插入数据,v.push_back(数据);
4 通过迭代器访问容器中的数据
Vector<int>::iterator itBegin = v.begin(); // v.begin() 起始迭代器 指向容器中第一个元素
Vector<int>::iterator itEnd = v.end(); // 结束迭代器 指向容器的最后一个元素的下一个位置。
遍历方式一
遍历方式二
5 vector容器存放自定义数据类型(Person)
6 容器嵌套容器(类似二维数组)
1 创建容器
vector<T> v; //采用模板实现类实现,默认构造函数
vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem); //构造函数将n个elem拷贝给本身。
vector(const vector &vec); //拷贝构造函数
2 赋值操作
vector &operator=(const vector &vec); //重载等号操作符
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。
3 容量和大小
empty(); //判断容器是否为空
capacity(); //容器的容量
size(); //返回容器中元素的个数
resize(int num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
resize(int num, elem); //重新指定容器的长度为num,若容器变长,则以elem填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
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(); // 删除容器中所有元素
5 数据存取
at(int idx); //返回索引idx所指的数据
operator[]; //返回索引idx所指的数据
front(); //返回容器中的第一个数据元素
back(); // 返回容器中最后一个数据元素
6 互换容器
swap(vec); //将vec与本身的元素互换
7 预留空间
reserve(int len); //容器预留len个元素长度,预留位置不初始化,元素不可访问
String容器
1 构造方式
String(); // 创建一个空的字符串,例如:string str;
String(const char s); //使用字符串s初始化
String(const string &str); // 使用一个string对象初始化另一个string对象
String(int n, char c); //使用n个符c初始化。
2 赋值操作方式
String & operator=(const char * s); // char类型字符串赋值给当前的字符串
String & operator=(const string &s); //把字符串s赋给当前的字符串
String & operator=(char 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个字符c赋给当前字符串
3 字符串拼接
String & operator+=(const char * str); //重载+=操作符
String & operator+=(const char c); //重载+=操作符
String & operator+=(const string& str); //重载+=操作符
String & append(const char *s); //把字符串s连接到当前字符串的尾部
String & append(const char *s, int n); //把字符串s的前n个字符连接到当前字符
串的尾部
String & append(const string &s); //同operator+=(const string & str)
String & append(const string &s, int pos, int n); //把字符串s中从pos开始的n个
字符连接到字符的结尾
4 查找和替换
查找:查找指定字符串是否存在
int find(const string &str, int pos=0)const; // 查找str第一次出现的位置,从pos=0开始查找。
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 *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
总结:
1 find查找是从左往右,rfind是从右往左;
2 find找到字符串后返回查找的第一个字符位置,找不到返回-1;
3 replace在替换时,要指定从哪个位置起,多少个字符,替换成什么样的字符串。
5 字符串比较
1 比较方式:按字符的ASCII码进行对比(=返回 0,>返回1,<返回-1)
int compare(const string &s)const; //与字符串s比较
int compare(const char *s)const; //与字符串s比较
6 字符串存取方式
char &operator[](int n); //通过[]方式取字符
char &at(int n); //通过at方法获取字符
7 插入和删除
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个字符
8 子串(从字符串中获取想要的子串)
string substr(int pos=0, int n=npos)const; //返回由pos开始的n个字符组成的字符串。
deque容器
功能:双端数组,可以对头端进行插入删除操作
deque与vector区别
vector对于头部的插入删除效率低,数据量大,效率越低;
deque相对而言,对头部的插入删除速度会比vector快;
vector访问元素时的速度会比deque快,这和两者内部实现有关。
deque内部工作原理:
deque内部有个中控器,维护每段缓冲区中的内容,缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址,使得使用deque时像一片连续的内存空间
deque容器的迭代器也是支持随机访问的
1 构造函数
deque<T> deqT; //默认构造形式
deque(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身
deque(n, elem); //构造函数将n个elem拷贝给本身
deque(const deque &deq); //拷贝构造函数
注意deque容器的迭代器要加const,在遍历的时候。
2 赋值操作
deque &operator =(const deque &deq); //重载等号操作符
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身
3 大小操作
deque.empty(); //判断容器是否为空
deque.size(); //返回容器中元素的个数
deque.resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
duque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
push_back(elem); //尾插
push_front(elem); //头插
pop_back(); //删除最后一个元素
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位置的数据,返回下一个数据的位置
5 数据存取
at(int idx); //返回索引idx所指的数据
operator[]; //同上
front(); // 返回容器中第一个数据元素
back(); // 返回容器中最后一个数据元素
6 排序
sort(iterator beg, iterator end) //对beg和end区间内元素进行排序,加头文件algorithm
stack容器
stack是一种先进后出(FILO)的数据结构,它只有一个出口
栈中只有顶端的元素可以被外界使用,因此不允许有遍历行为
栈中进入数据称为——入栈push
栈中弹出数据称为——出栈pop
1 构造函数
stack<T> stk; //stack采用模板类实现,stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数
2 赋值操作
stack& operator=(const stack &stk); //重载等号操作符
3 数据存取
push(elem); //向栈顶添加元素
pop(); //从栈顶移除第一个元素
top(); //返回栈顶元素
4 大小操作
empty(); // 判断堆栈是否为空
size(); //返回栈的大小
queue 容器
queue是一种先进先出(FIFO)的数据结构,它有两个出口
队列容器允许从一端新增元素,从另一端移除元素
队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为
队列中进数据称为——入队 push
队列中出数据称为——出队 pop
1 构造函数
queue<T> que; //queue采用模板类实现,queue对象的默认构造形式
queue(const queue &que); // 拷贝构造函数
2 赋值操作
queue& operator= (const queue & que); //重载等号操作符
3 数据存取
push(elem); //往队尾添加元素
pop(); //从队头移除第一个元素
back(); //返回最后一个元素
front(); //返回第一个元素
4 大小操作
empty(); //判断堆栈是否为空
size(); // 返回栈的大小
list容器
功能:将数据进行链式存储
链表(list)是一种物理存储单元上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接实现的。
链表的组成:由一系列结点组成。
结点的组成:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
STL中的链表是一个双向循坏链表:
由于链表的存储方式并不是连续的内存空间,因此链表list中的迭代器只支持前移和后移,属于双向迭代器。
List的优点:
采用动态存储分配,不会造成内存浪费和溢出
链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素。
List的缺点:
链表灵活,但是空间(指针域)和时间(遍历)额外耗费较大
注:list有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效,这在vector是不成立的。
总结:STL中list和vector是两个最常用的容器,各有优缺点。
1 构造函数
list<T> lst; //list采用模板类实现,对象的默认构造形式
list(beg, end); //构造函数将[beg, end)区间中的元素拷贝给本身
list(n, elem); //构造函数将n个elem拷贝给本身
list(const list &lst); //拷贝构造函数
2 赋值和交换
assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem); //将n个elem拷贝赋值给本身
list& operator=(const list &lst); //重载等号操作符
swap(lst); // 将lst与本身的元素互换。
3 大小操作
size(); //返回容器中元素的个数
empty(); //判断容器是否为空
resize(num); //重新指定容器的长度为num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,若容器变短,则末尾超出容器长度的元素被删除。
4 插入和删除
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值匹配的元素。
5 数据存取
front(); //返回第一个元素
back(); //返回最后一个元素
6 反转和排序
reverse(); // 反转链表
sort(); // 链表排序
set/multiset容器
简介:所有元素都会在插入时自动被排序
本质:set/multiset属于关联式容器,底层结构用二叉树实现。
set和multiset区别:
set不允许容器中有重复的元素
multiset允许容器中有重复的元素
1 构造和赋值
set<T> st; //默认构造函数
set(const set &st); //拷贝构造函数
set &operator=(const set &st); //重载等号操作符
2 大小和交换
size(); //返回容器中元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器
3 插入和删除
insert(elem); //在容器中插入元素
clear(); //清除所有元素
erase(pos); //删除pos迭代器所指的元素,返回下一个元素的迭代器
erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
erase(elem); //删除容器中值为elem的元素
4 查找和统计
find(key); //查找key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
count(key); //统计key的元素个数
pair对组创建(两种方式)
pair<type, type> p (value1, value2);
pari<type, type> p = make_pair(value1, value2);
set与unordered_set的区别
a c++ std中set与unordered_set区别和map与unordered_map区别类似:
set基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。
unordered_set基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存,无自动排序功能。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
b set使用时设置:
我们需要有序数据(不同的元素)
我们必须打印/访问数据(按排序顺序)
我们需要元素的前身/后继者
c 在以下情况下使用unordered_set:
我们需要保留一组不同的元素,不需要排序。
我们需要单个元素访问,即没有遍历。
map/multimap容器
简介:map中所有元素都是pair;
pair中第一个元素为key(键值),起到索引作用,第二个元素为values(实值)
所有元素都会根据元素的键值自动排序
本质:map/multimap属于关联式容器,底层结构是用二叉树实现
优点:可以根据key值快速找到value值
Map和multimap区别: map不允许容器中有重复的key值元素
Multimap允许容器中有重复key值元素。
1 构造和赋值
map<T1, T2> mp; //map默认构造函数
map(const map &mp); //拷贝构造函数
map & operator=(const map & mp); //重载等号操作符
2 大小和交换
size(); //返回容器中所有元素的数目
empty(); //判断容器是否为空
swap(st); //交换两个集合容器
3 插入和删除
insert(elem); //在容器中插入元素
clear(); //清除所有元素
erase(pos); //删除pos迭代器所指的元素,返回下一个元素的迭代器
erase(beg, end); //删除区间[beg, end)的所有元素,返回下一个元素的迭代器
erase(key); //删除容器中值为key的元素
4 查找和统计
find(key); //查找key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
count(key); // 统计key的元素的个数