stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)

STL常用算法介绍

STL(Standard Template Library)是C++标准库的一个庞大组成部分，提供了大量的常用算法，容器以及迭代器等等。这些工具都可以被拿来用来解决大部分的计算问题。其中stl常用算法主要包括排序算法和非变序型队列，下面进行详细讲解。

stl排序算法

STL提供了丰富的排序算法模板，可以直接拿来使用，无需重新实现。以下是一些常用的排序算法介绍：

1. sort()算法模板

sort()是最常用的排序算法模板，它可以对任意形式的数据类型进行排序，简单易用。如下是sort()模板的定义

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

我们可以用以下示例来说明sort()的用法

#include<algorithm>
#include<iostream>
using namespace std;

int main(){
    int a[5]={3,1,4,5,2};
    sort(a,a+5);
    for(int i=0;i<5;i++)
        cout<<a[i]<<" ";
    return 0;
}

输出为：1 2 3 4 5

2. stable_sort()算法模板

stable_sort()算法模板为在sort()的基础上，可以满足排序后具有稳定性，即对于相等的元素，排序前后的相对位置不变。但是由于实现过程较为复杂，速度较慢。使用稳定的排序，可以不改变相等的元素相对顺序。

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

我们可以使用以下示例来说明stable_sort()的用法

#include<algorithm>
#include<iostream>
using namespace std;

struct Person{
    int age;
    string name;
    bool operator<(const Person &p) const{
        return age<p.age;
    }
};

bool comp(const Person &a, const Person &b){
    return a.age<b.age;
}

int main(){
    Person a[5]={{18,"Tony"},{20,"Jack"},{18,"Ben"},{21,"Lucy"},{20,"Marry"}};
    stable_sort(a,a+5,comp);
    for(int i=0;i<5;i++)
        cout<<a[i].name<<", "<<a[i].age<<endl;
    return 0;
}

输出为

Tony, 18
Ben, 18
Jack, 20
Marry, 20
Lucy, 21

非变序型队列

STL常用的非变序型队列包括deque，queue，stack三种类型。这些容器分别实现了不同的数据结构，可以满足不同的需求。

1. deque(双端队列)

deque支持常数时间的随机存取，并允许在两端进行插入和删除操作。由于deque只会损失渐进常数因子的速度，并不会因为元素数量的增加而变得耗时。如下是一个deque的使用示例。

#include<iostream>
#include<deque>
using namespace std;

int main(){
    deque<int> d;
    d.push_back(3); //在队列尾部插入元素3
    d.push_front(2); //在队列头部插入元素2
    d.push_back(4);
    d.pop_front(); //从队列头部删除元素2
    d.pop_back(); //从队列尾部删除元素4

    for(int i=0;i<d.size();i++)
        cout<<d[i]<<" "; //输出当前容器中元素
    return 0;
}

输出为：3

2. queue(队列)

queue是一种典型的先进先出(FIFO)数据结构，它提供了顺序插入和删除元素的一种简单方式，被广泛应用于模拟等领域。下面是queue的使用示例。

#include<iostream>
#include<queue>
using namespace std;

int main(){
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.pop(); //弹出队列头部元素
    cout<<q.front(); //输出队列头部元素
    return 0;
}

输出为：2

3. stack(栈)

stack是一种后进先出(LIFO)的容器，它支持将元素压入栈顶，弹出栈顶元素，以及获取当前栈顶元素等操作。下面是stack的使用示例。

#include<iostream>
#include<stack>
using namespace std;

int main(){
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.pop(); //弹出栈顶元素
    cout<<s.top(); //输出当前栈顶元素
    return 0;
}

输出为：2

总结

本篇攻略详细介绍了STL常用算法排序算法和非变序型队列，包括sort()算法模板，stable_sort()算法模板，deque(双端队列)，queue(队列)和stack(栈)。通过实例讲解，让读者更好地理解和灵活运用这些常用算法和容器，可以为后续算法和数据结构的学习打下良好的基础。