vector是一个大小可变的动态数组（变长数组），和数组一样，他能对数组中的任意元素根据索引来快速访问。与普通数组不同的是，它的大小是可以动态变化的。当元素不断增加，超过vector自身容量后，vector会申请一块更大的内存空间（据参考资料这块内存空间是原来的一倍），把现有vector中的元素复制过去，然后销毁原来的内存。
2、怎么用它？ 使用vector，需要引入头文件#incude,然后，我们用vector来声明一个名为v的对象，这个对象可以储存n_elem个类型为typename的元素，式中n_elem也可以不写，这样初始长度默认为0，例子如下：
#includeQ：类型可以是类（如string）吗？
A：可以，如vector创造了一个string的vector
//1.构造函数
vector()//:创建一个空vector
vector(int nSize)//:创建一个vector,元素个数为nSize
vector(int nSize,const t& t)//:创建一个vector，元素个数为nSize,且值均为t
vector(const vector&)//:复制构造函数
vector(begin,end)//:复制[begin,end)区间内另一个数组的元素到vector中
//2.增加函数
void push_back(const T& x)//:向量尾部增加一个元素X
iterator insert(iterator it,const T& x)//:向量中迭代器指向元素前增加一个元素x
iterator insert(iterator it,int n,const T& x)//:向量中迭代器指向元素前增加n个相同的元素x
iterator insert(iterator it,const_iterator first,const_iterator last)//:向量中迭代器指向元素前插入另一个相同类型向量的[first,last)间的数据
//3.删除函数
iterator erase(iterator it)//:删除向量中迭代器指向元素
iterator erase(iterator first,iterator last)//:删除向量中[first,last)中元素
void pop_back()//:删除向量中最后一个元素
void clear()//:清空向量中所有元素
//4.遍历函数
reference at(int pos)//:返回pos位置元素的引用
reference front()//:返回首元素的引用
reference back()//:返回尾元素的引用
iterator begin()//:返回向量头指针，指向第一个元素
iterator end()//:返回向量尾指针，指向向量最后一个元素的下一个位置
reverse_iterator rbegin()//:反向迭代器，指向最后一个元素
reverse_iterator rend()//:反向迭代器，指向第一个元素之前的位置
//5.判断函数
bool empty() const//:判断向量是否为空，若为空，则向量中无元素
//6.大小函数
int size() const//:返回向量中元素的个数
int capacity() const//:返回当前向量所能容纳的最大元素值
int max_size() const//:返回最大可允许的vector元素数量值
//7.其他函数
void swap(vector&)//交换两个同类型向量的数据
void assign(int n,const T& x)//设置向量中前n个元素的值为x
void assign(const_iterator first,const_iterator last)//向量中[first,last)中元素设置成当前向量元素
注：vector中可以用>,<,==,!=等按字典序比较两个vector的大小。
Q： iterator迭代器是什么？
A： 迭代器是一个广义的指针，它可以执行类似指针的 *** 作，如解引用和递增。
迭代器使用举例：
vector<double>::iterator pd;//声明一个迭代器
vector<double> scores;
//可对迭代器 *** 作如下
pd = scores.begin();//让pd指向scores的首元素
*pd = 22.3;//给首元素赋值
pd++;//让pd指向scores的下一个元素
#includehttps://www.luogu.com.cn/problem/P1540
https://www.luogu.com.cn/problem/P1113
二、Stack&&Queue 1、简介：Stack（堆栈）是一种后进先出（Last in First out）的线性表，它只能在一端(称为栈顶(top))对数据项进行插入和删除。
Queue（队列）是一种先进先出（First in First out）的线性表表，它只允许在表的前端（front）进行删除 *** 作，而在表的后端（rear）进行插入 *** 作，和栈一样，队列是一种 *** 作受限制的线性表。进行插入 *** 作的端称为队尾，进行删除 *** 作的端称为队头。
2、怎么用它？例子如下：
#include- top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
- push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
- push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
- pop()：d出栈顶元素。
- size()：返回栈中元素的个数。
- empty()：在栈中没有元素的情况下返回 true。
- emplace()：用传入的参数调用构造函数，在栈顶生成对象。
- swap(stack & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。
| 元素访问 | |
|---|---|
| front | 访问第一个元素 (公开成员函数) |
| back | 访问最后一个元素 (公开成员函数) |
| 容量 | |
| empty | 检查底层的容器是否为空 (公开成员函数) |
| size | 返回容纳的元素数 (公开成员函数) |
| 修改器 | |
| push | 向队列尾部插入元素 (公开成员函数) |
| emplace(C++11) | 于尾部原位构造元素 (公开成员函数) |
| pop | 删除首个元素 (公开成员函数) |
| swap | 交换内容 (公开成员函数) |
注：stack和queue同样可以用>,<,==,!=等按字典序比较两个stack和queue的大小。
其中，stack是从栈底开始比较，queue是从队首开始比较
s[0].push(1);
s[0].push(2);
//top 2 1
s[1].push(2);
s[1].push(1);
//top 1 2
cout<<(s[0]>s[1])<<endl;
q[0].push(1);
q[0].push(2);
//front 1 2 rear;
q[1].push(2);
q[1].push(1);
//front 2 1 rear;
cout<<(q[0]>q[1])<<endl;
//输出为 0 0
这里面，emplace的用法其实与push相差不大，一些区别可以参见https://blog.csdn.net/Kprogram/article/details/82055673?utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control
4、实战例题https://www.luogu.com.cn/problem/CF911A
广度优先搜索的所有题都可以使用队列。
三、map 1、简介如何统计一串字符串中各个字符的数量？
一个比较巧妙的方法是建立一个数组，进行如下 *** 作：
int main(){
string s;
cin>>s;
int a[256] = {0};
for(int i = 0; i < s.length();i++){
a[s[i]]++;
}
}
a[s[i]]++其实是利用数组，建立了一个字符的ASCII值（s[i]）与对应字符数量的映射，我们把s[i]称作key（键），a[s[i]]称作key对应的value（值）。但利用数组建立的这种映射是有局限的，比如key只能是整型（或者类似整型的字符型）。
c++提供了map模板类来帮助我们建立更强大的映射，map的映射不局限于整型，它可以建立字符串到整型，结构体到字符型等等更强大的映射（注意结构体作为key时候需要重载 *** 作符<，可以参考https://blog.csdn.net/fengfengdiandia/article/details/87403713)。
2、怎么用它？#include//使用map，需要include map头文件
using namespace std;
int main(){
//创建map对象
map<string,int> myMap;//前面（string）是key，后面（int）是value
//创建map迭代器，指向map第一个元素
map<string,int>::iterator myMapIter = myMap.begin();
可以用myMapIter->first获取iter指向的map元素的key
用myMapIter->second获取iter指向的map元素的value
}
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
具体的增删改查参见https://www.cnblogs.com/yonglin1998/p/11780828.html，写得很详细
5、实战例题https://www.luogu.com.cn/problem/P1201
https://www.luogu.com.cn/problem/P1918
四、set 1、什么是set？ set的意思是集合。顾名思义，set里每一个元素都是唯一的，与数学中的集合不同的是，set内部会以特定的顺序储存每个元素（另一种容器unodered_set内部是无序的，这里不介绍）。
值得一提的是，如果要自定义排序关系来实现set，必须使用严格弱序（strict weak ordering）关系，即：两个相同的元素必须return false，这在我们使用sort函数时也应如此。
2、例题我们通过例题再来介绍set的基本 *** 作
题目描述：
读入n个数，要求按照从小到大的顺序输出出现的不同数字。
输入：第一行读入一个 n ( 0<n<=1000000)
第二行读入n个整数k （-2^31 <= k < 2^31 )
输出：
按从小到大的顺序输出不同的数字
样例输入
5
1 3 1 99999999 3
样例输出
1 3 99999999
代码：
#include由此我们掌握了set的基本使用，我们再来看看如何删除set内部的元素
#include同样的，set也有empty，size等方法，也有反向迭代器。set有一个count方法。在查询set内是否有某一个元素时，除了借助find方法，我们还可以使用count方法，count方法接收一个元素，返回一个set内具有该元素的个数，由于set内的元素是唯一的，所以该方法只会返回1（有该元素）或0（没有该元素）。
二、list 1、什么是list？list就是双向链表，所以它不仅可以正向遍历，也有反向迭代器
2、主要方法容量：empty判断链表是否为空，size返回链表的长度。
获取元素：front：返回第一个元素的引用，back：返回最后一个元素的引用。
插入元素：push_front,pop_front,push_back,pop_back，insert（插入位置是迭代器之前，返回值是新插入的元素的迭代器），函数如其名，具体 *** 作和之前vector等之类的容器类似。
// inserting into a list
#include
#include 删除元素：erase，与vector等类似，返回值是紧挨在被删除的迭代器之后的迭代器，区间的话也是前闭后开。
clear：删除所有元素。
resize：通过以下例子理解：
// resizing list
#include
int main ()
{
std::list<int> mylist;
// set some initial content:
for (int i=1; i<10; ++i) mylist.push_back(i);
mylist.resize(5);//1 2 3 4 5
mylist.resize(8,100);//1 2 3 4 5 100 100 100
mylist.resize(12);//1 2 3 4 5 100 100 100 0 0 0 0(in int, default value is zero)
std::cout << "mylist contains:";
for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
splice:"连接"两个表，通过以下例子理解：
// splicing lists
#include
int main ()
{
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
// set some initial values:
for (int i=1; i<=4; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4
for (int i=1; i<=3; ++i)
mylist2.push_back(i*10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // points to 2
mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element)
mylist2.splice (mylist2.begin(),mylist1, it);
// mylist1: 1 10 20 30 3 4
// mylist2: 2
// "it" is now invalid.
it = mylist1.begin();
std::advance(it,3); // "it" points now to 30
mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
// mylist1: 30 3 4 1 10 20
sort:和平常用sort一样调用就可以了，也可以自定义cmp；
merge：把已经排序好的两个链表（要先调用sort）合并在一起，合并后仍有序
first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);
second.push_back (3.7);
second.push_back (7.1);
second.push_back (1.4);
first.sort();
second.sort();
first.merge(second);
//first:1.4 2.2 2.9 3.1 3.7 7.1
unique：去除重复的元素（如果当前元素与前一个元素相同），一般与sort配合，达到去除所有重复元素的目的，可以自定义去除的函数。
// list::unique
#include
// a binary predicate implemented as a function:
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }
// a binary predicate implemented as a class:
struct is_near {
bool operator() (double first, double second)
{ return (fabs(first-second)<5.0); }
};
int main ()
{
double mydoubles[]={ 12.15, 2.72, 73.0, 12.77, 3.14,
12.77, 73.35, 72.25, 15.3, 72.25 };
std::list<double> mylist (mydoubles,mydoubles+10);
mylist.sort(); // 2.72, 3.14, 12.15, 12.77, 12.77,
// 15.3, 72.25, 72.25, 73.0, 73.35
mylist.unique(); // 2.72, 3.14, 12.15, 12.77
// 15.3, 72.25, 73.0, 73.35
mylist.unique (same_integral_part); // 2.72, 3.14, 12.15
// 15.3, 72.25, 73.0
mylist.unique (is_near()); // 2.72, 12.15, 72.25
std::cout << "mylist contains:";
for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
deque可以看做两头都能插入的vector，其各种 *** 作可以参见vector，但它比vector多了push_front和pop_front两种方法，即vector不可以从头部插入删除而deque可以。
七、总结：容器的选用[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nONmtnM5-1651055047529)(E:\杂物\科技小组作业\2021年6月_颜杰东_每月博客\20210109195048111.jpg)]
八、两个可能有用的STL1.nth_element(first, nth, last, compare)
求[first, last]这个区间中第n大小的元素，如果参数加入了compare函数，就按compare函数的方式比较。
nth_element仅排序第n个元素（从0开始索引），即将位置n（从0开始）的元素放在第n大的位置，处理完之后，默认排在它前面的元素都不比它大，排在它后面的元素都不比它小。
例如：array[first, last)元素区间，排序后，array[nth]就是第n大的元素（从0开始）
但是[first, nth) 和 [nth,last)区间的大小顺序不一定。但是可以确定的是array[nth]一定是整个区间里第n大的元素。[first,nth)中的元素都是不大于array[nth]的，[nth, last)中的元素都是不小于array[nth]的。
https://blog.csdn.net/xiaoquantouer/article/details/51591140
2.bool next_permutation(iterator start,iterator end)
next_permutation()会取得[first,last)所标示之序列的下一个排列组合，如果没有下一个排列组合，便返回false;否则返回true。
https://blog.csdn.net/qian2213762498/article/details/79683905
九、c++官网关于各种STL用法的介绍本文只介绍了一些比较常用的STL的基本用法，若想更深入了解更多的STL使用方法，请参考c++官方文档
元素（从0开始索引），即将位置n（从0开始）的元素放在第n大的位置，处理完之后，默认排在它前面的元素都不比它大，排在它后面的元素都不比它小。
例如：array[first, last)元素区间，排序后，array[nth]就是第n大的元素（从0开始）
但是[first, nth) 和 [nth,last)区间的大小顺序不一定。但是可以确定的是array[nth]一定是整个区间里第n大的元素。[first,nth)中的元素都是不大于array[nth]的，[nth, last)中的元素都是不小于array[nth]的。
https://blog.csdn.net/xiaoquantouer/article/details/51591140
2.bool next_permutation(iterator start,iterator end)
next_permutation()会取得[first,last)所标示之序列的下一个排列组合，如果没有下一个排列组合，便返回false;否则返回true。
https://blog.csdn.net/qian2213762498/article/details/79683905
九、c++官网关于各种STL用法的介绍本文只介绍了一些比较常用的STL的基本用法，若想更深入了解更多的STL使用方法，请参考c++官方文档
http://www.cplusplus.com/reference/stl/
------本文由网格布成员更新于2022/4/27
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）