STL之容器适配器（stack,queue和priority_queue）

用户9831583

发布于 2022-06-16 14:38:47

3940

发布于 2022-06-16 14:38:47

文章被收录于专栏：码出名企路

容器适配器主要有三种：

stack<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个后入先出的压入栈。

queue<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入先出的队列。可为它指定一个符合确定条件的基础容器。

priority_queue<T>：是一个封装了 vector<T> 容器的适配器类模板，默认实现的是一个对元素排序，保证最大元素总在队列最前面的队列。

1.stack

图展示了一个理论上的 stack 容器及其一些基本操作。只能访问 stack 顶部的元素；只有在移除 stack 顶部的元素后，才能访问下方的元素。

初始化：

std::stack<std::string> words;
//通过指定第二个模板类型参数，可以使用任意类型的底层容器
std::stack<std::string,std::list<std::string>> fruit;

std::list<double> values {1.414, 3.14159265, 2.71828};
std::stack<double,std::list<double>> my_stack (values);
//拷贝构造函数
std::stack<double,std::list<double>>copy_stack {my_stack}

基本操作：

top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()：弹出栈顶元素。
size()：返回栈中元素的个数。
empty()：在栈中没有元素的情况下返回 true。
emplace()：用传入的参数调用构造函数，在栈顶生成对象。
swap(stack<T> & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。

2.queue

图展示只能在容器的末尾添加新元素，只能从头部移除元素。

初始化：

std::queue<std::string> words;
//拷贝够咱函数
std::queue<std::string> copy_words {words}; 
//指定参数模板
std::queue<std::string, std::list<std::string>>words;

基本操作：

front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop()：删除 queue 中的第一个元素。
size()：返回 queue 中元素的个数。
empty()：如果 queue 中没有元素的话，返回 true。
emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
swap(queue<T> &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。

具体实例：

模拟超市运转的程序。结账队列的长度是超市运转的关键因素。

它会影响超市可容纳的顾客数——因为太长的队伍会使顾客感到气馁，从而放弃排队。

a)顾客类

#ifndef CUSTOMER_H
#define CUSTOMER_H

class Customer
{  
    //记录顾客结帐需要的时间
    protected:
        size_t service_t{};
    public:
        explicit Customer(size_t st=10):service_t{st}{}
    
    //每个顾客结帐时间不同，每过一分钟，调用一次
    Customer& time_decrement()
    {
        if(service_t >0)
            --service_t;//反映顾客结帐所花费的时间
        return *this;
    }
    bool done() const{return service_t==0;}
};
#endif

b)结帐类

#ifndef CHECKOUT_H
#define CHECKOUT_H
#include <queue>
#include "customer.h"

class Checkout
{
    //等待结帐的队列
    private:
        std::queue<Customer> customers;
    public:
        //向队列中添加新顾客
        void add(const Customer& customer){
            customers.push(customer);
            }
        size_t qleng() const {
            return customers.size();
        }

        void time_increment(){
            if(!customers.empty()){
                //顾客结帐完成，溢出
                if(customers.front().time_decrement().done())
                    customers.pop();
            }
        }

        bool operator<(const Checkout& other) const{
            return qleng() < other.qleng();
        }

        bool operator>(const Checkout& other) const{
            return qleng() > other.qleng();
        }
};
#endif

c)实现函数

#include <iostream>                    
#include <iomanip>                            
#include <vector>                              
#include <string>                        
#include <numeric>                      
#include <algorithm>                        
#include <random>                                
#include "customer.h"
#include "checkout.h"

using std::string;
using distribution = std::uniform_int_distribution<>;

// 输出时间
void histogram(const std::vector<int>& v, int min)
{
    string bar (60, '*');                          
    for (size_t i {}; i < v.size(); ++i)
    {
        std::cout << std::setw(3) << i+min << " "    
        << std::setw(4) << v[i] << " "            
        << bar.substr(0, v[i])                    
        << (v[i] > static_cast<int>(bar.size()) ? "...": "")
        << std::endl;
    }
}
int main()
{
    std::random_device random_n;
    // Setup minimum & maximum checkout periods - times in minutes
    int service_t_min {2}, service_t_max {15};
    distribution service_t_d {service_t_min, service_t_max};

    // Setup minimum & maximum number of customers at store opening
    int min_customers {15}, max_customers {20};
    distribution n_1st_customers_d {min_customers, max_customers};

    // Setup minimum & maximum intervals between customer arrivals
    int min_arr_interval {1}, max_arr_interval {5};
    distribution arrival_interval_d {min_arr_interval, max_arr_interval};

    size_t n_checkouts {};
    std::cout << "Enter the number of checkouts in the supermarket: ";
    std::cin >> n_checkouts;
    if (!n_checkouts)
    {
        std::cout << "Number of checkouts must be greater than 0. Setting to 1." << std::endl;
        n_checkouts = 1;
    }

    std::vector<Checkout> checkouts {n_checkouts};
    std::vector<int> service_times(service_t_max-service_t_min+1);

    // Add customers waiting when store opens
    int count {n_1st_customers_d(random_n)};
    std::cout << "Customers waiting at store opening: " << count << std::endl;
    int added {};
    int service_t {};

    while (added++ < count)
    {
        service_t = service_t_d(random_n);
        std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));
        ++service_times[service_t - service_t_min];
    }

    size_t time {};                                
    const size_t total_time {600};                
    size_t longest_q {};                          
    // Period until next customer arrives
    int new_cust_interval {arrival_interval_d(random_n)};

    // Run store simulation for period of total_time minutes
    while (time < total_time)                      
    {
        ++time;                                    
        // New customer arrives when arrival interval is zero
        if (--new_cust_interval == 0)
        {
            service_t = service_t_d(random_n);      
            std::min_element(std::begin(checkouts), std::end(checkouts))->add(Customer(service_t));

            ++service_times[service_t - service_t_min];  
          
            for (auto & checkout : checkouts)
                longest_q = std::max(longest_q, checkout.qleng());

            new_cust_interval = arrival_interval_d(random_n);
        }
        
        for (auto & checkout : checkouts)
            checkout.time_increment();
    }

    std::cout << "Maximum queue length = " << longest_q << std::endl;
    std::cout << "\nHistogram of service times:\n";
    histogram(service_times, service_t_min);
    std::cout << "\nTotal number of customers today: "
            << std::accumulate(std::begin(service_times), std::end(service_times), 0)
            << std::endl;
}

结果显示：

3.priority_queue

priority_queue 模板有 3 个参数，其中两个有默认的参数；

第一个参数是存储对象的类型，

第二个参数是存储元素的底层容器，

第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。

template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue

初始化：

std::priority_queue<std::string> words;
//适当类型初始化队列
std::string wrds[] { "one", "two", "three", "four"};
std::priority_queue<std::string> words { std::begin(wrds),std:: end(wrds)};
 // "two" "three" "one" "four"
 //优先级队列对他们进行排序
 std:: string wrds[] {"one", "two", "three", "four"};
 std::priority_queue<std::string, std::vector<std::string>,
     std: :greater<std::string>> words1 {std::begin (wrds) , std:: end (wrds) }; 
 //"four" "one" "three" "two"
 std::vector<int> values{21, 22, 12, 3, 24, 54, 56};
 std::priority_queue<int> numbers {std::less<int>(),values};
 //56 54 24 22 21 12  3
 //指定全部模板参数
 std::priority_queue<int, std::vector<int>,std::greater<int>> numbersl{std::greater<int>(), values};

基本操作：

push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。
 push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。
 emplace(T constructor a rgs...)：通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
 top()：返回优先级队列中第一个元素的引用。
 pop()：移除第一个元素。
 size()：返回队列中元素的个数。
 empty()：如果队列为空的话，返回true。
 swap(priority_queue<T>& other)：和参数的元素进行交换，所包含对象的类型必须相同。

具体示例：

#include <iostream> // For standard streams
#include <queue> // For priority_queue<T>
#include <string> // For string class
using std::string;
// List contents of a priority queue
template<typename T>
void list_pq(std::priority_queue<T> pq, size_t count = 5)
{
    size_t n {count};
    while (!pq.empty())
    {
        std::cout << pq.top() << " ";
        pq.pop();
        if (--n) continue;
        std::cout << std::endl;
        n = count;
    }
    std::cout << std::endl;
}
int main()
{
    std::priority_queue<std::string> words;
    std::string word;
    std::cout << "Enter words separated by spaces, enter Ctrl+D on a separate line to end:\n";
    while (true)
    {
        if ((std::cin >> word).eof())
            break;
        words.push(word);
    }
    std::cout << "You entered " << words.size() << " words:" << std::endl;
    list_pq(words);
}

结果展示：