c++ - 为什么 const_casting a heap.top() of priority_queue 有未定义的行为？

Question

我制作了一个简单的霍夫曼编码程序来输出字符的单独编码并保存编码文件。这是一个作业，有人告诉我使用 const_cast在 heap.top()如果我们 heap.pop() 被认为是未定义的行为之后，但我不确定我明白为什么。
我已阅读 cppreference关于 std::pop_heap这是我们调用 heap.pop() 时调用的底层函数我相信一个 nullptr在比较中仍然是定义和理解的。当我调试它时，它似乎并没有异常运行。
这是一个例子

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
#include <memory>

template<typename T> void print_queue_constcast(T& q) {
    while(!q.empty()) {
        auto temp = std::move(const_cast<int&>(q.top()));
        std::cout << temp << " ";
        q.pop();
    }
    std::cout << '\n';
}

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int> q1;
    std::priority_queue<int> q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2}){
        q1.push(n);
        q2.push(n);
    }
        
    print_queue(q1);
    print_queue_constcast(q2);
    
    
}

谁能解释背景中实际发生的事情是未定义的行为，或者在某些情况下会导致此失败？

Answer 1

tl;博士:也许；也许不吧。

语言级安全
与集合一样，priority_queue 负责对其元素进行排序。对元素的任何修改都可能会“破坏”排序，因此唯一安全的方法是通过容器自己的变异方法。 (事实上​​，没有人真正提供这样的东西。)直接修改元素是危险的。为了加强这一点，这些容器只暴露 const访问您的元素。
现在，在语言层面，对象实际上不会有 const T 的静态类型;很可能他们只是 T s .因此，修改它们(在 const_cast 之后以欺骗类型系统)在这个意义上没有未定义的行为。

图书馆级安全
然而，您可能会破坏使用容器的条件 . priority_queue 的规则实际上并没有这么说，但是因为它的变异操作是根据像 push_heap 这样的函数定义的。和 pop_heap ，如果容器的排序在您直接更改后不再满足，则您使用此类操作将破坏这些函数的先决条件。
因此，如果您破坏排序并随后以依赖于完整排序的方式改变 priority_queue，您的程序将具有未定义的行为。如果你不这样做，从技术上讲，你的程序的行为是明确定义的；然而，一般来说，你仍然是在玩火。 一个 const_cast应该是不得已而为之的措施。

那么，我们站在哪里？
问题是:你打破了顺序吗？从元素移出后元素的状态是什么，是否通过在队列顶部放置处于该状态的对象来满足排序？

您的原始示例使用 shared_ptr s，我们从文档中得知，一个来自 shared_ptr安全地变成空指针。

默认priority_queue排序由 std::less 定义, 对原始指针产生严格的全序； std::less在 shared_ptr实际上会调用它的基本情况 operator< ，但是 that in turn is defined to invoke std::less on its raw pointer equivalent .

不幸的是，这并不意味着 null shared_ptr 被排序为“第一” :though std::less 's pointer ordering is strict and total, where null pointers land in this ordering is unspecified .

因此，不确定您的突变是否会破坏排序，因此 不确定您的 pop() 是否将有未定义的行为 .

(带有 int 的 MCVE 示例是安全的，因为 std::move 上的 int 没有任何工作要做:它只会复制 int 。因此，排序不受影响。)

结论
我同意大概是你的驾驶理由，这是不幸的 pop()不会返回弹出的东西，然后你可以 move从。集合和映射的类似限制是我们现在拥有 node splicing features 的原因。对于那些容器。对于priority_queue 没有这样的事情，它只是一个像 vector 这样的另一个容器的包装器。如果您需要更细粒度的控制，您可以将其替换为您自己的具有您需要的功能的控制。
不管怎样， 为了一个 shared_ptr增量(如在您的原始代码中)，我可能只需要复制 ，除非您有一些非常极端的性能要求。这样，您就知道一切都将得到明确定义。
当然，为了 int复制(如在您的 MCVE 中)，一个 std::move完全没有意义(没有可以窃取的间接资源!)而且无论如何你都在做一个拷贝，所以重点是没有意义的，你所做的只是无缘无故地创建更复杂的代码。
我还建议不要在必须询问它是否定义明确的地方编写代码 ，即使事实证明确实如此。这对于可读性或可维护性来说并不理想。