STL初识

一、STL初识

容器、算法、迭代器

容器和算法之前通过迭代器无缝连接

STL几乎所有的代码都采用了类模板和函数模板

STL六大组件

容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器

1.容器：各种数据结构，如vector，list，deque，set，map等，用来存放数据

2.算法：各种常用算法，如sort，find，copy，for_each

3.迭代器：扮演了容器和算法之间的胶合剂

4.仿函数：行为类似函数，可作为算法的某种策略

5.适配器：一种用来修饰容器或者仿函数或迭代器接口的东西

6.空间配置器：负责空间的配置和管理

STL中容器、算法、迭代器

容器：序列式和关联式容器：

• 序列式容器：强调值的排序，序列式容器中的每个元素都有固定的位置
• 关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系

算法：质变算法和非质变算法：

• 质变算法：运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等
• 非质变算法：运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等

迭代器：容器和算法之间的粘合剂

• 提供一种方法，使之能够依序访问某个容器所含的各个元素，而无需暴露该容器的内部表示方式。
• 每个容器都有自己的专属迭代器
• 迭代器类似指针

迭代器种类:

常用迭代器为双向迭代器，随机访问迭代器

二、容器算法迭代器初识

1.vector容器存放内置数据类型

容器:vector

算法:for_each

迭代器:vector<int>::iterator

三种遍历算法

#include <vector>
vector<int> mv;
vector<int>::iterator itBegin = mv.begin();//起始迭代器，指容器中第一个元素
vector<int>::iterator itEnd = mv.end();//结束迭代器 指向容器中最后一个元素的下一个位置
while (itBegin!=itEnd)//第一种遍历方式
{
    cout << *itBegin << endl;
    itBegin++;
}

for (vector<int>::iterator it = mv.begin();it!=mv.end();it++)//第二种遍历方式
{
    cout << *it << endl;
}

#include <algorithm>
void myPrint(int i)
{
    cout << i << endl;
}
//调用
...
    vector<int> mv;//创建容器
    mv.push_back(10);//尾插入数据
    for_each(mv.begin(), mv.end(), myPrint);//STL提供的遍历算法
...

2.vector容器中存放自定义的数据类型

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
//vector容器存放自定义数据类型
class Person
{
public:
    string m_Name;
    int m_Age;
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
};
void myPrint(Person p)
{
    cout << p.m_Name << p.m_Age << endl;
}
void test1()
{
    vector<Person> mv;
    Person p1("aaa", 10);
    Person p2("vvv", 20);
    Person p3("sss", 30);
    mv.push_back(p1);
    mv.push_back(p2);
    mv.push_back(p3);
    for_each(mv.begin(), mv.end(), myPrint);//STL提供的遍历算法
}
int main()
{
    test1();
    system("pause");
}

3.vector容器嵌套

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void myPrintv(int i)
{
    cout << i << endl;
}
void myPrint(vector<int> mv)
{
    for_each(mv.begin(), mv.end(), myPrintv);//STL提供的遍历算法
}
void test1()
{
    vector<vector<int>> mv;
    vector<int> mv1;
    vector<int> mv2;
    vector<int> mv3;
    for (int i=0; i<4 ; i++)
    {
        mv1.push_back(i+1);
        mv2.push_back(i+2);
        mv3.push_back(i+3);
    }
    //将小容器插入大容器中
    mv.push_back(mv1);
    mv.push_back(mv2);
    mv.push_back(mv3);
    for_each(mv.begin(), mv.end(), myPrint);//STL提供的遍历算法
}
int main()
{
    test1();
    system("pause");
}

三、vector容器

功能：

• vector数据结构和数组非常相似，也成为单端数据
• vector可以动态扩展、不是在原空间之后接续新空间，而是找到更大的内存空间，然后将源数据拷贝新空间，释放原空间
• vector迭代器支持随机访问

1.vector构造函数

创建vector容器

函数原型

vector<T> mv;    //采用模板实现类实现，默认构造函数
vector(mv.begin(), mv.end()); //将mv [ begin(),end() )区间中的元素拷贝给本身、 左闭右开
vector(n,elem);        //构造函数，将n个elem拷贝给本身
vector(const vector &vec);    //拷贝构造

2.赋值操作

vector& operator=(const vector &vec);//等号重载
vec1.assign(vec2.beg,vec2.end);            //将[ vec2.begin, vec2.end ) 区间中的数据拷贝复制给本身、并清空vec1原来的数组（如果有的话）
assign(n,elem);                //将n个elem拷贝复制给本身

3.容量和大小

empty();        //判断容器是否为空
capacity();        //容器的容量 >= size
size();            //返回容器中元素的个数
resize(int num);//重新制定容器的长度为num，若容器边长，则以默认值填充新位置、以0填充其他位置
                //若容器变短，则末尾超出容器长度的元素被删除
resize(int num, elem);

4.vector插入和删除

push_back(elem);    //尾部插入元素elem
pop_back();            //删除最后一个元素
insert(const_iterator pos, elem);//迭代器向指定位置pos插入元素elem
insert(const_iterator pos, int count, elem);//迭代器指定位置pos插入count个元素elem
erase(const_iterator pos);//删除迭代器指向的元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
clear();            //删除容器中所有元素

vector<int> mv;
vector<int>::iterator itBegin = mv.begin();//起始迭代器，指容器中第一个元素

5.vector数据存取

at(int index);        //返回index所指的数据
operator([]);        //返回索引indx
front();            //返回容器中第一个数据元素
back();                //返回容器中最后一个数据元素

vector<int> mv;
int temp = mv.front();

6.swap(vec)互换容器

std::vector::swap(vec);//将vec与本身的元素互换，

使用vector收缩内存空间

使用resize将原本存储占用更大空间的数据，会发现有很多空间被闲置

#include <iostream>
#include <vector>
void test03()
{
    vector<int> v1;
    for (int i = 0; i < 100000; i++)
    {
        v1.push_back(i);
    }
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为： " << v1.size() << endl;
    v1.resize(3);
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为： " << v1.size() << endl;
        //现在v1中只存在3个数据，但是却占用了很大的一段内存
}
int main()
{
    test03();
}

结果

v1的容量为：138255
v1的大小为： 100000
v1的容量为：138255
v1的大小为： 3

方法-vector<int>(v1).swap(v1);

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
void test03()
{
    vector<int> v1;
    for (int i = 0; i < 100000; i++)
    {
        v1.push_back(i);
    }
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为： " << v1.size() << endl;

    v1.resize(3);
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为： " << v1.size() << endl;

    cout << endl << "收缩内存后：" << endl;
    vector<int>(v1).swap(v1);
    cout << "v1的容量为：" << v1.capacity() << endl;
    cout << "v1的大小为： " << v1.size() << endl;

}
int main()
{
    test03();
    system("pause");
}

结果

v1的容量为：138255
v1的大小为： 100000
v1的容量为：138255
v1的大小为： 3

收缩内存后：
v1的容量为：3
v1的大小为： 3

std::vector::shrink_to_fit()-减少容器的容量以适应其大小并销毁超出容量的所有元素。

std::vector<int> sss={1,2,3,4};
sss.shrink_to_fit();

7.vector预留空间

std::vector::reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

四、deque容器

• 双端数组，可以对头端进行插入删除操作

1.deque和vector的区别

• vector对于头部的插入删除效率低，数据量大，效率越低、需要移动元素
• deque相对而言，对头部的插入删除速度比vector快
• vector访问元素的速度会比deque快,这和两者内部实现有关
• deque容器的迭代器也是支持随机访问的

2.deque内部工作原理

deque内部有个中控器,维护每段缓冲区中的内容，缓冲区中存放真实数据

中控器中存放每个缓冲区的地址，使得deque时像一片连续的内存空间

3.deque构造函数

函数原型

deque<Y> deqT;                //默认构造形式
deque(beg, end);            //构造函数将 [beg,end) 区间中的元素拷贝给本身
deque(n, elem);                //构造函数将n个连续的elem拷贝给本身
deque(const deque &deq);    //拷贝构造函数

4.deque赋值操作

函数原型

deque& operator=(const deque &deq);                //重载等号操作符
assign(beg, end);                                //将    [beg, end) 区间中的数据拷贝赋值给本身
assign(n, elem);                                //将n个elem拷贝赋值给本身

5.容器的大小

empty();        //判断容器是否为空
size();            //返回容器中元素的个数
//没有capacity();//没有容量限制
resize(int num);//重新制定容器的长度为num，若容器边长，则以默认值填充新位置、以0填充其他位置
                //若容器变短，则末尾超出容器长度的元素被删除
resize(int num, elem);

void printx(const deque<int>&d)
{
    for (deque<int>::const_iterator it = d.begin; it!=d.end(); it++)
    {
        cout << *it << endl;
    }
}
...
deque<int> dd1 = {1,2,3,4,5,6};
printx(dd1);
...

6.deque插入和删除

两端的插入删除操作

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位置的数据，返回下一个数据的位置

7.deque数据存取

at(int idx);                //返回索引idx所指的数据
operator[];                    //~
front();                    //返回容器中第一个数据元素
back();                        //返回容器中最后一个数据元素

8.deque排序

#include <algorithm>//标准算法头文件
sort(iterator beg, iterator end);        //对 [beg, end) 区间内元素进行排序 、默认升序

五、stack-栈容器

1.stack基本概念

概念:stack是一种先进后出（First In Last Out，FILO）的数据结构，它只有一个出口

• 栈中只有顶端的元素可以被外界使用，因此栈不允许有遍历行为

2.栈常用接口

构造

stack<T> stk;                //默认构造
stack<const stack &stk>        //拷贝构造

赋值

stack& operator=(const stack &stk);        //重载等号符

数据存取

push(elem);                    //栈入
pop();                        //栈出
top();                        //返回栈顶元素

大小操作

empty();                    //判断栈是否为空
size();                        //返回栈的大小

六、queue-队列容器

1.概念

先进先出(First In First Out, FIFO)的数据结构，有两个出口

• 只有两端有数据访问口，不能有遍历的行为

2.队列容器常用接口

构造

queue<T> stk;                //默认构造
queue<const queue &stk>        //拷贝构造

赋值

queue& operator=(const queue &stk);        //重载等号符

数据存取

push(elem);                    //队尾添加元素
pop();                        //队头移除第一个元素
back();                        //返回最后一个元素
front();                    //返回第一个元素

大小操作

empty();                    //判断队列是否为空
size();                        //返回队列的大小

七、list-链表容器

链表(list)是一种物理存储单元上非连续的储存结构，数据元素的逻辑顺序是通过链表中的指针链接实现的

组成：链表是由一系列的节点组成、节点由储存数据元素的数据域,另一个是储存下一个节点地址的指针域

STL中的list链表容器是一个双向循环链表

• 可以快速的插入或删除元素，修改指针即可，不必移动大量元素
• 采用动态内存分配，不会造成内存浪费和溢出
• 遍历的速度没数组快
• 占用的空间比数组大
• list插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的
• 由于链表的储存方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，不支持跳跃，属于双向迭代器

1.list构造函数

list<T> list;                    //默认构造
list(beg, end);                    //将 [beg, end) 区间中的元素拷贝给本身
list(n,elem);                    //构造函数将n个elem拷贝给本身
list(const list &list);            //拷贝构造函数

2.list赋值和交换

assign(beg, end);                //将 [beg, end) 区间中的数据拷贝赋值给本身
assign(n, elem);                //将n个elem拷贝赋值给本身
list& operator=(const list & lst);        //重载等号符
swap(lst);                        //将lst与本身的元素互换

3.list大小操作

empty();        //判断容器是否为空
size();            //返回容器中元素的个数
resize(int num);//重新制定容器的长度为num，若容器边长，则以默认值填充新位置、以0填充其他位置
                //若容器变短，则末尾超出容器长度的元素被删除
resize(int num, elem);

4.list插入和删除

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值匹配的元素，

使用list::remove（）删除自定义数据

核心就是第一个if的== 运算符，所以我们需要重载==运算符。不同编译器有不同特点，如果报错需要注意

• 在类外重载 == 运算符
• 用const修饰Person变量

class Person
{
public:
    Person(string name, int age, int height)
    {
        this->m_Age = age;
        this->m_Name = name;
        this->m_height = height;
    }

    string m_Name;
    int m_Age;
    int m_height;
};
//    类外重载==让remove可以删除自定义的Person类型
bool operator==(const Person &p1,  const Person &p2)
{
    if(p1.m_Age == p2.m_Age && p1.m_height == p2.m_height && p1.m_Name == p2.m_Name)
        return true;
    return false;
}
void test03()
{
    list<Person>l;
    Person p1("张三", 10, 172);
    Person p2("张三", 19, 145);
    Person p3("张三", 15, 181);
    Person p4("张三", 20,199);
    Person p5("张三", 19, 171);
    Person p6("张三", 19, 179);
    l.push_back(p1);
    l.push_back(p2);
    l.push_back(p3);
    l.push_back(p4);
    l.push_back(p5);
    l.push_back(p6);
    l.remove(p3);
}

5.list数据存取

front();                    //返回第一个元素
back();                        //返回最后一个元素

6.反转和排序

reverse();                    //反转列表
sort();                        //链表排序

对自定义类型进行排序

#include <iostream>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
class Person
{
public:
    Person(string name, int age, int Height) :m_Name(name), m_Age(age), m_Height(Height) {};
    string m_Name;
    int m_Age;
    int m_Height;//身高
};
bool comparePerson(Person &p1, Person &p2)
{
    return p1.m_Age < p2.m_Age;
}
void myPrint(const Person & mp)
{    
    cout << mp.m_Name << mp.m_Age << mp.m_Height << endl;
}
void test()
{
    list<Person> mlt;
    Person p1("刘备",12, 21);
    Person p2("曹操", 25, 180);
    Person p3("张飞", 15, 170);
    mlt.push_back(p1);
    mlt.push_back(p2);
    mlt.push_back(p3);
    for_each(mlt.begin(),mlt.end(), myPrint);
    cout << "-------------------------" << endl << "排序后" << endl;
    mlt.sort(comparePerson);
    for_each(mlt.begin(),mlt.end(), myPrint);
}
int main()
{
    test();
    system("pause");
}

八、set/multiset容器

• 所有元素都会在插入时被排序
• set/multiset属于关联式容器，底层结构是用二叉树实现。

set和multiset区别

• set不允许容器中有重复的元素
• multiset允许容器中有重复的元素

1.set构造和赋值

set<T> mset;                    //默认构造函数
set(const set &st);                //拷贝构造函数
set& operator=(const set &set); //重载等号赋值

2.set大小和交换

size();                            //返回容器中元素的数目
empty();                        //判断容器是否为空
swap(st);                        //交换两个集合容器

3.插入和删除

insert(elem);                    //在容器中插入元素
clear();                        //清除所有元素
erase(pos);                        //删除迭代器所指的元素,返回下一个元素的迭代器
erase(beg,end);                    //删除区间 [beg, end) 区间的所有元素，返回下一个元素的迭代器
erase(elem);                    //删除容器中值为elem的元素

4.查找和统计

find(key);                        //查找key是否存在，返回该键的元素的迭代器，若不存在，则返回set.end();
count(key);                        //统计key的个数、不是0就是1、而multiset可能会有多个数

5.set和mutiset的区别

• set不可以插入重复数据，而mutiset可以
• set插入数据的同时会返回插入结果，表示插入成功
• mutiset不会检测数据，因此可以插入重复数据

set<int> s;
pair<set<int>::iterator, bool>  ret = s.insert(10);
if (ret.second)
{
    //插入成功
}

6.pair对组创建

对组:成对出现的数据，利用对组可以返回两个数据

pair<type, type> p (value1, vlaue2);
pair<type, type> p = make_pair(value1, vlaue2);

访问

cout << p.first << endl;
cout << p.second << endl;

7.set容器排序-利用仿函数（重载()操作符）

• set容器默认排序为从小到大

class MyCompare
{
public:
    bool operator()(int v1, int v2)
    {
        return v1 > v2;
    }
};
//指定排序规则为从大到小
set<int, MyCompare> s1;
s1.insert(20);
s1.insert(130);
s1.insert(120);
s1.insert(150);
s1.insert(50);
s1.insert(20);

8.set存放自定义数据、如何排序

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
class Person
{
public:
    Person(string name, int age, int Height) :m_Name(name), m_Age(age), m_Height(Height) {};
    string m_Name;
    int m_Age;
    int m_Height;//身高
};
class comparePerson
{
public:
    bool operator()(const Person &p1, const Person &p2)
    {
        return p1.m_Age < p2.m_Age;
    }
};
void myPrint(const Person & mp)
{    
    cout << mp.m_Name << mp.m_Age << mp.m_Height << endl;
}
void test()
{
    set<Person, comparePerson> mlt;
    Person p1("刘备",12, 21);
    Person p2("曹操", 25, 180);
    Person p3("张飞", 15, 170);
    mlt.insert(p1);
    mlt.insert(p2);
    mlt.insert(p3);
    for_each(mlt.begin(),mlt.end(), myPrint);
}
int main()
{
    test();
    system("pause");
}

九、map/mutimap容器

简介：

• map所有元素都是pair
• pair中第一个元素为key(键值)，起到索引作用，第二个元素为value(实值)
• 所有元素都会根据元素的键值自动排序

本质：

• map/mutimap属于关联式容器，底层结构是用二叉树实现的。

优点：

• 可以根据key值快速找到vlaue值

map与mutimap的区别

• map不允许容器有重复key值
• mutimap允许容器有重复的key值

1.map构造和赋值

map<T key,T value> mp;            //map默认构造函数
map(const map &map);            //拷贝构造函数
map& operator=(const map &map);    //等号操作符重载

范例

#include <map>

map<int, int> mp;
mp.insert(pair<int, int> (1,10));

2.map大小和交换

size();                            //返回容器中元素的数目
empty();                        //判断容器是否为空
swap(mp);                        //交换两个集合容器

3.map插入和删除

insert(elem);                    //在容器中插入元素
clear();                        //清除所有元素
erase(pos);                        //删除迭代器所指的元素,返回下一个元素的迭代器
erase(beg,end);                    //删除区间 [beg, end) 区间的所有元素，返回下一个元素的迭代器
erase(key);                        //删除容器中key值对应的元素

#include <map>
map<int, int> mp;
mp.insert(pair<int, int> (1,10));
mp.insert(make_pair(2,2));        //建议
mp.insert(map<int, int>::value_type(3, 30));
mp[4] = 40;                        //不建议用来插入、因为如果不存在mp[i], 系统会自动创建一个新的，并将value复制为0

4.map查找和统计

find(key);                        //查找key是否存在，如果存在返回该键的迭代器，若不存在则返回map.end()
count(key);                        //统计key的元素个数

5.map容器排序-利用仿函数

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Labours
{
public:
    Labours(string name, int Salary) :m_name(name), m_Salary(Salary){};
    string m_name;
    int m_Salary;
};
void createLab(vector<Labours> &labs)
{
    labs.push_back(Labours("顾笑甜",10000));
    labs.push_back(Labours("邢林", 556565));
    labs.push_back(Labours("liu", 568462));
}
void myPrint(const pair<int, Labours> &pa)
{
    cout << pa.first << pa.second.m_name << pa.second.m_Salary << endl;
}
void setGroup(vector<Labours> & mvlabs, multimap<int, Labours> & mmaplabs)
{
    for (vector<Labours>::iterator it = mvlabs.begin(); it!= mvlabs.end(); it++)
    {
        int depId = rand() % 3;
        mmaplabs.insert(make_pair(depId, *it));//make_pair创建一个对组，并放入这两个数据
    }
}

vector<Labours> mlabs;
multimap<int, Labours> mLmap;
int main()
{
    createLab(mlabs);
    setGroup(mlabs, mLmap);
    cout << "mlabs size =" << mlabs.size() << endl;
    cout << "mLmap size =" << mLmap.size() << endl;
    for_each(mLmap.begin(), mLmap.end(), myPrint);
    system("pause");
}