允许从 std::map 的密钥中窃取资源？

Question

在 C++ 中，可以从我以后不再需要的地图中窃取资源吗？更准确地说，假设我有一个 std::map 和 std::string 键，我想通过使用 std::move 窃取 maps 键的资源来构建一个向量。请注意，对密钥的这种写访问会破坏 map 的内部数据结构（密钥的排序），但我以后不会使用它。

问题：我是否可以毫无问题地执行此操作，或者这是否会导致意外错误，例如在 map 的析构函数中，因为我以某种方式访问它std::map 不适合？

这是一个示例程序：

#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main(int argc, char *argv[])
{
    std::vector<std::pair<std::string,double>> v;
    { // new scope to make clear that m is not needed 
      // after the resources were stolen
        std::map<std::string,double> m;
        m["aLongString"]=1.0;
        m["anotherLongString"]=2.0;
        //
        // now steal resources
        for (auto &p : m) {
            // according to my IDE, p has type 
            // std::pair<const class std::__cxx11::basic_string<char>, double>&
            cout<<"key before stealing: "<<p.first<<endl;
            v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second));
            cout<<"key after stealing: "<<p.first<<endl;
        }
    }
    // now use v
    return 0;
}

它产生输出：

key before stealing: aLongString
key after stealing: 
key before stealing: anotherLongString
key after stealing:

编辑：我想对大地图的全部内容执行此操作，并通过此资源窃取保存动态分配。

Answer 1

您正在执行未定义的行为，使用 const_cast 修改 const 变量。不要那样做。它是 const 的原因是因为地图是按它们的键排序的。因此，就地修改键打破了地图构建的基本假设。

您永远不应使用 const_cast 从变量中删除 const 和修改该变量。

也就是说，C++17 有解决您问题的方法：std::map 的 extract 函数：

#include <map>
#include <string>
#include <vector>
#include <utility>

int main() {
  std::vector<std::pair<std::string, double>> v;
  std::map<std::string, double> m{{"aLongString", 1.0},
                                  {"anotherLongString", 2.0}};

  auto extracted_value = m.extract("aLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));

  extracted_value = m.extract("anotherLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));
}

并且不要 using namespace std;。 :)

Answer 2

编辑：这个答案是错误的。善意的评论指出了错误，但我没有删除它，因为它已在其他答案中引用。

@druckermanly 回答了你的第一个问题，它说强行更改 map 中的键会破坏构建 map 内部数据结构（红黑树）的有序性。但是使用 extract 方法是安全的，因为它做了两件事：将键移出地图然后删除它，所以它根本不会影响地图的有序性。

你提的另外一个问题，解构的时候会不会出问题，不是问题。当 map 解构时，它会调用其每个元素的解构器（mapped_types 等），move 方法确保解构一个 class 之后是安全的感动。所以别担心。简而言之，正是 move 的操作确保删除或重新分配一些新值到 "moved" class 是安全的。特别是对于string，move方法可能会将其char指针设置为nullptr，因此它不会删除原始class的析构函数时移动的实际数据打电话。

一条评论让我想起了我忽略的一点，基本上他是对的，但有一件事我不完全同意：const_cast 可能不是 UB。 const只是编译器和我们之间的约定。标记为 const 的对象仍然是一个对象，就其类型和二进制形式的表示而言，与那些未标记为 const 的对象相同。当 const 被丢弃时，它应该表现得像一个普通的可变 class。关于move，如果你想使用它，你必须传递一个&而不是一个const &，所以我认为它不是一个UB，它只是违背了诺言const 并将数据移走。

我也做了两个实验，分别用MSVC 14.24.28314和Clang 9.0.0，结果一样。

map<string, int> m;
m.insert({ "test", 2 });
m.insert({ "this should be behind the 'test' string.", 3 });
m.insert({ "and this should be in front of the 'test' string.", 1 });
string let_me_USE_IT = std::move(const_cast<string&>(m.find("test")->first));
cout << let_me_USE_IT << '\n';
for (auto const& i : m) {
    cout << i.first << ' ' << i.second << '\n';
}

输出：

test
and this should be in front of the 'test' string. 1
 2
this should be behind the 'test' string. 3

我们可以看到字符串'2'现在是空的，但是显然我们破坏了映射的有序性，因为空字符串应该重新定位到前面。如果我们试图插入、查找或删除地图的某些特定节点，可能会造成灾难。

无论如何，我们可能会同意，绕过 public 接口操纵任何 classes 的内部数据绝不是一个好主意。 find、insert、remove等函数的正确性依赖于内部数据结构的有序性，这就是为什么我们应该远离窥视内部的想法.

Answer 3

在这种情况下，我认为 const_cast 和修改不会导致未定义的行为，但请评论此论点是否正确。

回答声称

In other words, you get UB if you modify an originally const object, and otherwise not.

所以当且仅当 string 对象 p.first 不是作为 const 对象创建时，问题中的 v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second)); 行不会导致 UB。现在注意 reference about extract 州

Extracting a node invalidates the iterators to the extracted element. Pointers and references to the extracted element remain valid, but cannot be used while element is owned by a node handle: they become usable if the element is inserted into a container.

所以如果我extract对应p的node_handle，p继续住在它的存储位置。但是在提取之后，我被允许 move 离开 p 的资源，就像的代码一样。这意味着 p 以及 string 对象 p.first 最初是 而不是 创建为 const 对象。

因此，我认为 map 的键的修改不会导致 UB 并且从，似乎现在损坏的树结构（现在多个相同的空字符串map 的键）不会在析构函数中引入问题。因此，问题中的代码至少在 extract 方法存在的 C++17 中应该可以正常工作（以及关于指针保持有效的声明）。

更新

我现在认为这个答案是错误的。我没有删除它，因为它被其他答案引用了。

Answer 4

您的代码试图修改 const 个对象，因此它具有未定义的行为，正如正确指出的那样。

一些其他答案（ and ) argue that the key must not be stored as a const object because the node handle resulted from extracting nodes out of the map allow non-const access to the key. This inference may seem plausible at first, but P0083R3，介绍 extract 功能的论文），有一个专门讨论这个主题的部分，使这个论点无效：

Concerns

Several concerns have been raised about this design. We will address them here.

Undefined behavior

The most difficult part of this proposal from a theoretical perspective is the fact that the extracted element retains its const key type. This prevents moving out of it or changing it. To solve this, we have provided the key accessor function, which provides non-const access to the key in the element held by the node handle. This function requires implementation "magic" to ensure that it works correctly in the presence of compiler optimizations. One way to do this is with a union of pair<const key_type, mapped_type> and pair<key_type, mapped_type>. The conversion between these can be effected safely using a technique similar to that used by std::launder on extraction and reinsertion.

We do not feel that this poses any technical or philosophical problem. One of the reasons the Standard Library exists is to write non-portable and magical code that the client can’t write in portable C++ (e.g. <atomic>, <typeinfo>, <type_traits>, etc.). This is just another such example. All that is required of compiler vendors to implement this magic is that they not exploit undefined behavior in unions for optimization purposes—and currently compilers already promise this (to the extent that it is being taken advantage of here).

This does impose a restriction on the client that, if these functions are used, std::pair cannot be specialized such that pair<const key_type, mapped_type> has a different layout than pair<key_type, mapped_type>. We feel the likelihood of anyone actually wanting to do this is effectively zero, and in the formal wording we restrict any specialization of these pairs.

Note that the key member function is the only place where such tricks are necessary, and that no changes to the containers or pair are required.

（强调我的）

允许从 std::map 的密钥中窃取资源？

Stealing resources from std::map's keys allowed?

c++

move-semantics

更新

Concerns

Undefined behavior