当前位置:   article > 正文

STL-容器适配器详解

STL-容器适配器详解
C++ STL容器适配器详解

容器适配器,其就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用。容器适配器的底层实现和模板 A、B 的关系是完全相同的,即通过封装某个序列式容器,并重新组合该容器中包含的成员函数,使其满足某些特定场景的需要。

STL容器适配器的种类

STL 提供了 3 种容器适配器,分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器

容器适配器基础容器筛选条件默认使用的基础容器
stack基础容器需包含以下成员函数:empty()、size()、back()、push_back()、pop_back()满足条件的基础容器有 vector、deque、list。deque
queue基础容器需包含以下成员函数:empty()、size()、front()、back()、push_back()、pop_front()满足条件的基础容器有 deque、list。deque
priority_queue基础容器需包含以下成员函数:empty()、size()、front()、push_back()、pop_back()满足条件的基础容器有vector、deque。vector
C++ stack(STL stack)容器适配器用法详解
stack容器适配器的创建

由于 stack 适配器以模板类 stack<T,Container=deque>(其中 T 为存储元素的类型,Container 表示底层容器的类型)的形式位于头文件中,并定义在 std 命名空间里。因此,在创建该容器之前,程序中应包含以下 2 行代码:

#include <stack>
using namespace std;
  • 1
  • 2

创建 stack 适配器,大致分为如下几种方式。

  1. 创建一个不包含任何元素的 stack 适配器,并采用默认的 deque 基础容器:
std::stack<int> values;
  • 1

在介绍适配器时提到,序列式容器中同时包含这 5 个成员函数的,有 vector、deque 和 list 这 3 个容器。因此,stack 适配器的基础容器可以是它们 3 个中任何一个。例如,下面展示了如何定义一个使用 list 基础容器的 stack 适配器:

std::stack<std::string, std::list<int>> values;
  • 1
  1. 可以用一个基础容器来初始化 stack 适配器,只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如:
std::list<int> values {1, 2, 3};
std::stack<int,std::list<int>> my_stack (values);
  • 1
  • 2
  1. 还可以用一个 stack 适配器来初始化另一个 stack 适配器,只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如:
std::list<int> values{ 1, 2, 3 };
std::stack<int, std::list<int>> my_stack1(values);
std::stack<int, std::list<int>> my_stack=my_stack1;
//std::stack<int, std::list<int>> my_stack(my_stack1);
  • 1
  • 2
  • 3
  • 4
stack容器适配器支持的成员函数
成员函数功能
empty()当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false。
size()返回 stack 栈中存储元素的个数。
top()返回一个栈顶元素的引用,类型为 T&。如果栈为空,程序会报错。
push(const T& val)先复制 val,再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
push(T&& obj)以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()弹出栈顶元素。
emplace(arg…)arg… 可以是一个参数,也可以是多个参数,但它们都只用于构造一个对象,并在栈顶直接生成该对象,作为新的栈顶元素。
swap(stack & other_stack)将两个 stack 适配器中的元素进行互换,需要注意的是,进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。
C++ STL queue容器适配器详解
queue容器适配器的创建

queue 容器适配器以模板类 queue<T,Container=deque>(其中 T 为存储元素的类型,Container 表示底层容器的类型)的形式位于头文件中,并定义在 std 命名空间里。因此,在创建该容器之前,程序中应包含以下 2 行代码:

#include <queue>
using namespace std;
  • 1
  • 2
  1. 创建一个空的 queue 容器适配器,其底层使用的基础容器选择默认的 deque 容器:
std::queue<int> values;
  • 1

通过此行代码,就可以成功创建一个可存储 int 类型元素,底层采用 deque 容器的 queue 容器适配器。

  1. 当然,也可以手动指定 queue 容器适配器底层采用的基础容器类型。通过学习 《STL容器适配器详解》一节我们知道,queue 容器适配器底层容器可以选择 deque 和 list。

作为 queue 容器适配器的基础容器,其必须提供 front()、back()、push_back()、pop_front()、empty() 和 size() 这几个成员函数,符合条件的序列式容器仅有 deque 和 list

std::queue<int, std::list<int>> values;
  • 1
  1. 可以用基础容器来初始化 queue 容器适配器,只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如:
std::deque<int> values{1,2,3};
std::queue<int> my_queue(values);
  • 1
  • 2
  1. 还可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器,只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如:
std::deque<int> values{1,2,3};
std::queue<int> my_queue1(values);
std::queue<int> my_queue(my_queue1);
//或者使用
//std::queue<int> my_queue = my_queue1;
  • 1
  • 2
  • 3
  • 4
  • 5
queue容器适配器支持的成员函数
成员函数功能
empty()如果 queue 中没有元素的话,返回 true。
size()返回 queue 中元素的个数。
front()返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back()返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
push(const T& obj)在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
emplace()在 queue 的尾部直接添加一个元素。
push(T&& obj)以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop()删除 queue 中的第一个元素。
swap(queue &other_queue)将两个 queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

和 stack 一样,queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。

C++ STL priority_queue容器适配器详解

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素,每当有新元素进入,它都会根据既定的排序规则找到优先级最高的元素,并将其移动到队列的队头;同样,当 priority_queue 从队头移除出一个元素之后,它也会再找到当前优先级最高的元素,并将其移动到队头。

基于 priority_queue 的这种特性,因此该容器适配器有被称为优先级队列。

STL 中,priority_queue 容器适配器的定义如下:

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

可以看到,priority_queue 容器适配器模板类最多可以传入 3 个参数,它们各自的含义如下:

  • typename T:指定存储元素的具体类型;

  • typename Container:指定 priority_queue 底层使用的基础容器,默认使用 vector 容器。

    作为 priority_queue 容器适配器的底层容器,其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数,STL 序列式容器中只有 vector 和 deque 容器符合条件。

  • typename Compare:指定容器中评定元素优先级所遵循的排序规则,默认使用

    std::less<T>
    
    • 1

    按照元素值从大到小进行排序,还可以使用

    std::greater<T>
    
    • 1

    按照元素值从小到大排序,但更多情况下是使用自定义的排序规则。

    其中,std::less 和 std::greater 都是以函数对象的方式定义在 头文件中。关于如何自定义排序规则。

创建priority_queue的几种方式

由于 priority_queue 容器适配器模板位于<queue>头文件中,并定义在 std 命名空间里,因此在试图创建该类型容器之前,程序中需包含以下 2 行代码:

#include <queue>
using namespace std;
  • 1
  • 2

创建 priority_queue 容器适配器的方法,大致有以下几种。

  1. 创建一个空的 priority_queue 容器适配器,第底层采用默认的 vector 容器,排序方式也采用默认的 std::less 方法:
std::priority_queue<int> values;
  • 1
  1. 可以使用普通数组或其它容器中指定范围内的数据,对 priority_queue 容器适配器进行初始化:
//使用普通数组
int values[]{4,1,3,2};
std::priority_queue<int>copy_values(values,values+4);//{4,2,3,1}
//使用序列式容器
std::array<int,4>values{ 4,1,3,2 };
std::priority_queue<int>copy_values(values.begin(),values.end());//{4,2,3,1}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 还可以手动指定 priority_queue 使用的底层容器以及排序规则,比如:
int values[]{ 4,1,2,3 };
std::priority_queue<int, std::deque<int>, std::greater<int> >copy_values(values, values+4);//{1,3,2,4}
  • 1
  • 2
priority_queue提供的成员函数
成员函数功能
empty()如果 priority_queue 为空的话,返回 true;反之,返回 false。
size()返回 priority_queue 中存储元素的个数。
top()返回 priority_queue 中第一个元素的引用形式。
push(const T& obj)根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。
push(T&& obj)根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。
emplace(Args&&… args)Args&&… args 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。
pop()移除 priority_queue 容器适配器中第一个元素。
swap(priority_queue& other)将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。

和 queue 一样,priority_queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。

C++ STL迭代器适配器

本章将介绍 5 种迭代器适配器,分别是反向迭代器适配器、插入型迭代器适配器、流迭代器适配器、流缓冲区迭代器适配器、移动迭代器适配器。

C++ STL迭代器适配器种类
名称功能
反向迭代器(reverse_iterator)又称“逆向迭代器”,其内部重新定义了递增运算符(++)和递减运算符(–),专门用来实现对容器的逆序遍历。
安插型迭代器(inserter或者insert_iterator)通常用于在容器的任何位置添加新的元素,需要注意的是,此类迭代器不能被运用到元素个数固定的容器(比如 array)上。
流迭代器(istream_iterator / ostream_iterator) 流缓冲区迭代器(istreambuf_iterator / ostreambuf_iterator输入流迭代器用于从文件或者键盘读取数据;相反,输出流迭代器用于将数据输出到文件或者屏幕上。 输入流缓冲区迭代器用于从输入缓冲区中逐个读取数据;输出流缓冲区迭代器用于将数据逐个写入输出流缓冲区。
移动迭代器(move_iterator)此类型迭代器是 C++ 11 标准中新添加的,可以将某个范围的类对象移动到目标范围,而不需要通过拷贝去移动。
#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> values{ 1,2,3,4,5 };
    //找到遍历的起点和终点,这里无需纠结定义反向迭代器的语法,后续会详细讲解
    std::reverse_iterator<std::list<int>::iterator> begin = values.rbegin();
    std::reverse_iterator<std::list<int>::iterator> end = values.rend();
    while (begin != end) {
        cout << *begin << " ";
        //注意,这里是 ++,因为反向迭代器内部互换了 ++ 和 -- 的含义
        ++begin;
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
C++ STL distance()函数用法详解

作用于同一容器的 2 个同类型迭代器可以有效指定一个区间范围。在此基础上,如果想获取该指定范围内包含元素的个数,就可以借助本节要讲的 distance() 函数。

distance() 函数用于计算两个迭代器表示的范围内包含元素的个数,其语法格式如下:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);
  • 1
  • 2

其中,first 和 last 都为迭代器,其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器;该函数会返回[first, last)范围内包含的元素的个数。

注意,first 和 last 的迭代器类型,直接决定了 distance() 函数底层的实现机制:

  • 当 first 和 last 为随机访问迭代器时,distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数,其时间复杂度为O(1)常数阶;
  • 当 first 和 last 为非随机访问迭代器时,distance() 底层通过不断执行 ++first(或者 first++)直到 first==last,由此来获取 [first, last) 范围内包含元素的个数,其时间复杂度为O(n)线性阶。

另外,distance() 函数定义在<iterator>头文件,并位于 std 命名空间中。因此在使用此函数前,程序中应包含如下代码:

#include <iterator>
using namespace std;
  • 1
  • 2
#include <iostream>     // std::cout
#include <iterator>     // std::distance
#include <list>         // std::list
using namespace std;
int main() {
    //创建一个空 list 容器
    list<int> mylist;
    //向空 list 容器中添加元素 0~9
    for (int i = 0; i < 10; i++) {
        mylist.push_back(i);
    }
    //指定 2 个双向迭代器,用于执行某个区间
    list<int>::iterator first = mylist.begin();//指向元素 0
    list<int>::iterator last = mylist.end();//指向元素 9 之后的位置
    //获取 [first,last) 范围内包含元素的个数
    cout << "distance() = " << distance(first, last);
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
C++ STL advance()函数用法详解
迭代器辅助函数功能
advance(it, n)it 表示某个迭代器,n 为整数。该函数的功能是将 it 迭代器前进或后退 n 个位置。
distance(first, last)first 和 last 都是迭代器,该函数的功能是计算 first 和 last 之间的距离。
begin(cont)cont 表示某个容器,该函数可以返回一个指向 cont 容器中第一个元素的迭代器。
end(cont)cont 表示某个容器,该函数可以返回一个指向 cont 容器中最后一个元素之后位置的迭代器。
prev(it)it 为指定的迭代器,该函数默认可以返回一个指向上一个位置处的迭代器。注意,it 至少为双向迭代器。
next(it)it 为指定的迭代器,该函数默认可以返回一个指向下一个位置处的迭代器。注意,it 最少为前向迭代器。

C++ STL advance()函数

advance() 函数用于将迭代器前进(或者后退)指定长度的距离,其语法格式如下:

template <class InputIterator, class Distance>
void advance (InputIterator& it, Distance n);
  • 1
  • 2

其中 it 指的是目标迭代器,n 通常为一个整数。

需要注意的是,如果 it 为输入迭代器或者前向迭代器,则 n 必须为一个正数,即表示将 it 右移(前进) n 个位置;反之,如果 it 为双向迭代器或者随机访问迭代器,则 n 为正数时表示将 it 右移(前进) n 个位置,n 为负数时表示将 it 左移(后退) n 个位置。

另外,根据 it 类型是否为随机访问迭代器,advance() 函数底层采用了不同的实现机制:

  • 当 it 为随机访问迭代器时,由于该类型迭代器支持 p+n 或者 p-n(其中 p 就是一个随机访问迭代器)运算,advance() 函数底层采用的就是 it+n 操作实现的;
  • 当 it 为其他类型迭代器时,它们仅支持进行 ++ 或者 – 运算,这种情况下,advance() 函数底层是通过重复执行 n 个 ++ 或者 – 操作实现的。

值得一提的是,advance() 函数定义在<iterator>头文件,并位于 std 命名空间中。因此,程序在使用该函数之前,应包含如下 2 行代码:

#include <iterator>
using namespace std;
  • 1
  • 2

为了让读者更好地知晓 advance() 函数的功能,首先以 forward_list 容器(仅支持使用前向迭代器)为例,下面程序演示了 advance() 函数的功能:

#include <iostream>     // std::cout
#include <iterator>     // std::advance
#include <forward_list>
using namespace std;
int main() {
    //创建一个 forward_list 容器
    forward_list<int> mylist{1,2,3,4};
    //it为前向迭代器,其指向 mylist 容器中第一个元素
    forward_list<int>::iterator it = mylist.begin();
    //借助 advance() 函数将 it 迭代器前进 2 个位置
    advance(it, 2);
    cout << "*it = " << *it;
    return 0;
}

// 程序执行结果为:*it = 3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/197848
推荐阅读
相关标签
  

闽ICP备14008679号