当前位置：首页 > article >正文

【C++ 面试 - STL】每日 3 题（四）

article 2024/11/17 21:28:24

✍个人博客：Pandaconda-CSDN博客
📣专栏地址：http://t.csdnimg.cn/fYaBd
📚专栏简介：在这个专栏中，我将会分享 C++ 面试中常见的面试题给大家~
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

10. STL 中的 heap 的实现

heap（堆）并不是 STL 的容器组件，是 priority queue（优先队列）的底层实现机制，因为 binary max heap（大根堆）总是最大值位于堆的根部，优先级最高。
binary heap 本质是一种 complete binary tree（完全二叉树），整棵 binary tree 除了最底层的叶节点之外，都是填满的，但是叶节点从左到右不会出现空隙，如下图所示就是一颗完全二叉树：
[图片]

完全二叉树内没有任何节点漏洞，是非常紧凑的，这样的一个好处是可以使用 array 来存储所有的节点，因为当其中某个节点位于i处，其左节点必定位于 2i 处，右节点位于 2i+1 处，父节点位于 i/2（向下取整）处。这种以 array 表示 tree 的方式称为隐式表述法。
因此我们可以使用一个 array 和一组 heap 算法来实现 max heap（每个节点的值大于等于其子节点的值）和 min heap（每个节点的值小于等于其子节点的值）。由于 array 不能动态的改变空间大小，用 vector 代替 array 是一个不错的选择。
那 heap 算法有哪些？常见有的插入、弹出、排序和构造算法，下面一一进行描述。
push_heap 插入算法
由于完全二叉树的性质，新插入的元素一定是位于树的最底层作为叶子节点，并填补由左至右的第一个空格。事实上，在刚执行插入操作时，新元素位于底层 vector 的 end() 处，之后是一个称为 percolate up（上溯）的过程，举个例子如下图：
在这里插入图片描述
新元素 50 在插入堆中后，先放在 vector 的 end() 存着，之后执行上溯过程，调整其根结点的位置，以便满足 max heap 的性质，如果了解大根堆的话，这个原理跟大根堆的调整过程是一样的。
pop_heap 算法
heap 的 pop 操作实际弹出的是根节点吗，但在 heap 内部执行 pop_heap 时，只是将其移动到 vector 的最后位置，然后再为这个被挤走的元素找到一个合适的安放位置，使整颗树满足完全二叉树的条件。这个被挤掉的元素首先会与根结点的两个子节点比较，并与较大的子节点更换位置，如此一直往下，直到这个被挤掉的元素大于左右两个子节点，或者下放到叶节点为止，这个过程称为 percolate down（下溯）。举个例子：
在这里插入图片描述
根节点 68 被 pop 之后，移到了 vector 的最底部，将 24 挤出，24 被迫从根节点开始与其子节点进行比较，直到找到合适的位置安身，需要注意的是 pop 之后元素并没有被移走，如果要将其移走，可以使用 pop_back()。
sort 算法
一言以蔽之，因为 pop_heap 可以将当前 heap 中的最大值置于底层容器 vector 的末尾，heap 范围减 1，那么不断的执行 pop_heap 直到树为空，即可得到一个递增序列。
make_heap 算法
将一段数据转化为 heap，一个一个数据插入，调用上面说的两种 percolate 算法即可。
代码实测：

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

int main()
{
    vector<int> v = { 0,1,2,3,4,5,6 };
    make_heap(v.begin(), v.end()); //以vector为底层容器
    for (auto i : v)
    {
        cout << i << " "; // 6 4 5 3 1 0 2
    }
    cout << endl;
    v.push_back(7);
    push_heap(v.begin(), v.end());
    for (auto i : v)
    {
        cout << i << " "; // 7 6 5 4 1 0 2 3
    }
    cout << endl;
    pop_heap(v.begin(), v.end());
    cout << v.back() << endl; // 7 
    v.pop_back();
    for (auto i : v)
    {
        cout << i << " "; // 6 4 5 3 1 0 2
    }
    cout << endl;
    sort_heap(v.begin(), v.end());
    for (auto i : v)
    {
        cout << i << " "; // 0 1 2 3 4 5 6
    }
    return 0;
}

11. STL 中的 priority_queue 的实现

priority_queue，优先队列，是一个拥有权值观念的 queue，它跟 queue 一样是顶部入口，底部出口，在插入元素时，元素并非按照插入次序排列，它会自动根据权值（通常是元素的实值）排列，权值最高，排在最前面，如下图所示。
在这里插入图片描述
默认情况下，priority_queue 使用一个 max-heap 完成，底层容器使用的是一般为 vector 为底层容器，堆 heap 为处理规则来管理底层容器实现。priority_queue 的这种实现机制导致其不被归为容器，而是一种容器配接器。关键的源码如下：

template <class T, class Squence = vector<T>, 
class Compare = less<typename Sequence::value_tyoe> >
class priority_queue{
    ...
protected:
    Sequence c; // 底层容器
    Compare comp; // 元素大小比较标准
public:
    bool empty() const {return c.empty();}
    size_type size() const {return c.size();}
    const_reference top() const {return c.front()}
    void push(const value_type& x)
    {
        c.push_back(x);
        push_heap(c.begin(), c.end(),comp);
    }
    void pop()
    {
        pop_heap(c.begin(), c.end(),comp);
        c.pop_back();
    }
};

priority_queue 的所有元素，进出都有一定的规则，只有 queue 顶端的元素（权值最高者），才有机会被外界取用，它没有遍历功能，也不提供迭代器。
举个例子：

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

int main()
{
    int ia[9] = {0,4,1,2,3,6,5,8,7 };
    priority_queue<int> pq(ia, ia + 9);
    cout << pq.size() <<endl;  // 9
    for(int i = 0; i < pq.size(); i++)
    {
        cout << pq.top() << " "; // 8 8 8 8 8 8 8 8 8
    }
    cout << endl;
    while (!pq.empty())
    {
        cout << pq.top() << ' ';// 8 7 6 5 4 3 2 1 0
        pq.pop();
    }
    return 0;
}

12. STL 中 set 的实现？

STL 中的容器可分为序列式容器（sequence）和关联式容器（associative），set 属于关联式容器。
set 的特性是，所有元素都会根据元素的值自动被排序（默认升序），set 元素的键值就是实值，实值就是键值，set 不允许有两个相同的键值。
set 不允许迭代器修改元素的值，其迭代器是一种 constance iterators。
标准的 STL set 以 RB-tree（红黑树）作为底层机制，几乎所有的 set 操作行为都是转调用 RB-tree 的操作行为，这里补充一下红黑树的特性：

每个节点不是红色就是黑色
根结点为黑色
如果节点为红色，其子节点必为黑
任一节点至（NULL）树尾端的任何路径，所含的黑节点数量必相同
关于红黑树的具体操作过程，比较复杂读者可以翻阅《算法导论》详细了解。
举个例子：

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

int main()
{
    int i;
    int ia[5] = { 1,2,3,4,5 };
    set<int> s(ia, ia + 5);
    cout << s.size() << endl; // 5
    cout << s.count(3) << endl; // 1
    cout << s.count(10) << endl; // 0

    s.insert(3); //再插入一个3
    cout << s.size() << endl; // 5
    cout << s.count(3) << endl; // 1

    s.erase(1);
    cout << s.size() << endl; // 4

    set<int>::iterator b = s.begin();
    set<int>::iterator e = s.end();
    for (; b != e; ++b)
        cout << *b << " "; // 2 3 4 5
    cout << endl;

    b = find(s.begin(), s.end(), 5);
    if (b != s.end())
        cout << "5 found" << endl; // 5 found

    b = s.find(2);
    if (b != s.end())
        cout << "2 found" << endl; // 2 found

    b = s.find(1);
    if (b == s.end())
        cout << "1 not found" << endl; // 1 not found
    return 0;
}