Set storage confusion

Question

I have declared a structure like:

struct data{
   vector<string> att;
   string ds;
};

Now a set to store unique data from multiple data element

set<data> s;

based on different vector<string> att and string ds

How to do this?

You need some way to compare `data` elements. You can do this by overriding `operator<` or providing a [custom `Compare` functor to `set` as the second template parameter](http://en.cppreference.com/w/cpp/container/set). — Cornstalks, Nov 08 '15 at 16:18
Possible duplicate of [problems with c++ set container](http://stackoverflow.com/questions/14784620/problems-with-c-set-container) — Cornstalks, Nov 08 '15 at 16:19
@Cornstalks can you please provide code for the compare function for this particular case? — sb15, Nov 08 '15 at 16:22

score 2 · Answer 1 · answered Nov 08 '15 at 16:23

Without knowing anything about how you want your structure to be compared, you could try the following:

struct data
{
    vector<string> att;
    string ds;

    friend bool operator < (const data& lhs, const data& rhs)
    {
        if (std::lexicographical_compare(lhs.att.begin(), lhs.att.end(), rhs.att.begin(), rhs.att.end()))
        {
            return true;
        }
        else if (std::lexicographical_compare(rhs.att.begin(), rhs.att.end(), lhs.att.begin(), lhs.att.end()))
        {
            return false;
        }
        else
        {
            return lhs.ds < rhs.ds;
        }
    }
};

I'm not happy with this solution because it performs the lexicographical comparison twice, which is inefficient. Hopefully someone will come along with a better solution.

The basic idea is, for each member, compare left < right. If true, return true, otherwise compare right < left. If true, return false. Otherwise, continue to the next member.

@Cornstalks I don't know. Will that figure out how to compare the vectors? Will that make a copy of the vectors? — Neil Kirk, Nov 08 '15 at 16:32

score 0 · Accepted Answer · edited May 23 '17 at 11:51

Note: you can read more about the trick I'm using to compare things (std::tie) in Implementing comparison operators via 'tuple' and 'tie', a good idea?

std::string and std::vector already have operator< defined: for strings and for vectors. So we can use them with std::tie to create a temporary std::tuple (it just uses references to the data members, it doesn't create any copies, so it's efficient) for comparison.

Option 1: Providing `operator<`

std::set needs to compare its objects so it knows what's unique and how to sort things. It will do this by using operator< by default (via std::less), so if you provide that operator for your class it will use it. Like so:

struct data{
   vector<string> att;
   string ds;

   operator<(const data& other) {
      // Be sure to #include <tuple> for std::tie
      return std::tie(att, ds) < std::tie(other.att, ds);

      // If you don't want to (or can't) use std::tie, you can do this:
      // return att < other.att || (att == other.att && ds < other.ds);
   }
};
std::set<data> my_set; // Now it works.

Option 2: Providing a functor

This will use the Compare functor to compare two data objects (instead of operator<, so we don't need to define it):

struct Compare {
   bool operator()(const data& left, const data& right) const {
      return std::tie(left.att, left.ds) < std::tie(right.att, right.ds);

      // Again, if you don't want to (or can't) use std::tie, you can do this:
      // return left.att < right.att || (left.att == right.att && left.ds < right.ds);
   }
};
std::set<data, Compare> my_set; // Now it works.

Set storage confusion

2 Answers2

Option 1: Providing operator<

Option 2: Providing a functor

Option 1: Providing `operator<`