vector为"变长数组",长度根据需要自动改变的数组。有时候用普通数组会出现超时的问题,使用vector可以解决这种问题。
使用vector,需要使用头文件#include
vector<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;
(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 << " "; } }
(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后实现自动排序
#include
set name;
set数组定义set<typename> Arrayname[Arraysize - 1]
只能通过迭代器访问
#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内的元素实现自动递增排序,且自动去除了重复元素。
(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为映射,也是常见容器
可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)可以建立string到int型的映射
还可以解决:需要判断给定的一些数字在某个文件中是否出现过。按照正常思路,可以加一个布尔的hashTable[max_size],通过判断hashTable[x]为true还是false来确定是否出现过,但是可能会出现数字较大(有几千位)那么这个数组会开不了,就可以使用map将这些数字当成一些字符然后建立string到int的映射,使用时需加入头文件#include
map<typename1,typename2> mp;
map需要确定映射前的类型(键key)和映射后的类型(值)
如果是字符串到整型的映射,只能只要string而不能使用char数组:
map<string,int> mp;
map<set,string> mp;
(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