CODEWITHSUNDEEP
c++data-structureslanguage-lawyerstd
cloudraven
cloudraven

Reputation: 2544

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

I have a multi-set containing pointers to custom types. I have provided a custom sorter to the multi-set that compares on a particular attribute of the custom type.

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? Or anytime I create an iterator (or a foreach loop), I will still get the items in order?

I can make a quick test for myself, but I wanted to know if the behavior would be consistent on any platform and compiler or if it is standard.

Edit: Here is an example I tried. I noticed two things. In a multi-set if I change the value that is used to compare before removing the key, I can no longer remove it. Otherwise, my original thought of removing and reinserting seems the best way for this to work.

#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;
}

This is the output I get

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

Upvotes: 2

Views: 626

Answers (3)

user4442671
user4442671

Reputation:

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.

It is simply illegal to change the change the object in a way that affects how it compares to other objects within the associative container.

If you want to do that, you have to get the object out of the container, apply the change to it, and put it back in. Have a look at https://en.cppreference.com/w/cpp/container/multiset/extract if that's what you want to do.

Upvotes: 4

Davis Herring
Davis Herring

Reputation: 39838

The container must remain sorted at all times because begin has constant complexity. Changing the comparison order of elements in the container is 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.

You can use node handles to efficiently modify elements by temporarily removing them from the container, although for elements that are just pointers the only efficiency is avoiding a memory (de)allocation.

Upvotes: 1

eerorika
eerorika

Reputation: 238351

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

The standard doesn't specify explicitly, but practically speaking the ordering must be established on insertion.

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?

You may not change the ordering of an element while it is in the set.

However, instead of erase + insert element with different walue, you can extract + modify + re-insert which should be slightly more efficient (or significantly, depending on the element type).

Here is an example I tried.

The behaviour of the example is undefined.

Upvotes: 2

Related Questions