AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】priority_queue、仿函数和反向迭代器

2023-07-27 151
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++优先级队列、仿函数和反向迭代器的介绍及使用。

一、priority_queue

1. priority_queue的介绍

  1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元
    素)。
  3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
  4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
    empty()：检测容器是否为空
    size()：返回容器中有效元素个数
    front()：返回容器中第一个元素的引用
    push_back()：在容器尾部插入元素
    pop_back()：删除容器尾部元素
  5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
  6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2. priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

image.png

void test()
{
   
   
    //默认是大堆
    priority_queue<int> pq;
    pq.push(2);
    pq.push(5);
    pq.push(0);
    pq.push(9);
    pq.push(3);
    pq.push(1);
    while (!pq.empty())
    {
   
   
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    //建立小堆
    priority_queue<int,vector<int>,greater<int>> pq1;
    pq1.push(2);
    pq1.push(5);
    pq1.push(0);
    pq1.push(9);
    pq1.push(3);
    pq1.push(1);
    while (!pq1.empty())
    {
   
   
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << endl;
}

image.png

经典例题

image.png

💕 解题思路

根据堆的性质，我们可以考虑使用数组建大堆，然后pop掉k-1个元素，这时候堆顶的数就是第k大的数，但是这种思路的时间复杂度是O(N+k*logN)，夫如果N很大的时候，就需要浪费很多的空间，这里我们还可以考虑第二种做法，就是利用topK的思路，先用前k个数建一个小堆，然后遍历剩下的元素，遇到比堆顶大的元素就替换掉堆顶的元素。注意这里的替换是指，先pop掉堆顶的元素，然后再插入目标元素。这里的时间复杂度是O(k+(N-k)*logk)，虽然时间上没有太大的提升，但是空间上却减少了浪费。

💕 解题代码

class Solution {
   
   
public:
    int findKthLargest(vector<int>& nums, int k) {
   
   
        //使用topk问题的求解方式
        priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);
        for(int i = k;i < nums.size();i++)
        {
   
   
            if(nums[i] > pq.top())
            {
   
   
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};

image.png

二、仿函数

1. 仿函数的使用

仿函数(Functor) 又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator()运算符。因为==调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。==，这里的()指的就是函数调用操作符。

template<class T>
struct Greater {
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x > y;
    }
};

template<class T>
struct Less {
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x < y;
    }
};

int main()
{
   
   
    Greater<int> gt;
    cout << gt(1, 2) << endl;//相当于gt.operator()(1,2),gt是一个对象，可以像函数一样使用
    cout << Less<int>()(1, 2) << endl;//直接使用匿名对象调用operator(1,2)
    return 0;
}
内置类型使用仿函数 
template<class T, class Compare>
void BubbleSort(T* a, int n, Compare com)
{
   
   
    for (int j = 0; j < n; j++)
    {
   
   
        int exchange = 0;
        for (int i = 1; i < n - j; i++)
        {
   
   
            if (com(a[i], a[i - 1]))
            {
   
   
                swap(a[i - 1], a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
        {
   
   
            break;
        }
    }
}

template<class T>
struct Greater {
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x > y;
    }
};

template<class T>
struct Less {
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x < y;
    }
};

int main()
{
   
   
    Less<int> ls;
    int a[] = {
   
    2,3,4,5,6,1,2,8 };
    BubbleSort(a, sizeof(a) / sizeof(int), ls);
    cout << "升序排序的结果为:";
    for (auto e : a)
    {
   
   
        cout << e << " ";
    }
    cout << endl;
    Greater<int> gt;
    BubbleSort(a, sizeof(a) / sizeof(int), gt);
    cout << "降序排序的结果为:";
    for (auto e : a)
    {
   
   
        cout << e << " ";
    }
    cout << endl;

    return 0;
}

image.png

下面我们看一下仿函数的优缺点：

优点：

  • 在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态（可以根据不同的类型代表不同的状态）
  • 仿函数即使定义相同，也可能有不同的类型(可以有不同的类型)
  • 仿函数使程序代码变得简单(仿函数在一定程度上使代码更通用，本质上简化了代码)

缺点：

仿函数比一般函数速度慢

自定义类型使用仿函数

前面我们谈到了内置类型，下面我们来看一下日期类这个自定义类型如何使用仿函数：

class Date
{
   
   
public:
    Date(int year = 1900, int month = 1, int day = 1)
        : _year(year)
        , _month(month)
        , _day(day)
    {
   
   }
    bool operator<(const Date& d)const
    {
   
   
        return (_year < d._year) ||
            (_year == d._year && _month < d._month) ||
            (_year == d._year && _month == d._month && _day < d._day);
    }
    bool operator>(const Date& d)const
    {
   
   
        return (_year > d._year) ||
            (_year == d._year && _month > d._month) ||
            (_year == d._year && _month == d._month && _day > d._day);
    }
    friend ostream& operator<<(ostream& _cout, const Date& d)
    {
   
   
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }
private:
    int _year;
    int _month;
    int _day;
};

int main()
{
   
   
    //建立小堆
    priority_queue<Date,vector<Date>, greater<Date>> q;
    q.push(Date(2023, 1, 1));
    q.push(Date(2023, 4, 7));
    q.push(Date(2020, 1, 1));
    cout << q.top() << endl;
    //建立大堆
    priority_queue<Date> q2;
    q2.push(Date(2023, 1, 1));
    q2.push(Date(2023, 4, 7));
    q2.push(Date(2020, 1, 1));
    cout << q2.top() << endl;

    return 0;
}

image.png

自定义类型自己定义仿函数

如果传入的是一个Date*的指针的时候，这个时候仿函数中的运算符重载已经不符合我们的要求了，这个时候我们就需要自己定义仿函数

image.png

template<class T>
struct Greater {
   
   
    bool operator()(const Date* x, const Date* y)
    {
   
   
        return *x > *y;
    }
};

template<class T>
struct Less {
   
   
    bool operator()(const Date* x, const Date* y)
    {
   
   
        return *x < *y;
    }
};

image.png

2. priority_queue的模拟实现

这里的priority_queue就是我们在数据结构阶段讲过的优先级队列——堆，所以我们在这里只需要用类模板和适配器模式来封装一下即可，当然了，这里我们还会用到仿函数来调整堆的构建方式是大堆还是小堆。

namespace cjl
{
   
   
    template<class T>
    struct greater {
   
   
        bool operator()(const T& x, const T& y) const
        {
   
   
            return x > y;
        }
    };

    template<class T>
    struct less {
   
   
        bool operator()(const T& x, const T& y) const
        {
   
   
            return x < y;
        }
    };

    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
   
   
    public:
        priority_queue()
        {
   
   }
        template<class Iterator>
        priority_queue(Iterator first, Iterator last)
        {
   
   
            while (first != last)
            {
   
   
                push(*first);
                first++;
            }
        }

        //向上调整算法
        void adjust_up(int child)
        {
   
   
            int parent = (child - 1) / 2;
            while (child > 0)
            {
   
   
                if (_com(_con[parent], _con[child]))
                {
   
   
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
   
   
                    break;
                }
            }
        }

        //向下调整算法
        void adjust_down(int parent)
        {
   
   
            int child = parent * 2 + 1;
            while (child < _con.size())
            {
   
   
                if (child + 1 < _con.size() && _com(_con[child], _con[child + 1]))
                {
   
   
                    child++;
                }
                if (_com(_con[parent], _con[child]))
                {
   
   
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
   
   
                    break;
                }
            }
        }

        //向堆中插入数据
        void push(const T& x)
        {
   
   
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }

        //删除堆顶数据
        void pop()
        {
   
   
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();

            //向下调整算法
            adjust_down(0);
        }

        //取堆中数据个数
        size_t size() const
        {
   
   
            return _con.size();
        }

        //取堆顶数据
        const T& top() const
        {
   
   
            return _con[0];
        }

        //堆的判空操作
        bool empty() const
        {
   
   
            return _con.empty();
        }

    private:
        Container _con;
        Compare _com;
    };
}

image.png

三、反向迭代器

1. 反向迭代器的使用

前面我们讲解list的时候对正向迭代器已经有了一个很好的认识，下面我们来认识一下反向迭代器
其中正向迭代器是iterator和const_iterator，反向迭代器则为：reverse_iterator和const_reverse_iterator，其实反向迭代器和正向迭代器的区别如下：

  • rbegin()相当于end()
  • rend()相当于begin()
  • 反向迭代器的++相当于正向迭代器--
  • 其他的操作和正向迭代器相同

image.png

int main()
{
   
   
    int arr[] = {
   
    1,2,3,4,5 };
    list<int> lt(arr, arr + 5);

    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
   
   
        cout << *rit << " ";
        rit++;
    }
    cout << endl;

    return 0;
}

image.png

2. 反向迭代器的模拟实现

这里我们可以先来看一下STL库中的反向迭代器是如何实现的，在stl_iterator.h这个头文件中，部分源码如下：

template <class Iterator>
class reverse_iterator {
   
   
protected:
    Iterator current;

public:
    typedef Iterator iterator_type;
    typedef reverse_iterator<Iterator> self;

public:
    reverse_iterator() {
   
   }
    explicit reverse_iterator(iterator_type x) : current(x) {
   
   }
    reverse_iterator(const self& x) : current(x.current) {
   
   }
    reference operator*() const {
   
   
        Iterator tmp = current;
        return *--tmp;
    }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const {
   
    return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

    self& operator++() {
   
   
        --current;
        return *this;
    }
    self& operator--() {
   
   
        ++current;
        return *this;
    }
    //...
};

这里我们也需要模仿库里面，反向迭代器是一个容器适配器，他的适配器就是正向迭代器，这样它就能根据传递过来的正向迭代器的不同实例化出对应的反向迭代器了。因此，我们只需要将每个容器对应的正向迭代器传递过来，我们就可以实现出对应的反向迭代器了。

image.png

namespace cjl
{
   
   
    template<class Iterator,class Ref,class Ptr>
    class ReverseIterator
    {
   
   
    public:
        typedef ReverseIterator<Iterator, Ref, Ptr> Self;

        //构造函数
        ReverseIterator(const Iterator& it)
            :_cur(it)
        {
   
   }

        //重载*
        Ref operator*()
        {
   
   
            auto tmp = _cur;
            return *--tmp;
        }

        //重载&
        Ptr operator->()
        {
   
   
            return &(*_cur);
        }

        //重载前置++
        Self& operator++()
        {
   
   
            --_cur;
            return *this;
        }

        //重载后置++
        Self operator++(int)
        {
   
   
            auto tmp = _cur;
            _cur--;
            return tmp;
        }

        //重载前置--
        Self& operator--()
        {
   
   
            ++_cur;
            return *this;
        }

        //重载后置--
        Self& operator--(int)
        {
   
   
            auto tmp = _cur;
            _cur++;
            return tmp;
        }

        //重载!=
        bool operator!=(const Self& s)
        {
   
   
            return _cur != s._cur;
        }

        //重载==
        bool operator==(const Self& s)
        {
   
   
            return _cur = s._cur;
        }
    private:
        Iterator _cur;
    };
}

image.png

这里我们可以在我们之前自己模拟实现的list容器中测试一下：

image.png

文章标签：
C++
容器
算法
存储
关键词：
C++仿函数
C++ priority_queue
C++ priority_queue仿函数
C++仿函数反向迭代器
C++ priority_queue反向迭代器
~小白学编程~
目录
相关文章
可能只会写BUG
|
3月前
|
C++
C++(十七)仿函数
### Functor 仿函数简介 Functor（仿函数）是一种通过在类中实现 `operator()` 使其行为像函数的对象。这种方式可以让类拥有更多可定制的功能，同时保持函数般的简洁调用方式。下面展示了如何定义和使用一个计算幂运算的仿函数类，并通过示例说明了其在 `std::sort` 中的优势与灵活性。
可能只会写BUG
41 3
დ旧言~
|
5月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
დ旧言~
42 1
Eternity._
|
6月前
|
算法 安全 编译器
【C++进阶】模板进阶与仿函数：C++编程中的泛型与函数式编程思想
【C++进阶】模板进阶与仿函数：C++编程中的泛型与函数式编程思想
Eternity._
61 1
东洛的克莱斯韦克
|
5月前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一：优先级队列 priority_queue
【C++】详解STL的适配器容器之一：优先级队列 priority_queue
东洛的克莱斯韦克
52 0
GR鲸鱼
|
7月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（下）
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
GR鲸鱼
31 0
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（下）
好奇的菜鸟
|
6月前
|
C++
C++函数对象(仿函数)
C++函数对象(仿函数)
好奇的菜鸟
30 0
枫叶丹4
|
6月前
|
存储 设计模式 算法
【C++航海王：追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些？
【C++航海王：追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些？
枫叶丹4
56 0
ephemerals__
|
23天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
37 2
ephemerals__
|
29天前
|
存储 编译器 C++
【c++】类和对象（下）（取地址运算符重载、深究构造函数、类型转换、static修饰成员、友元、内部类、匿名对象）
本文介绍了C++中类和对象的高级特性，包括取地址运算符重载、构造函数的初始化列表、类型转换、static修饰成员、友元、内部类及匿名对象等内容。文章详细解释了每个概念的使用方法和注意事项，帮助读者深入了解C++面向对象编程的核心机制。
ephemerals__
83 5
ephemerals__
|
1月前
|
存储 编译器 C++
【c++】类和对象（中）（构造函数、析构函数、拷贝构造、赋值重载）
本文深入探讨了C++类的默认成员函数，包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化，析构函数用于对象销毁时的资源清理，拷贝构造函数用于对象的拷贝，赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项，并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
ephemerals__
79 4