不定长数组:vector

vector就是一个不定长数组,并且封装了一些常用操作。vector是一个模板类,需要通过vector <int> a 这样的方式来定义。
常见的使用情况有vector <int> a[maxn],例如这样像一个二维数组,总元素数目有限,但开成二维数组会浪费太多空间导致mle的情况。这样用vector定义第一位的大小是确定的(不超过maxn),但第二维的大小不固定。

一、vector 的初始化:可以有五种方式,举例说明如下:

(1) vector<int> a(10); //定义了10个整型元素的向量(尖括号中为元素类型名,它可以是任何合法的数据类型),但没有给出初值,其值是不确定的。
(2) vector<int> a(10, 1); //定义了10个整型元素的向量,且给出每个元素的初值为1
(3) vector<int> a(b); //用b向量来创建a向量,整体复制性赋值
(4) vector<int> a(b.begin(), b.begin+3); //定义了a值为b中第0个到第2个(共3个)元素
(5) int b[7]={1, 2, 3, 4, 5, 9, 8};
vector <int> a(b, b+7); //从数组中获得初值

二、vector的部分操作

(1) a.push_back(5); //在a的最后一个向量后插入一个元素,其值为5
(2) a.pop_back(); //删除a向量的最后一个元素
(3) a.back(); //返回a的最后一个元素
(4) a.front(); //返回a的第一个元素
(5) a[i]; //返回a的第i个元素,当且仅当a[i]存在
(6) a.clear(); //清空a中的元素
(7) a.empty(); //判断a是否为空,空则返回ture,不空则返回false
(8) a.size(); //返回a中元素的个数;
(9) a.assign(b.begin(), b.begin()+3); //b为向量,将b的0~2个元素构成的向量赋给a
(10) a.assign(4,2); //是a只含4个元素,且每个元素为2
(11) a.erase(a.begin()+1, a.begin()+3); //删除a中第1个(从第0个算起)到第2个元素,也就是说删除的元素是左闭区右开。
(12) a.insert(a.begin()+1, 5); //在a的第1个元素(从第0个算起)的位置插入数值5
(13) a.insert(a.begin()+1, 3, 5); //在a的第1个元素(从第0个算起)的位置插入3个数,其值都为5
(14) a.insert(a.begin()+1, b+3, b+6); //b为数组,在a的第1个元素(从第0个算起)的位置插入b的第3个元素到第5个元素,同样是左闭右开。
(15) a.resize(10); //将a的现有元素个数调至10个,多则删,少则补,其值随机
(16) a.resize(10, 2); //将a的现有元素个数调至10个,多则删,少则补,其值为2
(17) a.reserve(100); //将a的容量扩充至100。这种操作只有在需要给a添加大量数据的时候才显得有意义,因为这将避免内存多次容量扩充操作(当a的容量不足时电脑会自动扩容,当然这必然降低性能)
(18) a.swap(b); //b为向量,将a中的元素和b中的元素进行整体性交换
(19) a == b; //b为向量,向量的比较操作还有!=,>=,<=,>,<(默认是比较字典序)

三、一些顺序访问,添加元素的方法和误区

(1) 顺序添加元素

vector <int> a;
    for (int i = 0; i < n; i++)
        a.push_back(i);

pushback当空间不足时会自动申请空间。

(2) 常见误区

vector <int> a;
    for(int i = 0; i < 10; i++)
        a[i] = i;
    //通过下标访问只能访问已存在的元素,对a[i]还是空的对象时不行。
    //如果声明vector时申请了容量且没有超出就可以:vector <int> a(100);

(3) vector的迭代器

for(vector<int>::iterator it = a.begin(); it != a.end(); it++)
    cout << *it << " ";

//我pys死都不用这个(大概吧)

四、一些重要算法

需要头文件algorithm
(1) sort(a.begin(), a.end()); //对a中的从a.begin()(包括它)到a.end()(不包括它)的元素进行从小到大排列,可以通过定义cmp定义排列逻辑。
(2) reverse(a.begin(), a.end()); //对a中的从a.begin()(包括它)到a.end()(不包括它)的元素倒置,但不排列,如a中元素为1,3,2,4,倒置后为4,2,3,1
(3) find(a.begin(), a.end(), 10); //在a中的从a.begin()(包括它)到a.end()(不包括它)的元素中查找10,若存在返回其在向量中的位置
(4) lower_bound(a.begin(), a.end(), x); //查找大于或等于x的第一个元素的位置。(lower_bound也可以用在数组上,upper_bound找第一个大于的位置。返回地址,-a得到下标)

参考《算法竞赛入门指南》,young0173的博客

队列:queue

先进先出,可以删除队首,在队尾插入元素的数据结构。模板类,需要如queue<int> q这样定义。

一、queue常用操作

(1) back(); //返回最后一个元素
(2) empty(); //如果队列空则返回真
(3) front(); //返回第一个元素
(4) pop(); //删除第一个元素
(5) push(); //在末尾加入一个元素
(6) size(); //返回队列中元素的个数
(7) empty(); //返回队列是否为空

二、优先队列priority_queue

我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。
适合用于维护不断有删除,插入元素的序列有序,比较常用,每次插入的时间复杂度为O(logn)
(1) 定义优先级

priority_queue<int> a; //对于基础数据类型默认是大顶堆
    //等同于 priority_queue<int, vector<int>, less<int> > a;
    
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆

(2) 对于自定义数据类型定义优先级

struct node //运算符重载<
    {
        int x, y;
        bool operator<(const node& a) const
        {
            if (a.x != x) return a.x > x; //大顶堆
            return a.y > y;
        }
    };
    priority_queue<node> q;

    q.push(node{ x,y });//插入node元素
    //等价于
    node a;
    a.x = x, a.y = y;
    q.push(a);

(3) 常用操作
front()变成了top(),其余操作与queue基本一致。

映射:map

map就是从键(key)到值(value)的映射。应为重载了[]运算符,可以当作高级版数组,也被称为“关联数组”。map对象是模板类,需要关键字和存储对象两个模板参数定义:map<string, int> m;

一、map插入元素

(1) 用insert插入pair数据

m.insert(pair<string, int>("Melo", 1));

(2) 用insert函数插入value_type数据(又臭又长没啥用)

m.insert(map<string, int>::value_type ("Melo",1));

(3) 像数组一样插入(最常用)

m["Melo"] = 1;

注意:以上三种用法,虽然都可以实现数据的插入,但是它们是有区别的,当然了第一种和第二种在效果上是完成一样的,用insert函数插入数据,在数据的插入上涉及到集合的唯一性这个概念,即当map中有这个关键字时,insert操作是插入不了的,但是用数组方式赋值会覆盖以前该关键字对应的值。

二、容量查询

(1) m.empty();
(2) m.size(); //键值数量

三、查找与删除

(1) 迭代器刪除

iter = m.find("123");
    m.erase(iter);

(2) 用关键字刪除

int n = m.erase("123"); //如果刪除了會返回1,否則返回0

(3) 用迭代器范围刪除

m.erase(m.begin(), m.end());
    m.clear(); //清空map

四、迭代器遍历map

//按key顺序遍历
    map<string, int>::iterator iter;
    for(iter = m.begin(); iter != m.end(); iter++)  
        cout << iter->first << "  " << iter->second << endl;  
    //按key值倒叙遍历只需要iterator,begin,end变成reverse_iterator,rbegin,rend即可
    map<string, int>::reverse_iterator iter;
    for(iter = m.rbegin(); iter != m.rend(); iter++)  
        cout << iter->first << "  " << iter->second << endl;

五、其他常用操作

(1) begin(); //返回指向map头部的迭代器
(2) clear(); //删除所有元素
(3) count(); //返回指定元素出现的次数
(4) empty(); //如果map为空则返回true
(5) end(); //返回指向map末尾的迭代器
(6) equal_range(); //返回特殊条目的迭代器对
(7) erase(); //删除一个元素
(8) find(); //查找一个元素
(9) insert(); //插入元素
(10) key_comp(); //返回比较元素key的函数
(11) lower_bound(); //返回键值>=给定元素的第一个位置
(12) max_size(); //返回可以容纳的最大元素个数
(13) rbegin(); //返回一个指向map尾部的逆向迭代器
(14) rend(); //返回一个指向map头部的逆向迭代器
(15) size(); //返回map中元素的个数
(16) swap(); //交换两个map
(17) upper_bound(); //返回键值>给定元素的第一个位置
(18) value_comp(); //返回比较元素value的函数

六、注意

(1) 按数组方式取值需要注意键值存在

cout << m[qwq] << endl; //键值qwq不存在时不会报错,但是会打印空白

(2) 如果只是当作数组使用,不需要对键值排序,尽量使用unordered_map。
比如只用来hash的时候,能用数组就别用unordered_map,能unordered_map别map。(被卡过)

集合:set

set就是数学上的集合,每个元素最多出现一次。set是模板类,需要按set <string> s这种方式定义。
set、map都是关联式容器。set内部是基于红黑树实现的。插入和删除操作效率较高,因为只需要修改相关指针而不用进行数据的内存上的移动。
set中的元素类型必须定义小于号,int,string 等C++自带元素类型已经帮我们定义好了小于号。int在set中从小到大排序,string在set中按字典序排序。
set常用于需要维护有序去重的序列,需要高效的插入删除时。

一、set的部分操作

(1) s.insert(x); //在set s中插入元素x,其中x的类型必须是声明该set时的类型,时间复杂度O(logn)
(2) s.erase(x); //在set s中删除元素x其中x的类型必须是声明该set时的类型,时间复杂度O(logn)
如果x不在该set中则在erase(x)时什么都不会删除。
(3) s.empty(); //返回s中元素个数是否为0,时间复杂度O(1)
(4) s.size(); //返回set大小(即元素个数),时间复杂度O(1)
(所有STL容器都有以上两个内置函数)
(5) s.clear(); //清空set,O(n)
(6) s.find(x); //查找set s中是否有x这个元素,如果有,则返回指向该元素的迭代器,否则返回end(),时间复杂度O(logn)

if(s.find(x) == s.end()); //没有这个元素
    if(s.find(x) != s.end()); //有此元素

注意返回的时x的迭代器,不能找到其位置(第几个是x),只能判断是否存在x。
(7) s.lower_bound(x); //返回指向大于(或等于)x的第一个元素的迭代器。

二、需要注意的地方

(1) set容器中只能存储键,是单纯的键的集合,其中键是不能重复的。
(2) set支持大部分的map的操作,但是set不支持下标的操作。
(3) set会自动帮你去重,如果不需要去重可以使用multiset(关键字可重复出现的set,用法和set基本一样)。
(4) 不需要排序时可以用unordered_set。对于unordered_set insert/find/erase的平均复杂度是O(1),但是最坏复杂度是O(n)的。
出现O(n)主要情况是哈希函数太烂了,导致很多不同元素的哈希值都相同,全是碰撞,这种情况复杂度会变成O(n)。但是这种情况一般不用担心,因为对于string,int以及double之类的基本数据类型,都有默认的哈希函数,而且默认的哈希函数足够好,不会退化到O(n)。如果是自定义的哈希函数,别写的太差了。
(个人感觉没有人会卡这个,问题不大)

日常感叹:迭代器这东西怎么这么傻逼。
参考:官方文档

栈:stack

栈(stack)是限制插入和删除只能在一个位置上进行的线性表,该位置在表的末端,叫做栈顶。添加元素只能在尾节点后添加,删除元素只能删除尾节点,查看节点也只能查看尾节点。添加、删除、查看依次为入栈(push)、出栈(pop)、栈顶节点(top)。形象的说,栈是一个先进后出(LIFO)表,先进去的节点要等到后边进去的节点出来才能出来。

一、常用操作

(1) empty() //堆栈为空则返回真
(2) pop() //移除栈顶元素
(3) push() //在栈顶增加元素
(4) size() //返回栈中元素数目
(5) top() //返回栈顶元素

update

使用emplace/emplace_back代替insert/push_back

emplace/emplace_back是c++11的新特性。
对vector来说,push_back()方法要调用构造函数和复制构造函数,这也就代表着要先构造一个临时对象,然后把临时的copy构造函数拷贝或者移动到容器最后面。
而emplace_back()在实现时,则是直接在容器的尾部创建这个元素,省去了拷贝或移动元素的过程。
vector中emplace_back替代push_back,map中用emplace替代insert可以加快速度并节约内存。
同时在比赛/做题中它方便了很多,时常会有在vecotor中插入一对数字的需求(每个询问的答案,每个节点的代价等等)。

vector< pair<int> <int> > v;
    v.push_back(make_pair(114, 514));
    v.emplace_back(114, 514);//可以少打几个字

auto关键字

看tourist代码时候学到的,很适合比赛写题用,方便快速
auto的自动类型推断发生在编译期,所以使用auto并不会造成程序运行时效率的降低。

int a = 5;
    auto t = a;//此时t为int类型

在使用STL容器时更加好用,可以快速使用迭代器,并且可以和for配合顺序遍历容器

//快速使用迭代器
    map<int, int> m;
    auto it = m.lower_bound(x);
    map<int, int>::iterator it = m.lower_bound(x);

    //这个例子是vector中记录了每个操作,顺序输出
    vector <pair<int, int>> ops;
    for (auto& op : ops)//这样op是顺序取出ops中的每个pair
        cout << op.first << " " << op.second << endl;
    //对比迭代器
    for (vector<pair<int, int>>::iterator it = ops.begin(); it != ops.end(); it++)
        cout << (*it).first << " " << (*it).second << endl;
    //方便写太多了,高下立判。这里嵌套pair的情况下(*it)不打括号的话还会ce...
最后修改:2022 年 03 月 06 日
如果觉得我的文章对你有用,请随意赞赏