【STL编程】【竞赛常用】【part 3】

【STL编程】【竞赛常用】【part 1】

【STL编程】【竞赛常用】【part 1】

【STL编程】【竞赛常用】【part 2】

【STL编程】【竞赛常用】【part 2】

【STL编程】【竞赛常用】【part 3】

11. list 双向链表容器

list双向链表容器在头文件中声明，它对任一位置元素的查找、插入及删除都具有高效的常数阶算法时间复杂度。

#include <bits/stdc++.h> //使用万能头文件，无需写#include <list>
using namespace std;

int main(){
    
    list<int> l;
    l.push_back(2); //尾部插入新元素，链表自动扩张
    l.push_back(2);
    l.push_back(9);
    l.push_back(12);
    l.push_back(12);
    l.push_back(4);
    l.push_back(4);
    l.push_back(6);
    // l.clear();//清空链表
    l.push_front(9); //头部插入新元素，链表自动扩张
    list<int>::iterator it;
    it = l.begin();
    it++;             //链表迭代器只能++或--操作，不能进行+n操作，因为list节点不是连续内存
    l.insert(it, 20); //当前位置插入新元素
    it++;
    l.erase(it);                              //删除迭代器位置上的元素
    for (it = l.begin(); it != l.end(); it++) //正向遍历
        cout << *it << " ";
    cout << endl;
    l.remove(12);                     //删除所有值为12的元素
    l.pop_front();                    //删除链表首元素
    l.pop_back();                     //删除链表尾元素
    it = find(l.begin(), l.end(), 4); //查找元素值为4
    if (it != l.end())
        cout << "find " << *it << endl;
    l.sort();                                 //升序排列
    l.unique();                               //删除连续重复元素（只保留一个）
    for (it = l.begin(); it != l.end(); it++) //正向遍历
        cout << *it << " ";
    cout << endl;
    return 0;
}
/* 9 20 2 9 12 12 4 4 6 find 4 2 4 9 20 */

结构体：

#include <bits/stdc++.h>
using namespace std;

struct student{
    
    char *name;
    int age;
    char *city;
};

int main(){
    
    student s[] = {
    
            {
    "张三", 18, "浙江"},
            {
    "李四", 19, "北京"},
            {
    "王二", 18, "上海"}};
    list<student> l;
    l.push_back(s[0]); //插入元素
    l.push_back(s[1]);
    l.push_back(s[2]);
    student x = {
    "刘四", 19, "新疆"};
    l.push_front(x);        //插入到首位，复杂度为O(1)
    l.insert(l.begin(), x); //插入任意位置,时间复杂度O(1)
    // l.pop_front();//删除首元素
    // l.pop_back();//删除尾元素
    l.erase(l.begin());
    // l.erase(l.begin(),l.end());//删除区间的元素
    for (list<student>::iterator i = l.begin(); i != l.end(); i++)
        cout << (*i).name << " " << (*i).age << " " << (*i).city << "\n";
    return 0;
}
/* 刘四 19 新疆 张三 18 浙江 李四 19 北京 王二 18 上海 */

list链表归并例程

#include <bits/stdc++.h>
using namespace std;

void print(list<int> l){
    
    list<int>::iterator i;
    for (i = l.begin(); i != l.end(); i++)
        cout << *i << " ";
    cout << endl;
}

int main(){
    
    list<int> l1;
    for (int j = 10; j >= 0; j--)
        l1.push_back(j);

    list<int> l2;
    list<int>::iterator ii;
    l2.splice(l2.begin(), l1); //将l1的全部元素归并到L2，L1清空
    ii = l2.begin()++;
    l1.splice(l1.begin(), l2, ii); //将l2的ii位置的元素归并到l1，l2原元素删除
    print(l1);
    print(l2);
    // swap(l1,l2);//交换l1,l2
    l1.push_back(8);
    l1.push_back(8);
    l1.push_back(35);
    l1.unique(); //除去连续重复元素
    l2.push_back(30);
    l1.sort(); //排序
    l2.sort();
    print(l1);
    l2.merge(l1); // L1归并到l2，两链表需排序,具体见后面的见归并算法merge
    print(l2);
    return 0;
}

12. stack 堆栈容器

堆栈类似于一个一端开口、一端封闭的容器，开口端称为栈顶（Stack Top），封闭端称为栈底（Stack Bottom），元素的插入和删除只能在栈顶操作。堆栈的元素插入称为入栈，元素的删除称为出栈。堆栈的主要特点是“后进先出”（Last In First Out），即后入栈的元素先出栈。每次入栈的元素都放在原当前栈顶元素之上，成为新的栈顶元素，每次出栈的元素都是原当前栈顶元素

参考我的数据结构教程：
2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】

方法	解释
empty()	堆栈为空则返回真
pop()	移除栈顶元素
push()	在栈顶增加元素
size()	返回栈中元素数目
top()	返回栈顶元素

#include <bits/stdc++.h> 
using namespace std;
#define STACK_SIZE 100

int main(){
    
    stack<string> s;
    s.push("aaa"); //入栈
    s.push("bbb");
    s.push("ccc");
    if (s.size() < STACK_SIZE) //可限制大小
        s.push("68");
    cout << s.size() << endl; //输出栈内元素个数
    while (!s.empty()) {
       //当栈不为空
        cout << s.top() << endl; //出栈
        s.pop();                 //出栈
    }
    return 0;
}

结果：

4
68
ccc
bbb
aaa

13. queue 队列容器

方法	解释
push()	在队尾插入一个元素
pop()	删除队列第一个元素
size()	返回队列中元素个数
empty()	如果队列空则返回true
front()	返回队列中的第一个元素
back()	返回队列中最后一个元素

#include <bits/stdc++.h> 
using namespace std;

int main(){
    
    queue<int> q;
    q.push(3); //入队
    q.push(5);
    q.push(2);
    cout << "The number of elements is:" << q.size() << endl;
    cout << q.back();  //取队尾元素
    while (!q.empty())  {
     //当队列未空
        cout << q.front() << endl; //打印队首元素
        q.pop();                   //出队
    }
    return 0;
}

结果：

The number of elements is:3      
23
5
2

14. deque 双端队列容器

deque在头文件<deque>中声明，它是一种双向开口的连续线性空间，可以高效地在头、尾两端插入和删除元素。它的时间复杂度为O(1)，考虑容器元素的内存分配策略和操作性能时，deque比vector有优势。

方法	解释
push_back(element);	容器尾部添加一个数据
push_front(element);	容器头部插入一个数据
pop_back();	删除容器最后一个数据
pop_front();	删除容器第一个数据
begin();	返回容器中第一个元素的迭代器。
end();	返回容器中最后一个元素之后的迭代器。
rbegin();	返回容器中倒数第一个元素的迭代器。
rend();	返回容器中倒数最后一个元素之后的迭代器。
cbegin();	返回容器中第一个元素的常量迭代器。
cend()；	返回容器中最后一个元素之后的常量迭代器。
size();	返回容器中元素的个数
empty();	判断容器是否为空
insert(pos,elem);	在pos位置插入一个elem元素的拷贝，返回新数据 的位置。
insert(pos,n,elem);	在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);	在pos位置插入[beg,end)区间的数据，无返回值
clear();	移除容器的所有数据
erase(beg,end);	删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);	删除pos位置的数据，返回下一个数据的位置。

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    deque<string> d;  //定义一个包含string类型的deque
    d.push_back("A"); //尾部插入元素
    d.push_back("B");
    d.push_back("C");
    d.push_front("X"); //头部插入元素
    d.push_front("Y");
    // d.pop_front();//删除首元素
    // d.pop_back();//删除尾元素
    // d.erase(d.begin()+1);//删除指定位置元素
    // d.clear();//删除所有元素
    d.insert(d.end() - 2, "O"); //指定位置插入

    reverse(d.begin(), d.end());       //反转元素顺序
    for (int i = 0; i < d.size(); i++) //数组方式访问
        cout << d[i] << " ";
    cout << endl;

    swap(d[1], d[2]);          //两元素交换
    deque<string>::iterator i; //迭代器访问
    for (i = d.begin(); i != d.end(); i++)
        cout << *i << " ";
    cout << endl;

    cout << "\nDeque is empty " << d.empty();
    cout << "\nDeque element number is " << d.size();
    cout << "\nDeque's first element is " << d.front();
    cout << "\nThe last element of Deque is " << d.back();
    return 0;
}

结果：

C B O A X Y 
C O B A X Y

Deque is empty 0
Deque element number is 6
Deque's first element is C
The last element of Deque is Y

15. priority_queue 优先队列容器

priority_queue优先队列容器在头文件<queue>中声明，与队列容器一样，只能从队尾插入元素，从队首删除元素。其一般形式为priority_queue<Type,Container, Functional>，其中Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。

Container必须是用数组实现的容器，例如vector、deque等，但不能用 list，STL里面默认用的是vector。如果后面两个参数采用默认设置，优先队列容器就是大顶堆（降序），队首元素最大。可以重载运算符来重新定义比较规则。

从小到大排列，让小的元素优先出队的基本写法如下。
priority_queue<int,vector<int>,greater<int> >q;
从大到小排列，让大的元素优先出队的基本写法如下。(默认)
priority_queue<int,vector<int>,less<int> >q;

#include <bits/stdc++.h>
using namespace std;

struct cmp{
    
    bool operator()(const int &a, const int &b) {
    //重载"()"操作符
        return a > b; //由小到大排列用">"，否则用"<"
    }
};

int main(){
    
    priority_queue<int, vector<int>, cmp> que1;
    //priority_queue<int, vector<int>, greater<int>> que1;
    priority_queue<int, vector<int>> que2;
    int a[] = {
    1, 3, 4, 2, 5, 0, 6};
    for (int i = 0; i < 7; i++){
    
        que1.push(a[i]);
        que2.push(a[i]);
    }
    cout << "que1:";
    while (!que1.empty()){
    
        cout << que1.top() << " ";
        que1.pop();
    }
    cout << endl
         << "que2:";
    while (!que2.empty()){
    
        cout << que2.top() << " ";
        que2.pop();
    }
    return 0;
}
/* que1:0 1 2 3 4 5 6 que2:6 5 4 3 2 1 0 */