多集何时排序？插入，迭代，两者？

Question

我有一个包含指向自定义类型的指针的多集。我为多集提供了一个自定义排序器，用于比较自定义类型的特定属性。

如果我更改任何给定项目的属性值（以影响排序顺序的方式）。我是否必须从集合中取出该项目并重新插入以保证订购？或者在我创建迭代器（或 foreach 循环）的任何时候，我仍然会按顺序获取项目？

我可以为自己做一个快速测试，但我想知道这种行为在任何平台和编译器上是否一致，或者它是否是标准的。

编辑：这是我试过的一个例子。我注意到两件事。在多集中，如果我在删除键之前更改用于比较的值，我将无法再删除它。否则，我最初的删除和重新插入的想法似乎是最好的方法。

#include <stdio.h>
#include <set>

struct NodePointerCompare;

struct Node {
    int priority;
};

struct NodePointerCompare {
  bool operator()(const Node* lhs, const Node* rhs) const {
        return lhs->priority < rhs->priority;
  }
};



int main()
{
    Node n1{1};
    Node n2{2};
    Node n3{3};
    
    std::multiset<Node*, NodePointerCompare> nodes;
    nodes.insert(&n1);
    nodes.insert(&n2);
    nodes.insert(&n3);
    
    printf("First round\n");
    
    for(Node* n : nodes) {
      printf("%d\n", n->priority);
    }
    
    n1.priority = 10;

    printf("Second round\n");

    for(Node* n : nodes) {
      printf("%d\n", n->priority);
    }

    n1.priority = 1;

    printf("Third round\n");
    nodes.erase(&n1);
    n1.priority = 10;
    nodes.insert(&n1);

    for(Node* n : nodes) {
      printf("%d\n", n->priority);
    }
    

    return 0;
}

这是我得到的输出

First round
1
2
3
Second round
10
2
3
Third round
2
3
10

Answer 1

http://eel.is/c++draft/associative.reqmts#general-3

For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value.

以影响对象与关联容器中其他对象比较的方式更改对象是完全非法的。

如果你想这样做，你必须从容器中取出对象，应用更改，然后放回容器中。看看 https://en.cppreference.com/w/cpp/container/multiset/extract 如果这是你想要的做。

Answer 2

容器必须始终保持排序，因为 begin 具有恒定的复杂性。更改容器中元素的比较顺序是 undefined behavior per [associative.reqmts.general]/3 (and [res.on.functions]/2.3):

For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value.

您可以使用节点句柄通过临时将元素从容器中移除来有效地修改元素，尽管对于只是指针的元素而言，唯一的效率是避免内存（取消）分配。

Answer 3

When is a multiset sorted? Insertion, iteration, both?

标准没有明确规定，但实际上顺序必须在插入时确定。

If I change the value of the attribute on any given item (in a way that would influence the sorting order). Do I have to remove the item from the set and re-insert it to guarantee ordering?

您不能更改元素在集合中的顺序。

但是，您可以提取 + 修改 + 重新插入，而不是擦除 + 插入具有不同值的元素，这应该稍微更有效（或明显更有效，具体取决于元素类型）。

Here is an example I tried.

示例的行为未定义。

多集何时排序？插入，迭代，两者？

When is a multiset sorted? Insertion, iteration, both?

c++

std

language-lawyer

data-structures