C++ std::set and std::multiset

Question

In C++ by default both std::set and std::multiset have std::less<T> as their comparator. Can anyone please explain how does std::multiset allow duplicates and std::set does not?

score 7 · Answer 1 · answered May 20 '15 at 02:43

7

Both start with the equivalent an upper_bound on the existing contents to find the correct insertion point for the new item.

std::set then checks whether that found an existing item with a key equal to the new key, and if so returns, signaling failure.

std::multiset just inserts the new item at that point (and if it didn't return in the step above, std::set does the same).

answered May 20 '15 at 02:43

Jerry Coffin

476,176
80
629
1,111

3

I think std::set is checking for equivalence, not equality, isn't it? In particular, one can use a type that only defines `operator<` (strict weak ordering), but not `operator==`. – vsoftco May 20 '15 at 02:54
Does this mean the return value of `upper_bound` can be effectively used as a hint to `insert`? – Lingxi May 20 '15 at 03:07
@Lingxi probably, but it is not going to improve on the total number of comparisons required to insert, since you pay for the `upper_bound`. – vsoftco May 20 '15 at 03:12

score 4 · Answer 2 · edited May 23 '17 at 12:32

To follow up on Jerry's answer, note that std::set and std::multiset assume that the elements are comparable via a strict weak ordering by operator<. In particular, the elements do not have to be comparable under operator==. std::set only allows non-equivalent elements, whereas std::multiset allows in addition equivalent elements. This is slightly different from equality/non-equality. Two elements A and B are equivalent whenever !(A < B) && !(B < A), and it is this latter condition that is checked by std::set::insert, and if true, the element is not inserted.

Example Live on Ideone

#include <iostream>
#include <set>

struct Foo
{
    int _x, _y, _z;
    Foo(int x, int y, int z): _x(x), _y(y), _z(z) {}
    bool operator<(const Foo& rhs) const // weak majorization
    {
        return (_x < rhs._x) && (_x + _y < rhs._x + rhs._y) &&
               (_x + _y + _z < rhs._x + rhs._y + rhs._z) ; 
    }
};

int main()
{
    std::set<Foo> setFoo;
    // try to insert 2 equivalent elements
    setFoo.insert(Foo{1, 2, 3}); 
    if(setFoo.insert(Foo{1, 2, 0}).second == false) // failed to insert
        std::cout << "Equivalent element already in the set!" << std::endl;
}

C++ std::set and std::multiset

2 Answers2