C++关联容器 - 为什么标准没有定义交换和替换密钥的方法？
我需要替换特定的键值，而 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);
我缺少什么吗？
I need to replace specific key values, while the rest of the value_type is left untouched. What I actually need to do, is copy the value, erase the entry and insert it with changed key value again. This is absolutely bad. I need to copy the whole value_type twice, and deallocate/allocate again.
Why the standard doesn't define methods like this:
// 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);
Is there anything I'm missing?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我认为这是一个抽象问题。该标准没有具体说明容器如何实现，它只指定了某些操作的最大复杂性，并将其余操作留给实现。
如果标准要添加一个replace_key函数，它还必须指定它应该具有与现有擦除-插入组合不同的复杂性。如何在不泄露实现细节的情况下做到这一点？如果不能保证该函数在所有实现上都更快，那么它就毫无用处。
当您说它显然会更快时，您就对标准试图避免的实现细节做出了假设。
I think this is an abstraction problem. The standard doesn't say exactly how the containers are to be implemented, it only specifies the maximum complexity of some of the operations and leaves the rest to the implementation.
If the standard were to add a
replace_keyfunction, it would also have to specify that this should have a different complexity than the existing erase-insert combination. How can it do that without leaking implementation details? If the function isn't guaranteed to be faster on all implementations, it is pretty useless.When you say that it would obviously be faster, you make assumptions about implementation details that the standard tries to avoid.
这是因为更改键可能会影响关联容器的结构。值得注意的是，
std::map是一棵典型的红黑树，一旦修改一个键（例如，旋转子树），树结构就会发生变化。在某些数据结构中，甚至不允许这样的动态变化。因此，将此类操作公开为关联容器中的标准是具有挑战性的。关于您所关心的开销，一旦您将 value_type 作为指针或引用，删除/插入一对的开销并不算太糟糕。
This is because changing a key could affect the structure of an associative containers. Notably,
std::map, which is a typically Red-Black tree, the tree structure mostly will be changed once you modify a key (e.g., rotating sub trees). In some data structures, even such dynamic changes are disallowed. So, it is challenging to expose such operation as a standard in an associative container.Regarding the overhead you concerned, once you have value_type as a pointer or reference, the overhead of deleting/inserting a pair isn't too bad.
好吧，老实说，无论如何，它都会在屏幕后面导致插入和删除操作，唯一的区别是值部分不会被复制。虽然这似乎是您最关心的问题，但除非您的对象在大型容器中复制量很大，否则重新稳定有序容器的更新操作无论如何都会更重。
现在，这需要一些重要的更改，但是比关联容器更进一步，我可以看到的两个最重要的是：
std::pair类需要更新，因为您必须能够更新密钥无需创建新的对（因为这也会复制值对象）。我认为主要问题在于第一个，因为 std::pair 目前实际上是一个非常简单的包装器，您的建议将删除该原则并为其添加一些（不必要的）复杂性。另请注意，调用 2 实际上并未添加新功能，而是包装了一个系统，开发人员可以通过引用等轻松管理自己。如果他们将所有这些包装添加到 std，它将成为一个非常庞大且臃肿的库。
如果你想要这个原则，你应该寻找更复杂的库（可能boost有一些）。或者您应该简单地使用引用/shared_ptr 作为您的 value_type。
Well, honestly behind the screens it would result into an insert and delete operation anyhow, with the sole difference that the value-part will not be copied. While this seems to be your biggest concern, unless your object is very heavy on copying, in a large container, the update operation to re-stabilize the ordered container will be heavier anyhow.
Now this would require some important changes however going further than the associative containers, the two most important I can see are:
std::pairclass needs an update, because you must be able to update the key without creating a new pair (as this would also copy the value object).I think the main problem lies with the first one, as
std::pairis at the moment actually a very simple wrapper, and your proposal would delete that principle and add some (unnecessary) complexity to it. Also note that call 2 does not actually add new functionality but wraps a system the developer could manage himself easily through references and the like. If they would add all this wrapping to std, it would become a really huge bloated piece of library.If you want this principle, you should look for more complex libraries (probably boost has some). Or you should simply use a reference/shared_ptr as your value_type.
现在，您可以使用
.extract(key)（C++17 起）。https://en.cppreference.com/w/cpp/container/map/摘录
Now, you can, with
.extract(key)(since C++17).https://en.cppreference.com/w/cpp/container/map/extract
我不明白为什么一开始没有添加它，我知道这太糟糕了。我猜他们只是添加了他们认为绝对必要的内容。
我想我在某处读过 Boost.MultiIndex 提供了这种能力。
I don't why it was not added in the first place, and i understand that it is too bad. I guess they just added what they felt was absolutely necessary.
I think i have read somewhere that Boost.MultiIndex provided this ability.
关联容器的实现方式不允许以有效的方式更改“密钥”。为了明确这一点，它没有提供替换密钥的便捷方法。关联容器还必须移除并再次插入盖子下方。
Associative containers are implemented in a way that does not allow to change the 'key' in an efficient manner. To make this explicit it does not provide convienence methods to replace a key. The associative container would also have to remove and insert again under the covers.