3

我需要替换特定的键值，而其余的value_type保持不变。我真正需要做的是复制值，擦除条目并再次插入更改后的键值。这绝对是糟糕的。我需要复制整个 value_type 两次，然后再次取消分配/分配。

为什么标准没有定义这样的方法：

// returns count of exchanged keys
size_type exchange_key(key_type const& x, key_type const& y);
// returns count of replaced keys
size_type replace_key(key_type const& old_key, key_type const& new_key);

有什么我想念的吗？

4

5 回答 5

0

我不知道为什么一开始就没有添加它，我知道它太糟糕了。我猜他们只是添加了他们认为绝对必要的内容。

我想我在某处读过Boost.MultiIndex提供了这种能力。

于 2011-07-22T08:29:28.320 回答
0

关联容器的实现方式不允许以有效的方式更改“键”。为了明确这一点，它没有提供替换密钥的便捷方法。关联容器还必须移除并再次插入盖下。

于 2011-07-22T08:31:03.140 回答
0

这是因为更改键可能会影响关联容器的结构。值得注意的是std::map，它是一个典型的红黑树，一旦你修改了一个键（例如，旋转子树），树结构大部分都会改变。在某些数据结构中，即使是这样的动态变化也是不允许的。因此，在关联容器中将此类操作作为标准公开是具有挑战性的。

关于您关心的开销，一旦您将 value_type 作为指针或引用，删除/插入一对的开销并不算太糟糕。

于 2011-07-22T08:33:47.117 回答
0

我认为这是一个抽象问题。该标准没有具体说明容器将如何实现，它只指定了一些操作的最大复杂性，其余的留给实现。

如果标准要添加一个replace_key功能，它还必须指定它应该具有与现有擦除-插入组合不同的复杂性。如何在不泄露实现细节的情况下做到这一点？如果不能保证该函数在所有实现上都更快，那它就毫无用处了。

当您说它显然会更快时，您对标准试图避免的实现细节做出假设。

于 2011-07-22T08:44:20.463 回答
0

好吧，老实说，在屏幕后面，无论如何它都会导致插入和删除操作，唯一的区别是不会复制值部分。虽然这似乎是您最关心的问题，除非您的对象在复制时非常繁重，否则在大型容器中，重新稳定有序容器的更新操作无论如何都会更重。

现在这将需要一些重要的更改，但是比关联容器更进一步，我能看到的两个最重要的是：

  1. 该类std::pair需要更新，因为您必须能够在不创建新对的情况下更新键（因为这也会复制值对象）。
  2. 您需要一个更新函数，从树中删除一对，从 1. 调用新逻辑，然后重新插入它。

我认为主要问题在于第一个问题，因为std::pair目前实际上是一个非常简单的包装器，您的建议将删除该原则并为其添加一些（不必要的）复杂性。另请注意，调用 2 实际上并没有添加新功能，而是包装了一个开发人员可以通过引用等轻松管理自己的系统。如果他们将所有这些包装添加到 std，它将成为一个非常庞大的库。

如果你想要这个原则，你应该寻找更复杂的库（可能 boost 有一些）。或者你应该简单地使用一个reference/shared_ptr 作为你的value_type。

于 2011-07-22T08:43:21.243 回答