#include <vector>

Vector 包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度( O(1) ) 内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度( O(n) )

声明

  • vector < int > a;                            声明一个名字是a的动态数组
  • vector < int > a(10);                     a里有10个值为0的元素
  • vector < int > a(10,6);                  a里有10个值为6的元素
  • vector < int > a[MAXN];              a是一个二维的动态数组
  • vector < MyType > a;                  a里存放的是MyType类型

size/empty

size函数返回的是vector的实际长度(包含元素的个数)。调用方法 a.size();

empty函数判断vector是否为空,如果为空返回 true 否则返回false。调用方法 :a.empty();

STL里所有的容器都支持这两个函数,含义也都相同。

clear

把vector清空,a.clear();

push_back/pop_back

a.push_back(x)   在vector a末尾添加一个元素 x.

a.pop_back()  删除vector a的最后一个元素.

front/back

a.front()  返回vector a的第一个元素,相当于a[0].

a.back()  返回vector a的最后一个元素,相当于a[n-1] (n=a.size()).

insert/erase

插入和删除操作的时间复杂度都是O(n),比较低效,不经常用。

begin/end

begin函数返回指向vector中第一个元素的迭代器 。*a.begin() 与 a[0]作用相同。

end函数返回vector的尾部的一个迭代器,*a.end() 与 a[n] 相同 (n=a.size()),都是越界访问。

迭代器(iterator)

迭代器就像STL容器的“指针”,可以用“ * ”操作符解除引用。

一个保存int类型的vector的迭代器的声明方法为:

vector<int>::iterator it;  声明了一个名字为 it 的vector迭代器

vector的遍历:

方法一:用迭代器遍历

vector<int> a;
for(int i=1;i<=10;i++) a.push_back(i);
vector<int>::iterator it;
for(it=a.begin();it!=a.end();it++)
    cout<<*it<<endl;

方法二:用c++11里的 auto

vector<int> a;
for(int i=1;i<=10;i++) a.push_back(i);
for(auto it:a)
    cout<<it<<endl;

reverse

reverse函数的头文件是#include<algorithm>

reverse函数可以把vector里所有的元素倒置。时间复杂度是O(n).

reverse(a.begin(),a.end());

reverse函数也可以用来倒置string字符串。

sort

对动态数组排序类似于数组

vector<int> a;
sort(a.begin(),a.end());//从小到大排序

从大到小需要重载一个cmp函数

bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    vector<int> a;
    sort(a.begin(),a.end(),cmp);
}

综合用法:

vector<int> v;
v.push_back(3);
v.push_back(2);
v.push_back(4);
v.push_back(1);
v.push_back(5);
for(auto it:v)
    cout<<it<<" ";
cout<<endl;

cout<<"size: "<<v.size()<<endl;

sort(v.begin(),v.end());//排序
for(auto it:v)
    cout<<it<<" ";
cout<<endl;

reverse(v.begin(),v.end());//翻转
for(auto it:v)
    cout<<it<<" ";
cout<<endl;

#include<stack> 栈

先进后出(FILO)

声明

stack<Type> s; //定义栈,Type为类型,如int、double、char、string或是自己定义的结构体类型

push/pop

s.push(x); //入栈,把x放到栈顶

s.pop(); //出栈,删除栈顶元素,不返回值

top

s.top(); //返回栈顶元素的值,但不会删除

遍历栈通常先用top取到栈顶元素,然后pop出栈。

stack<int> st;
for(int i=1;i<=10;i++) st.push(i);
while(st.size())
{
    int p = st.top();
    st.pop();
    cout<<p<<endl;
}

#include<queue> 队列

先进先出(FIFO)

声明

queue<Type> que;//定义队列,Type为类型,如int、double、char、string或是自己定义的结构体类型

push/pop

que.push(x);//入队,把x放到队列, O(1)

que.pop(); //出队,删除队首元素,不返回值, O(1)

front/back

que.front();//返回队首元素,不会删除, O(1)

que.back();//返回队尾元素,不会删除, O(1)

遍历队列和遍历栈的方法类似,先用front取到队首元素,然后pop出队。

queue<int> que;
for(int i=1;i<=10;i++) que.push(i);
while(que.size())
{
    int p = que.front();
    que.pop();
    cout<<p<<endl;
}

优先队列priority_queue

最大值优先级队列、最小值优先级队列 // 谁的值最大 或 最小 放在队头

头文件也是#include<queue>

声明

  • priority_queue<int> que; //默认是最大值优先级队列
  • priority_queue<int,vector<int>,less<int>  > que; 与默认的相同
  • priority_queue<int,vector<int>,greater<int>  > que;//最小值优先级队列

push/pop/top

que.push(x); //入队,把x放到队列, O(log n)

que.pop();//出队,删除队首元素,不返回值, O(log n)

que.top();//返回堆顶元素(优先级最高的元素),与queue里的front()做好区分

结构体优先队列

当优先队列中存放的是我们自己定义的结构体时

方法一:重载 “<”(小于号).

struct point
{
    int id,x,y;
    friend bool operator<(const point &a,const point &b)//按照id的大小规定优先级
    {
        return a.id>b.id;
    }
};
int main()
{
    priority_queue<point> que;
    que.push(point{2,3,1});
    que.push(point{5,2,3});
    que.push(point{3,2,2});
    que.push(point{1,5,6});
    que.push(point{4,2,4});
    while(que.size())
    {
        point p = que.top();
        que.pop();
        cout<<"id:"<<p.id<<" "<<p.x<<" "<<p.y<<endl;
    }
}

方法二:重载”()”运算符

struct point
{
    int id,x,y;
};
struct cmp1
{
    bool operator() (const point a,const point b) const//按照id的大小规定优先级
    {
        return a.id>b.id;
    }
};
struct cmp2
{
    bool operator() (const point a,const point b) const//按照x的大小规定优先级
    {
        return a.x>b.x;
    }
};
struct cmp3
{
    bool operator() (const point a,const point b) const//按照x+y的值规定优先级
    {
        return a.x+a.y>b.x+b.y;
    }
};
// ...
int main()
{
    priority_queue<point,vector<point>,cmp1> que;
    priority_queue<point,vector<point>,cmp2> q2;
    priority_queue<point,vector<point>,cmp3> q3;
    que.push(point{2,3,1});
    que.push(point{5,2,3});
    que.push(point{3,2,2});
    que.push(point{1,5,6});
    que.push(point{4,2,4});
    while(que.size())
    {
        point p = que.top();
        que.pop();
        cout<<"id:"<<p.id<<" "<<p.x<<" "<<p.y<<endl;
    }
}

#include<deque> 双端队列

双端队列 deque 是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与 vector 相比,deque在头部增删元素只需要 O(1) 的时间;与 queue 相比,deque可以像数组一样支持随机访问。

#include<set> 集合

头文件 set 主要包括 set 和 multiset 两个容器。两个容器都是有序的,即存入容器就自动排序。

set 容器里的元素不能重复,multiset容器允许重复。两者内部都是用红黑树实现的,所支持的函数基本相同。

声明

  • set<int> s;
  • set<string> s;
  • multiset<double> s;
  • set<MyType> s; // 集合里存放的是自定义的数据类型

因为set和multiset容器里存放的元素是有序的,所以当我们存放自己定义的结构体的时候,需要和优先队列一样,重载 ‘<’ (小于号)运算符。

size/empty/clear

与 vector 类似。

insert/erase/count

s.insert(x); //把一个元素 x 插入到 s 中,时间复杂度是 O(log n)。

s.erase(it); // it 是一个迭代器,从 s 中删除迭代器 it 指向的元素,时间复杂度是 O(log n)。

s.erase(x); // x 是一个元素,从 s 中删除所有等于 x 的元素,时间复杂度是 O(k + log n),k是被删掉元素的个数

s.count(x);// 返回从 s 中所有等于 x 的元素个数。时间复杂度是 O(k + log n),k是元素x的个数。

find

s.find(x);// 在集合 s 中查找等于 x 的元素,返回指向该元素的迭代器。如果不存在x,则返回s.end()。时间复杂度是 O(log n)。

lower_bound/upper_bound

这两个函数的用法和 find 类似。查找条件有一点不同,时间复杂度是 O(log n)。

s.lower_bound(x);//查找大于等于 x 的元素中最小的一个,并返回指向该元素的迭代器。

s.upper_bound(x);//查找大于 x 的元素中最小的一个,并返回指向该元素的迭代器。

#include<map> 映射

map容器是一个键值对 key-value 的映射,也是基于红黑树实现的,所以map的大部分操作的时间复杂度都是O(log n)。

声明

map<key_type,value_type> mp;

例如:

  • map<int,int> mp;
  • map<string,int> mp;
  • map<long long,bool> mp;
  • map< pait<int,int> ,vector<int> > mp;

如果map里的key_type类型是自定义的结构体类型,必须重载 ‘<’ (小于号)运算符。

[ ] 操作符

map常用的就这一个操作符。

例如根据学生姓名找对应学号的问题。

我们只需要定义一个key是string,value是int的映射。 map<string,int> sno;

起初标记的时候可以这样写:sno["张三"] = 10001;

当我们需要 “张三” 的学号时就可以直接使用 sno["张三"]

unordered_map

unordered_map 是基于 Hash 的容器,所以时间复杂度是O(1)。略快于传统的 map 。使用方法和 map 基本相同。


一个好奇的人