CODEWITHSUNDEEP
c++setcontainersstdmultiset
A Roy
A Roy

Reputation: 91

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

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?

Upvotes: 7

Views: 5018

Answers (2)

vsoftco
vsoftco

Reputation: 56577

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

Upvotes: 4

Jerry Coffin
Jerry Coffin

Reputation: 490728

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).

Upvotes: 7

Related Questions