迭代器

迭代器是一个变量,相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。

unique

unique\text {unique} 是STL比较实用的一个函数。用于“去除”容器内相邻的重复的元素(只保留一个)。这里说的去除并不是真正将容器内的重复元素删去,只是把重复的元素移到容器最后,但是依然在容器内。 对于数组而言返回去重后最后一个元素的指针,而其他容器则是返回去重后最后一个元素的迭代器。

用法举例

因为是去除相邻的重复元素,因此通常使用前容器应该要是有序的。

数组:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  int a[6] = {1,1,4,6,6,7};
  int *p = unique(a,a+6);
  cout << &a[4] << endl;
  cout << p << endl;
  cout << p - a <<endl;
  for(int i = 0;i < p-a;i++)
      cout << a[i] << endl;
  return 0;
}

vector

vector\text {vector}可以看成是什么都可以放进去的线性表。

用法:

vector<int>v;//vector元素为 int 型  
vector<int>::iterator it;//定义一个迭代器

v.push_back()    //在数组的最后添加一个数据
v.pop_back()     //去掉数组的最后一个数据 v.front()     //返回第一个元素(栈顶元素)
v.begin()        //得到数组头的指针,用迭代器接受
v.end()          //得到数组的最后一个单元+1的指针,用迭代器接受
v.clear()        //移除容器中所有数据
v.empty()        //判断容器是否为空
v.erase(pos)     //删除pos位置的数据
v.erase(beg,end) //删除[beg,end)区间的数据
v.size()         //回容器中实际数据的个数v.insert(pos,data) //在pos处插入数据

deque

deque\text {deque} 是双端队列STL,是一种两端都可以进出元素的结构。

用法:

deque<int> d;
d.push_front(x);    //双端队列头部增加一个元素X
d.push_back(x);     //双端队列尾部增加一个元素X
d.pop_front();      //双端队列头部弹出一个元素X
d.pop_back();       //双端队列尾部弹出一个元素X
d.clear();          //清空双端队列中元素
d.empty();          //队列中是否有元素
d.size();           //队列中元素个数
d.front();          //队列中头部元素
d.back();           //队列中尾部元素
d.begin();          //指向头部元素
d.end();            //指向尾部元素

stack

stack\text {stack}是栈STL,是一种先进后出的结构。

用法:

stack<int> s;
s.empty();	//栈中是否有元素
s.size();	//栈中元素个数
s.pop();	//弹出栈顶元素
s.top();	//反回栈顶元素
s.push(x);  //栈中压入x元素

queue

queue\text {queue} 是队列STL,是一种先进先出的结构。

用法:

q.empty()// 如果队列为空返回true,否则返回false
q.size() // 返回队列中元素的个数
q.pop()  //删除队列首元素
q.front()  // 返回队首元素的值 
q.push(X) //在队尾压入新元素X
q.back() //返回队列尾元素的值  

priority_queue

priority_queue\text {priority}\_\text{queue} 是优先队列STL,优先队列是队列的一种,不过它可以按照自定义的一种方式(数据的优先级)来对队列中的数据进行动态的排序,每次的 push\text {push}pop\text {pop} 操作,队列都会动态的调整,以达到我们预期的方式来存储。

例如,将元素 5 3 2 4 6\text {5 3 2 4 6} 依次 push\text {push} 到优先队列中,规定顺序为从大到小并输出,输出顺序为 6 5 4 3 2\text {6 5 4 3 2}

定义

priority_queue<int> p;//最大值优先,是大顶堆一种简写方式
priority_queue<int,vector<int>,greater<int>>q1;//最小值优先,小顶堆
priority_queue<int,vector<int>,less<int> >q2;//最大值优先,大顶堆

//其中第一个参数是数据类型,第二个参数为容器类型。第三个参数为比较函数。

在使用时,我们会有很多时间用到根据结构体的某一个元素进行排序,下面给出定义结构体的优先级比较方式

struct node
{
    string name;
    int price;
    friend bool operator< (node a, node b)
    {
        return a.price < b.price; // 相当于less,这是大顶堆,反之则是小顶堆,最大值优先
    }
} stu; //定义结构体变量

//这样直接可以:
priority_queue<node > q;

可以将比较运算符外置,方法如下

struct node
{
    string name;
    int price;
} stu; //定义结构体变量

struct cmp
{
    bool operator () (node a, node b) // 重载括号
    {
        return node.price < node.price; // 相当于less,大顶堆
    }
};

3.常用操作:

q.push(x) //将x加入队列中,即入队操作

q.pop() //出队操作(删除队列首元素),只是出队,没有返回值

q.top() //返回第一个元素(队首元素)优先队列的队首用top,而普通队列的队首用front

q.size() //返回栈队列中的元素个数

q.empty() //当队列为空时,返回 true

这里放下 P1090 合并果子 的代码,方便理解使用 \text {priority_queue}

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
    int a,b,x,y,ans=0;
    read(a);
	For(i,0,a-1) read(b),q.push(b);
	For(i,1,a-1){
		x=q.top();q.pop();
         y=q.top();q.pop();
		q.push(x+y);ans+=x+y;
	}
	write(ans);
}

set

介绍

set\text {set} 是集合STL\text {STL}set\text {set} 是一个内部自动有序且不含重复元素的容器。

set最主要的作用是自动去重并按升序排序

用法:

1.set的定义

set<typename> name;
//这里的typename可以是任何基本类型
//举例:
set<int> name;
set<double> name;
set<char> name;
set<node> name; //node是结构体的类型

2. set 容器内元素的访问

//(重点)set 只能通过迭代器(iterator)访问
set<typename>::iterator it;

举例:

#include <bits/stdc++.h>
using namespace std;
int main() {
    set<int> st;
    st.insert(3);   //insert(x)将x插入set中
    st.insert(5);
    st.insert(2);
    st.insert(3);
    for(set<int>::iterator it = st.begin(); it != st.end(); it++) {
        printf("%d", *it);
    }
}

3.set常用函数

  1. insert(x)\text {insert(x)}
insert(x);         //insert(x)可将 x 插入 set 容器中,并自动递增排序和去重,时间复杂度O(logN)
  1. find(value)\text {find(value)}
find(value);       //find(value)返回 set 中对应值为 value 的迭代器,时间复杂度为O(logN)
//用法:
set<int>::iterator it = st.find(2); //在set中查找2,返回其迭代器
printf("%d\n", *it);
//以上两句也可以直接写成printf("%d\n", *(st.find(2)));
  1. $ \text {erase()}$
erase();
//erase()有两种用法:删除单个元素,删除一个区间内的所有元素
// 1. 删除单个元素
//删除单个元素的方法有两种
//st.erase(it), it为所需要删除元素的迭代器。时间复杂度为O(1)
st.erase(st.find(x));//利用find()函数找到x,然后用erase删除它

//st.erase(value), value为所需要删除元素的值。时间复杂度为O(logN)
st.erase(x);  //删除set中值为x的元素


// 2.删除一个区间内的所有元素
//st.erase(first, last)可以删除一个区间内的所有元素
//first为所需要删除区间的起始迭代器,last则为所需要删除区间的末尾迭代器的下一地址
//即删除[first, last), 时间复杂度为O(last - first)
set<int>::iterator it1 = st.find(x);
set<int>::iterator it2 = st.find(y);
st.erase(it1, it2); //删除元素x至y之间的元素(包括x和y)
  1. size()\text {size()}
int x=size();//size()用来获得set内元素的个数,时间复杂度为O(1)
  1. clear()\text {clear()}
set<int> s;
s.clear(); //清空set

multiset

set\text {set}multiset\text {multiset} 会根据特定的排序原则将元素排序。两者不同之处在于, multiset\text {multiset} 允许元素重复,而 set\text {set} 不允许重复,其他操作和 set\text {set} 都差不多的。

map

说白了就是一个动态的桶。

函数:

//应该只有这个要用到。。
map<int,int> mp;
mp.clear();//map初始化

unordered_map

使用方法和map\text {map}完全一样!

但是由于底层原理不同,它的查询是O(1)\text {O(1)}的,而map\text {map}的查询却是O(log n)\text {O(log n)}的。

传闻这玩意要C++11才能用 ——假的!

一切都在标准C++范围内。

bitset

可以看作一个支持二进制数,每 位占用 个字节,并支持基本的位运算。

类型可以用 和整数初始化(整数转化成对应的二进制)。

举例:

bitset<23>bit (string("11101001"));
cout<<bit<<endl;
bit=233;
cout<<bit<<endl;

输出:

00000000000000011101001
00000000000000011101001

这应该是用的最多的东西了,别的函数还有很多,这里就省略了(觉得没什么用。

binary_search

函数模板:

binary_search(arr[], arr[]+size, indx);

参数说明:
arr[]\text {arr[]} :数组首地址
size\text {size}:数组元素个数
indx\text {indx}:需要查找的值
函数功能: 在数组中以二分法检索的方式查找,若在数组(要求数组元素非递减)中查找到 indx\text {indx} 元素则真,若查找不到则返回值为假。

lower_bound

lower_bound(begin, end, num)\text {lower}\_\text{bound(begin, end, num)} :从数组的 begin\text {begin} 位置到 end - 1\text {end - 1}位置二分查找第一个大于或等于 num\text {num} 的数字,找到返回该数字的地址,不存在则返回 end\text {end} 。通过返回的地址减去起始地址begin\text {begin} ,得到找到数字在数组中的下标。

int num[n+1];
pos=lower_bound(num+1,num+n+1,y)-num;    //返回数组num[1]到num[n]的元素中第一个大于或等于被查数的值的下标

upper_bound

upper_bound( begin,end,num)\text {upper}\_\text{bound( begin,end,num)} :从数组的 begin\text {begin} 位置到 end - 1\text {end - 1} 位置二分查找第一个小于 num\text {num} 的数字,找到返回该数字的地址,不存在则返回 end\text {end} 。通过返回的地址减去起始地址 begin\text {begin} ,得到找到数字在数组中的下标。

int num[n+1];
pos=upper_bound(num+1,num+n+1,y)-num;    //返回数组num[1]到num[n]的元素中第一个大于被查数的值的下标

reverse

reverse()\text {reverse()} 函数可以对字符串进行反转操作。

容器类型的要用 begin()\text {begin()}end()\text {end()} 来指定反转的区域,数组类型的直接用 int\text {int} 类型即可。

使用方法

  1. 交换 vector\text {vector} 容器中元素顺序
vector<int> v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值为1,2,3,4,5
  1. 交换 string\text {string} 字符串中元素的顺序
string str="hello";
reverse(str.begin(),str.end());//str结果为olleh
  1. 交换字符数组 char[]\text {char[]} 中元素的顺序
char a[101] = “hello world”;
reverse(a,a+strlen(a));
  1. 翻转一个数组
int a[5+1]={0,1,2,3,4,5};
reverse(a+1,a+n+1);

random_shuffle

random_shuffle()\text {random}\_\text {shuffle()} 函数可以随机打乱容器内元素,用法和 reverse()\text {reverse()} 相同。

int a[5+1]={0,1,2,3,4,5};
random_shuffle(a+1,a+n+1);

next_permutation

next_permutation\text {next}\_\text{permutation} 是全排列函数。

用法比较少,下面是用这个函数实现全排列的代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        int a[1000];
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        do{
            for(int i=0;i<n;i++)
                printf("%d ",a[i]);
            printf("\n");
        }while(next_permutation(a,a+n));
    }
    return 0;
}

注意事项(重要):

  1. 除开 vector\text {vector}string\text {string} 之外的STL容器都不支持 *(it+i) 的访问方式(这里 it\text {it} 是迭代器)
  2. 大多数STL都需要特定的头文件,但是万能头是全部都包含的,为了方便,也为了安全,请使用万能头。

后记

对于初学者来说,STL尽量不要使用,要理解STL实现的原理,STL只是用于简化代码的,而不是用来当算法学习的。

STL就像是一个个封装好的工具,可以任你挑选使用,但是你需要先知道,哪个工具适合于你,也需要学会使用工具,这篇文章则是更偏向于讲后者。