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字符串比较
功能描述:
比较方式:
如果字符串相同 返回 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容器
函数原型:
vector<T>v;
//采用模板实现类实现,默认构造函数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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
using namespace std;
int main()
{
//定义一个容器v大小为1000
vector<int>v;
for (int i = 0; i < 1000; i++)
{
v.push_back(i);
}
cout << "v容器的原大小和容量:"<<endl;
cout << "v的容量为:" << v.capacity() << endl;
cout << "v的大小为:" << v.size() << endl;
//重新指定v的大小为10,但是v的容量不会变
v.resize(10);
cout << "v容器resize后的大小和容量:" << endl;
cout << "v的容量为:" << v.capacity() << endl;
cout << "v的大小为:" << v.size() << endl;
cout << endl;
//利用匿名对象和swap方法收缩内存
cout << "v容器收缩后的大小和容量:" << endl;
vector<int>(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预留空间
功能描述:
获取扩展次数:
#include <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
using namespace std;
int main()
{
vector<int>v;
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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
#include<deque>
#include<time.h>
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");
vector<Player>player;
player.push_back(p1);
player.push_back(p2);
player.push_back(p3);
player.push_back(p4);
for (vector<Player>::iterator it = player.begin(); it != player.end(); it++)
{
deque<int>d;
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<int>::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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
#include<deque>
#include<time.h>
#include<list>
#include<queue>
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<Person>& 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()
{
list<Person>l;
creat(l);
for (list<Person>::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<Person>::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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
#include<deque>
#include<time.h>
#include<list>
#include<queue>
#include<set>
using namespace std;
class MyCompare
{
public:
bool operator()(int v1, int v2)const //定义仿函数
{
return v1 > v2;
}
};
void test01()
{
set<int>s1;
s1.insert(50);
s1.insert(20);
s1.insert(30);
s1.insert(40);
s1.insert(10);
for (set<int>::iterator it = s1.begin(); it != s1.end(); it++)
{
cout << *it << " ";
}
cout << endl;
cout << "更改排序规则后:" << endl;
set<int, MyCompare>s2;
s2.insert(50);
s2.insert(20);
s2.insert(30);
s2.insert(40);
s2.insert(10);
for (set<int, MyCompare>::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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
#include<deque>
#include<time.h>
#include<list>
#include<queue>
#include<set>
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);
set<Person, comparePerson>s;
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
s.insert(p5);
for (set<Person, comparePerson>::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属于关联式容器,底层结构是用二叉树实现的
优点:
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 <iostream>
#include<vector>
#include<typeinfo>
#include<algorithm>
#include<deque>
#include<time.h>
#include<list>
#include<queue>
#include<set>
#include<map>
using namespace std;
class Compare
{
public:
bool operator()(int v1, int v2)const //定义仿函数
{
return v1 > v2;
}
};
void test01()
{
map<int, int, Compare>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(6, 60));
m.insert(pair<int, int>(5, 50));
m.insert(pair<int, int>(10, 100));
m.insert(pair<int, int>(8, 80));
for (map<int, int, Compare>::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
include
#include
#include
class Compare
{
public:
bool operator()(int v1, int v2)const //定义仿函数
{
return v1 > v2;
}
};
void test01()
{
map<int, int, Compare>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(6, 60));
m.insert(pair<int, int>(5, 50));
m.insert(pair<int, int>(10, 100));
m.insert(pair<int, int>(8, 80));
for (map<int, int, Compare>::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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)