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

Question

我做了一个简单的霍夫曼编码程序来输出字符的单独编码并保存编码文件。这是一个作业，我被告知如果我们之后 heap.pop() 在 heap.top() 上使用 const_cast 被认为是未定义的行为，但我不确定我明白为什么。

我已经阅读了 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 的静态类型；他们很可能只是 Ts。所以修改它们（在 const_cast 之后欺骗类型系统）在这个意义上没有未定义的行为。

图书馆级安全

但是，您可能会违反使用容器的条件。 priority_queue 的规则实际上并没有这样说，但由于它的变异操作是根据 push_heap and pop_heap 等函数定义的，您使用此类操作将打破 those 如果容器的顺序在你的直接突变后不再满足则起作用。

因此您的程序将有未定义的行为如果您破坏了顺序并稍后以依赖于顺序完整的方式改变priority_queue。如果你不这样做，从技术上讲你的程序的行为是明确定义的；但是，一般来说，您仍然是在玩火。 一个const_cast应该是万不得已的措施。

那么，我们的立场是什么？

问题是：你打破了顺序吗？元素从元素中移出后的状态是什么？在队列顶部有一个处于该状态的对象是否满足排序？

您的原始示例使用 shared_ptrs，并且我们从文档中得知移出的 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 被排序为“第一个”：.
所以，你的突变是否会破坏顺序是不确定的，因此你的pop()是否会有未定义的行为是不确定的.

（带有 int 的 MCVE 示例是安全的，因为 int 上的 std::move 没有工作要做：它只会复制 int。所以，排序不受影响。）

结论

我同意你大概的驾驶理由，不幸的是 pop() 没有 return 你突然出现的东西，然后你可以 move 从。集合和地图的类似限制是我们现在为这些容器设置 node splicing features 的原因。 priority_queue 没有这样的东西，它只是像矢量一样围绕另一个容器的包装器。如果您需要更细粒度的控制，您可以将其替换为具有您需要的功能的您自己的。

无论如何，为了 shared_ptr 增量（如在您的原始代码中），我可能只接受副本，除非您有一些非常极端的性能要求。那样的话，你知道一切都会被明确定义。

当然，为了 int 副本（如在您的 MCVE 中），std::move 完全毫无意义（没有间接资源偷！）而且你还是在做一个副本，所以这一点是没有实际意义的，你所做的只是无缘无故地创建更复杂的代码。

我还建议不要在必须询问它是否定义明确的地方编写代码，即使事实证明是这样。这对于可读性或可维护性来说并不理想。

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

Why does const_casting a heap.top() of priority_queue have undefined behavior?

c++

c++17

priority-queue

undefined-behavior

const-cast

语言级别的安全

图书馆级安全

那么，我们的立场是什么？

结论