文章目录
一、vector 的使用
1.定义
vector为"变长数组"，长度根据需要自动改变的数组。有时候用普通数组会出现超时的问题，使用vector可以解决这种问题。
使用vector,需要使用头文件#includevector<typename> name相当于一维数组name[SIZE],数组长度可以改变
typename可以是任何类型
基本类型：int,double,char,结构体等；也可以是STL标准容器，例如vector,set,queue,等，注意：如果typename也是容器的话，定义的时候要在>>符号之间加上空格，否则有可能会被当作移位操作，
vector<int> name;
vector<double> name;
vector<char> name;
vector<node> name;
2.vector容器内元素访问
（1）通过下标访问
和访问普通数组一样，vectorvi,vi[i]
数组下标是从0到vi.size()-1,访问这个范围外的元素可能出错
（2）通过迭代器访问
迭代器（iterator)可以理解为一种类似指针的东西，其定义是：
vector<typename>::iterator it;
可以通过*it访问vector内的元素
#include <bits/stdc++.h>
#include <vector>
using namespace std;
// struct node{
// };
// vector<int> name;
// vector<double> name;A
// vector<char> name;
// vector<node> name;
// vector<vector<int> >name; //二维变长数组
// vector<int>array[10]; //0~9每个都是一个一维变长数组
vector<int> vi;
int main()
{
for (int i = 1; i <= 5; i++)
{
vi.push_back(i);
}
// vi.begin()取首元素地址
vector<int>::iterator it = vi.begin();
for (int i = 0; i < 5; i++)
{
cout << *(it + i) << " "; // vi[i] 与 *(vi.begin() + i) 等价 }
// 迭代器++ -- 操作
for (vector<int>::iterator it = vi.begin(); it != vi.end(); it++)
{
cout << *it << " ";
}
}
3.常用函数
(1)push_back()
push_back(x) 就是在结尾添加一个元素x，时间复杂度为O(1)
for(int i = 1; i <= 5; i++){
v.push_back(i);
}
for(int i = 0; i < v.size(); i++){
cout << v[i] << " ";
}
（2）pop_back()；
删除尾元素，时间复杂度为O（1）；
for (int i = 1; i <= 5; i++)
{
v.push_back(i);
}
v.pop_back();
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
(3)size();
获得vector中元素个数，时间复杂度为O(1)
(4)clear();
用来清空所有元素，时间复杂度(N)
vector<int> vi;
for(int i = 1; i <= 3; i++){
vi.push_back(i);
}
cout << vi.size() << endl;
vi.clear();
cout << vi.size() <<endl;
（5）insert()
insert(it,x)向it插入元素x,时间复杂度为O(N)
for(int i = 1; i <= 5; i++){
v.push_back(i);
}
v.insert(v.begin() + 2, -1); //将-1插入v[2];
for(int i = 0; i < v.size(); i++){
cout <<v[i] <<" "; //1 2 -1 3 4 5
}
(6) erase();
有两种用法：删除单个元素或者删除一个区间内的所有元素
1）删除单个元素
erase(it)即为删除迭代器为it处的元素
for (int i = 5; i <= 9; i++)
{
v.push_back(i);
}
v.erase(v.begin() + 3); //删除v[3]
for (int i = 0; i < v.size(); i++)
{
cout << v[i]; // 5 6 7 9
}
2）删除一个区间内的所有元素
erase(first,last)即删除[first,last)内的所有元素
vector<int> v;
for(int i = 5; i <= 5; i++){
v.push_back(i);
}
v.erase(v.begin() + 1,v.begin() + 4); //删除v[1] v[2] v[3]
for(int i = 0; i< v.size(); i++){
cout << v[i] <<" "; // 5 9
}
v.end()就是尾元素下一个地址
二、set的使用
集合
set是一个内部自动有序且不含重复元素的容器。可以用于去除重复元素，元素放入set后实现自动排序
#include
1.set定义
set name;
set数组定义set<typename> Arrayname[Arraysize - 1]
2.set元素访问
只能通过迭代器访问
#include<iostream>
#include<set>
using namespace std;
int main(){
set<int> st;
st.insert(3);
st.insert(2);
st.insert(3);
st.insert(5);
//不支持 it < st,end();
for(set<int>::iterator it = st.begin(); it != st.end(); it++){
cout << *it;
}
}
set内的元素实现自动递增排序，且自动去除了重复元素。
3.set常用函数
（1）insert()
insert(x)可以将x插入set容器中，并自动递增排序和去重，时间复杂度为O（logN)
（2）find()
find(value)返回set中对应值value的迭代器，时间复杂度为O（logN)
（3）erase()
st.erase(value)删除值为value的元素，时间复杂度为0（logN)
st.insert(100);
st.insert(200);
st.erase(100);
for(set<int>::iterator it = st.begin(); it != st.end(); it++){
cout << *it <<" ";
} //200
删除一个区间
//erase()
st.insert(20);
st.insert(10);
st.erase(40);
st.erase(30);
set<int>::iterator it = st.find(30);
st.erase(it,st.end()); //删除it到结尾的元素
for(it = st.begin(); it != st.end(); it++){
cout << *it <<" ";
}
（4）size()
获取元素个数，O(1)
st.size();
(5)clear();
清除所有元素
st.clear();
三、map的使用
map为映射，也是常见容器
可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）可以建立string到int型的映射
还可以解决：需要判断给定的一些数字在某个文件中是否出现过。按照正常思路，可以加一个布尔的hashTable[max_size],通过判断hashTable[x]为true还是false来确定是否出现过，但是可能会出现数字较大（有几千位）那么这个数组会开不了，就可以使用map将这些数字当成一些字符然后建立string到int的映射，使用时需加入头文件#include
1.map的定义
map<typename1,typename2> mp;
map需要确定映射前的类型（键key)和映射后的类型（值）
如果是字符串到整型的映射，只能只要string而不能使用char数组：
map<string,int> mp;
map<set,string> mp;
2.map元素访问
（1）通过下标访问
对map<char,int> mp的map来说可以通过mp[‘c’]来访问它对应的整数
#include<iostream>
#include<map>
using namespace std;
int main(){
map<char,int> mp;
mp['c'] = 20;
mp['c'] = 66; //20被覆盖
cout<<mp['c']<<endl;
}
（2）通过迭代器访问
map<typename1,typename2>::iterator it;
map可以使用it->first来访问键，使用it->second来访问值
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> mp;
mp['c'] = 20;
mp['c'] = 66; // 20被覆盖
mp['a'] = 40;
mp['b'] = 30;
cout << mp['c'] << endl;
for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
}
3.常用函数
（1）find();
find(key)返回键值为key的映射，时间复杂度为log(N);
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> mp;
mp['c'] = 20;
mp['c'] = 66; // 20被覆盖
mp['a'] = 40;
mp['b'] = 30;
cout << mp['c'] << endl;
for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++)
{
cout << it->first << " " << it->second << endl;
}
}
（2）erase();
1)删除单个元素
mp.erase(it),it为需要元素的迭代器，时间复杂度为O（1）；
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
map<char,int>::iterator it = mp.find('b');
mp.erase(it);
for(map<char,int>::iterator it = mp.begin();it != mp.end(); it++){
cout <<it -> first <<"," <<it ->second <<endl;
}
mp.erase(key),key为预删除的键。时间复杂度为O（logN）
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
// map<char,int>::iterator it = mp.find('b');
mp.erase('b'); //删除键为b的映射，即2
for(map<char,int>::iterator it = mp.begin();it != mp.end(); it++){
cout <<it -> first <<"," <<it ->second <<endl;
}
2）删除一个区间的所有元素
mp.erase(first,last),其中first为要删除区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个位置。时间复杂度为O（last-first）
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
map<char,int>::iterator it = mp.find('b');
// mp.erase('b'); //删除键为b的映射，即2
mp.erase(it,mp.end()); //删除it之后的所有映射 即b 2和 c 3
for(map<char,int>::iterator it = mp.begin();it != mp.end(); it++){
cout <<it -> first <<"," <<it ->second <<endl;
}
（3)size();
获得map中映射的对数，时间复杂度为O(1)/font>
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
cout << mp.size(); //3
（4）clear()
清空map中的所有元素，复杂度为O(N)
map<char,int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
mp.clear();
cout<<mp.size();
4.map的作用
（1）建立字符（或字符串与整数之间的映射），使用map可以减少代码使用量
（2）判断大整数或者其他数据类型是否存在的问题
（3）字符串与字符串的映射也有可能出现
map的键与值是唯一的，如果一个键对应多个值可以使用multimap