STL — 常用容器

2 STL — 常用容器 2.1 string容器 2.1.1 string基本概念

本质：

string是C++风格的字符串，而string本质上是一个类

string和char 的区别：*

char* 是一个指针string是一个类，类内部封装了char* ，管理这个字符串，是一个char*型的容器

特点:
string类内部封装了很多成员方法
例如:查找find，拷贝copy，删除delete替换replace，插入insert
string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

2.1.2 string构造函数

构造函数原型：

string(); //创建一个空的字符串 例如：string str;string(const char* s); //使用字符串s初始化string (const string& str); //使用一个string对象初始化另一个string对象string(int n, char c); //使用n个字符c初始化字符串 2.1.3 string赋值操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lr2bqn3P-1648379765277)(D:Typora图像image-20210813215422336.png)]

2.1.4 string拼接操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f5KwsOQn-1648379765278)(D:Typora图像image-20210813215942614.png)]

2.1.5 string查找和替换操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r1Refocj-1648379765278)(D:Typora图像image-20210813220541342.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iQKQWumL-1648379765279)(D:Typora图像image-20210813221339111.png)]

2.1.6 string字符串比较

功能描述：

字符串之间的比较

比较方式：

字符串比较是按照字符的ASCII码进行对比

如果字符串相同 返回 0

如果第一个字符串大于第二个字符串 返回 1

如果第一个字符串小于第二个字符串 返回 -1

函数原型：

int compare(const string &s) const;//与字符串s比较int compare(const string &s) const;//与字符串s比较 2.1.7 string字符存取

string中单个字符存取方式有两种

char& operator[](int n) //通过[ ]方式取字符char& at(int n) //通过at方法取字符

2.1.8 string字符插入删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HXQk2DY4-1648379765279)(D:Typora图像image-20210813222607680.png)]

2.1.9 string字串

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hC1yeLS7-1648379765280)(D:Typora图像image-20210813222928855.png)]

2.2 vector容器 2.2.1 vector基本概念

功能：

STL中的vector容器的数据结构和数组非常相似，类似于栈，所以称为单端数组

vector与普通数组的区别：

不同之处在于数组是静态空间，而vector可以动态扩展

动态扩展：

并不是在原空间后再续接新的空间，而是重写开辟出更大的内存空间，然后将原有的数据拷贝到新的空间，同时释放原空间

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xAJuaDnR-1648379765280)(D:Typora图像image-20210814133827289.png)]

vector容器中的迭代器是支持随机访问的迭代器

2.2.2 vector构造函数

**功能描述：**创建vector容器

函数原型：

vectorv; //采用模板实现类实现，默认构造函数vector(v.begin(), v.end()) //将v[ begin(), end() )区间中的元素拷贝给对象本身(区间前闭后开)vector(n, elem) //构造函数，将n个elem拷贝给本身vector(const vector &vec) //拷贝构造函数 2.2.3 vector赋值操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-21ZmWbWq-1648379765281)(D:Typora图像image-20210814134638887.png)]

2.2.4 vector容量和大小 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BIJpiApC-1648379765282)(D:Typora图像KM%%H$S6C]VJQ{@IB78]%MT.png)]

注：resize()方法只会改变size不会改变capacity

2.2.5 vector插入和删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LgDf95HZ-1648379765282)(D:Typora图像image-20210814135039404.png)]

2.2.6 vector数据存取

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O6I5UBf1-1648379765283)(D:Typora图像image-20210814135121558.png)]

2.2.7 vector互换容器

功能描述：

实现两个容器内元素进行互换

函数原型：

swap(vec); //将vec与本身的元素进行互换

注：互换指的是所有的内容进行互换，包括容器大小和容量

应用：swap收缩内存

#include 
#include
#include
#include
using namespace std;

int main()
{
    //定义一个容器v大小为1000
    vectorv;
    for (int i = 0; i < 1000; i++)
    {
        v.push_back(i);
    }
    cout << "v容器的原大小和容量："<(v).swap(v);     //创建一个匿名对象，利用拷贝构造把容器v赋给匿名对象，然后匿名对象调用swap方法与容器v进行互换
    cout << "v的容量为：" << v.capacity() << endl;
    cout << "v的大小为：" << v.size() << endl;
    return 0 ;
}


//输出结果：
v容器的原大小和容量：
v的容量为：1066
v的大小为：1000
v容器resize后的大小和容量：
v的容量为：1066
v的大小为：10

v容器收缩后的大小和容量：
v的容量为：10
v的大小为：10

2.2.8 vector预留空间

功能描述：

减少vector在动态扩展容量时的扩展次数

获取扩展次数：

#include 
#include
#include
#include
using namespace std;

int main()
{
    vectorv;
    int num = 0;   
    int* p = NULL;  //定义一个int*空指针
    for (int i = 0; i < 100000; i++)
    {
        v.push_back(i);
        if (p != &v[0]) //如果p的指向不是首元素则说明v又开辟了新的内存
        {
            p = &v[0]; //使p指向首元素
            num++;    //次数递增
        }
    }
    cout << num << endl;
    return 0 ;
}


//输出结果：
30

函数原型：

reserve(int len) //容器预留len个元素长度，预留位置不初始化，元素不可访问 2.3 deque容器 2.3.1 deque容器基本概念

功能描述：

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

deque与vector区别：
1、vector对于头部的插入删除效率低，数据量越大，效率越低.

2、deque相对而言，对头部的插入删除速度回比vector快

3、vector访问元素时的速度会比deque快,这和两者内部实现有关

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FtLcnGY7-1648379765283)(D:Typora图像image-20210814142944808.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vFkcoROx-1648379765284)(D:Typora图像image-20210814143226531.png)]

2.3.2 deque构造函数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5b741b2S-1648379765285)(D:Typora图像image-20210814143429859.png)]

2.3.3 deque赋值操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X3kTtD9y-1648379765285)(D:Typora图像image-20210814143858689.png)]

2.3.4 deque大小操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mGO6Ubjc-1648379765286)(D:Typora图像image-20210814144248875.png)]

与vector的区别是deque在中控器中可增加缓冲区，所有没有容器限制

2.3.5 deque插入删除操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l8IAZdmg-1648379765287)(D:Typora图像image-20210814145152698.png)]

2.3.6 deque数据存取

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gUxRdi1n-1648379765287)(D:Typora图像image-20210814150833879.png)]

2.3.7 deque数据排序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YNk9Mfmr-1648379765288)(D:Typora图像image-20210814151123240.png)]

默认的排序方式为升序

#include 
#include
#include
#include
#include
#include
using namespace std;

class Player
{
public:
    string name;
    int score;
    Player(string name)
    {
        this->name = name;
    }
};
int main()
{
    srand((unsigned int)time(NULL));
    Player p1("A");
    Player p2("B");
    Player p3("C");
    Player p4("D");
    vectorplayer;
    player.push_back(p1);
    player.push_back(p2);
    player.push_back(p3);
    player.push_back(p4);
    for (vector::iterator it = player.begin(); it != player.end(); it++)
    {
        dequed;
        for (int j = 0; j < 10; j++)
        {
            int num = rand() % 10;
            d.push_back(num);
        }
        sort(d.begin(), d.end());
        d.pop_back();
        d.pop_front();
        int sum = 0;
        for (deque::iterator id = d.begin(); id != d.end(); id++)
        {
            sum += *id;
        }
        it->score = sum / 8;
    }
    for (int i = 0; i < player.size(); i++)
    {
        cout << player[i].score << endl;
    }
    return 0;
}

2.4 stack容器 2.4.1 stack基本概念

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

2.4.2 stack常用接口

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iwzWtzhP-1648379765288)(D:Typora图像image-20210814161734621.png)]

2.5 queue容器 2.5.1 queue基本概念

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7VPBWvaH-1648379765289)(D:Typora图像image-20210814162733959.png)]

2.5.2 queue 常用接口

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-orqYwqXe-1648379765289)(D:Typora图像image-20210814162956455.png)]

2.6 list容器 2.6.1 list基本概念

**功能：**将数据进行链式存储

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qn7juGXI-1648379765290)(D:Typora图像image-20210814164058638.png)]

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点:

采用动态存储分配，不会造成内存浪费和溢出

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点:
链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大
List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

2.6.2 list构造函数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DARQys7v-1648379765290)(D:Typora图像image-20210814165519737.png)]

2.6.3 list赋值和交换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XJSanyAH-1648379765291)(D:Typora图像image-20210814165814178.png)]

2.6.4 list大小操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jjuyrm7v-1648379765292)(D:Typora图像image-20210814170834554.png)]

2.6.5 list插入和删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XuHDd5oH-1648379765292)(D:Typora图像image-20210814170959462.png)]

2.6.6 list数据存取

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EnErmTDb-1648379765293)(D:Typora图像image-20210814171611595.png)]

2.6.7 list反转和排序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8xyHcIRc-1648379765293)(D:Typora图像image-20210814172754357.png)]

因为list的迭代器不支持随机访问，所以不可以使用标准算法algorithm，需要使用自身的排序方法，默认也为升序

如果想要降序操作，需要在sort中传入一个函数名

函数具体实现如下：

bool compare(int a, int b)
{	
	return a > b;
}

多条件排序案例：

#include 
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Person
{
public:
    string name;
    int age;
    int height;

    Person(string name, int age, int height)
    {
        this->name = name;
        this->age = age;
        this->height = height;
    }
};
void creat(list& lp)
{
    Person p1("张三", 18, 162);
    Person p2("里斯", 19, 188);
    Person p3("王五", 12, 124);
    Person p4("赵六", 24, 175);
    Person p5("李四", 19, 169);

    lp.push_back(p1);
    lp.push_back(p2);
    lp.push_back(p3);
    lp.push_back(p4);
    lp.push_back(p5);
}

bool real(Person &p1, Person &p2)
{
    if (p1.age == p2.age)
    {
        return p1.height > p2.height;
    }
    else
    {
        return p1.age < p2.age;
    }

}
int main()
{
    listl;
    creat(l);
    for (list::const_iterator it = l.begin(); it != l.end(); it++)
    {
        cout << it->name << "t" << it->age << "t" << it->height << endl;
    }
    cout << "排序后：" << endl;
    l.sort(real);
    for (list::const_iterator it = l.begin(); it != l.end(); it++)
    {
        cout << it->name << "t" << it->age << "t" << it->height << endl;
    }
    return 0;
}

2.7 set / multiset 容器 2.7.1 set基本概念

作用：

所有元素都会在插入时自动被排序

本质：

set/multiset属于关联式容器，底层结构式用二叉树实现的

set与multiset区别：

set不允许容器中出现重复的元素multiset允许容器中出现重复的元素 2.7.2 set构造和赋值

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-esbLvtol-1648379765294)(D:Typora图像image-20210814185220986.png)]

2.7.3 set大小和交换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OlXYKzq6-1648379765294)(D:Typora图像image-20210814190355683.png)]

2.7.4 set插入和删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Rt9ZvRcj-1648379765295)(D:Typora图像image-20210814190630721.png)]

set只有insert写入数据的方法

2.7.5 set的查找和统计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kQUOs2Cc-1648379765295)(D:Typora图像image-20210814191009613.png)]

2.7.6 set和multiset的区别

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z03fTwLa-1648379765296)(D:Typora图像image-20210814192528809.png)]

2.7.7 pair对组的创建

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qdiStdd8-1648379765296)(D:Typora图像image-20210814192736867.png)]

2.7.8 set容器排序

set容器默认的排序规则为从小到大，但可以利用仿函数，改变原有的排序规则

1、对于内置数据类型

#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class MyCompare
{
public:
     bool operator()(int v1, int v2)const   //定义仿函数
    {
        return v1 > v2;
    }
};
void test01()
{
    sets1;
    s1.insert(50);
    s1.insert(20);
    s1.insert(30);
    s1.insert(40);
    s1.insert(10);
    for (set::iterator it = s1.begin(); it != s1.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
    cout << "更改排序规则后：" << endl;
    sets2;
    s2.insert(50);
    s2.insert(20);
    s2.insert(30);
    s2.insert(40);
    s2.insert(10);
    for (set::iterator it = s2.begin(); it != s2.end(); it++)
    {
        cout << *it << " ";
    }
}
int main()
{
    test01();
    return 0;
}



//输出结果：
10 20 30 40 50
更改排序规则后：
50 40 30 20 10

2、对于自定义数据类型

#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Person
{
public:
    string name;
    int age;
    Person(string name, int age)
    {
        this->name = name;
        this->age = age;
    }
};

class comparePerson
{
public:
    bool operator()(Person p1, Person p2)const     //定义仿函数
    {
        return p1.age > p2.age;
    }
};

void test01()
{
    Person p1("张三", 18);
    Person p2("李四", 28);
    Person p3("王五", 21);
    Person p4("里斯", 16);
    Person p5("赵六", 25);
    sets;
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);
    s.insert(p4);
    s.insert(p5);
    for (set::iterator it = s.begin(); it !=s.end(); it++)
    {
        cout << it->name << "t" << it->age << endl;
    }
}
int main()
{
    test01();
    return 0;
}


//输出结果：
李四    28
赵六    25
王五    21
张三    18
里斯    16

2.8 map/ multimap容器 2.8.1 map的基本概念

简介：

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

本质：

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

优点：

可以根据key值快速查找到value值

map与multimap的区别：

map不允许容器中有重复的key值元素multimap允许容器中有重复的key元素 2.8.2 map构造和赋值

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qY4RxGYh-1648379765297)(D:Typora图像image-20210814214415496.png)]

2.8.3 map大小和交换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4QAEaeud-1648379765297)(D:Typora图像image-20210814214455118.png)]

2.8.4 map插入和删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b44ZKl98-1648379765298)(D:Typora图像image-20210814214936747.png)]

2.8.5 map插入和删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f3WeaaX9-1648379765298)(D:Typora图像image-20210814215702406.png)]

2.8.6 map容器排序

map容器默认排序的规则为：按照key值进行从小到大排序

利用仿函数，可以改变排序顺序

**示例：**实现key降序

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

include
#include
#include

class Compare
{
public:
bool operator()(int v1, int v2)const //定义仿函数
{
return v1 > v2;
}
};

void test01()
{
mapm;
m.insert(pair(1, 10));
m.insert(pair(6, 60));
m.insert(pair(5, 50));
m.insert(pair(10, 100));
m.insert(pair(8, 80));
for (map::iterator it = m.begin(); it != m.end(); it++)
{
cout << “key：” << it->first << “tvalue：” << it->second << endl;
}
}
int main()
{
test01();
return 0;
}

//输出结果：
key：10 value：100
key：8 value：80
key：6 value：60
key：5 value：50
key：1 value：10