CODEWITHSUNDEEP
c++setstd
Yur3k
Yur3k

Reputation: 739

What is the right way to have a set of structs in c++?

I need to have a set of custom structs in order to be able to quickly retrive the instance with the smallest given parameter. However, I discovered that std::set considers some instances the same, even though they have different values. Here is my example program:

#include <set>
#include <iostream>

struct S
{
    int foo, bar;
    S(int foo, int bar): foo(foo), bar(bar) {}
};

inline bool operator<(const S& a, const S& b)
{
    return a.foo < b.foo;
}

int main()
{
    std::set<S> baz;
    baz.emplace(1, 2);
    baz.emplace(1, 3);
    std::cout << baz.size();

    return 0;
}

This program prints 1

std::set considers S(1, 2) and S(1, 3) to be the same. I'm guessing this is because bar is not used when comparing them. But I need the set to keep both elements, how do I solve this?

EDIT: I feel I have not stated my question correctly: I want to keep instances that are not exactly the same, but std::multiset does not work for me, because I don't want identical instances to be in the container

SOLUTION: I think I understand what was wrong. I assumed that if for 2 elements a < b and b < a were both true, it would result in undefined behaviour. But std::set checks for this, so it removes one of the elements. The best solution for me is to modify the comparator so it includes bar.

Upvotes: 2

Views: 383

Answers (6)

DevSolar
DevSolar

Reputation: 70411

It's not std::set that considers instances of S the same if they have the same foo, it's your own operator<.

So you either have to:

  • change your operator< (which would also affect sorts), or
  • use a different comparator for your set (the second type parameter), or
  • change your operator< to be fit for std::set and use a different Compare parameter for std::sort (or however you get the smallest element).

Bottom line, if you want a different compare functionality for std::sort (or whatever) and std::set, you need to provide different functionality.

As you did not really specify why your operator< looks the way it does (not considering S::bar), it's hard to tell what would match your intentions.

Upvotes: 3

Daniel Jour
Daniel Jour

Reputation: 16156

Perhaps as addition to the other answers:

std::set keeps a sorted set, and uses the <-relation created by the operator< to sort the elements.

So given two objects a and b ... if ! (a < b) and ! (b < a), then neither is a "less" than b, nor is b "less" than a. Therefore a == b - from the perspective of the sorted order however.

Upvotes: 1

Yksisarvinen
Yksisarvinen

Reputation: 22394

Simplifying a bit, std::set compares two elements twice when inserting:

  1. a < b
  2. b < a

If 1. is true, then a goes before b in ordering.
Else if 2. is true, then b goes before a.
Else (both are false), a and b are equivalent.

Since S{1, 2} < S{1, 3} == false and S{1, 3} < S{1, 2} == false according to your definition of operator <, they are deemed equivalent and std::set::emplace fails.

Upvotes: 2

Felipe Matos Mendes
Felipe Matos Mendes

Reputation: 61

You can try to use std::multiset http://www.cplusplus.com/reference/set/multiset/

Upvotes: 0

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 30005

This happens because you only compare foo, and if foo is equivalent, the objects are considered equivalent. std::set keeps only one of equivalent values. If bar makes objects unique, include bar in the comparison or else, if you still want to keep both (equivalent) values, use a std::multiset. Both are valid solutions depending on what you want to do.

Upvotes: 3

ChrisMM
ChrisMM

Reputation: 10103

If both foo and bar make S unique, then you can modify your operator< to use both variables, like so:

inline bool operator<(const S& a, const S& b)
{
    if ( a.foo == b.foo )
       return a.bar < b.bar;
    return a.foo < b.foo;
}

Upvotes: 1

Related Questions