CODEWITHSUNDEEP
c++comparefunctorstdsetequivalence
izaak_pyzaak
izaak_pyzaak

Reputation: 960

std::set. Custom set of sets

Word.

I have a struct, containing a single field that I would like set to use for comparison and equivalence, and other fields as metadata:

struct read_tag{
    unsigned int read_id; // want std::set to use this
    int offset;           // metadata
    bool orientation;     // metadata
};

I have a functor to do the job:

struct read_tag_compare {
    bool operator() (const read_tag &a, const read_tag &b) const {
        return a.read_id > b.read_id
    }
};

and decl. the required set as

std::set<read_tag, read_tag_compare> block;

Everything so far compiles. The problem is below:

How do I make a set containing std::set<read_tag, read_tag_compare>. I want something like this:

std::set< std::set<read_tag, read_tag_compare> > blocks;
blocks.insert(a_block); // comp error

But this gives me a very large, and hard to decipher error.

I thought it would recursively check how the inner sets are compared and extend this to the outer sets. All one had to do is define the comparator for the inner most set.

For example

std::set<std:set<unsigned int>> set_o_sets;

works fine, without me having to define how to compare std::set<unsigned int>

Any help is mucho appreciated :D

Upvotes: 0

Views: 855

Answers (2)

Zeta
Zeta

Reputation: 981

It compiled with no error with my g++-5.3.1 ubuntu..

#include<set>
#include<iostream>
using namespace std;

struct read_tag{
    unsigned int read_id; // want std::set to use this
    int offset;           // metadata
    bool orientation;     // metadata
};
struct read_tag_compare {
    bool operator() (const read_tag &a, const read_tag &b) const {
        return a.read_id > b.read_id;
    }
};
struct read_compare {
bool operator() (const set<read_tag, read_tag_compare> &a, const     set<read_tag, read_tag_compare> &b) const {
    return true;
}
};

int main()
{
    set<read_tag, read_tag_compare> block;
    set<set<read_tag, read_tag_compare>, read_compare> blocks;
    blocks.insert(block)
}

Above was what I compiled.

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 476990

The <-comparison on std::set uses std::lexicographical_compare without comparator, i.e. it just forwards to < on the element type. (This is a limitation of the standard library, since this is defined for all containers, not just the ordered-associative ones.) So what you need is a custom comparator for sets of sets that uses the correct overload of lexicographical comparison:

using read_tag_set = std::set<read_tag, read_tag_compare>;

struct read_tag_set_compare {
    bool operator()(const read_tag_set &a, const read_tag_set &b) const noexcept {
        return std::lexicographical_compare(a.begin(), a.end(),
                                            b.begin(), b.end(), a.key_comp());
        //                                                      ^^^^^^^^^^^^
    }
};

Now use: std::set<read_tag_set, read_tag_set_compare>

The code shows why there isn't an obvious "fix" to the ordered associative containers that would make this "just work": If the containers use custom, stateful predicates, then it's not in general guaranteed that the members of two distinct containers can actually be compared with one another at all. All you know is that the elements within one container are comparable with that container's comparator. So when you're using a custom comparator, you better also say explicitly how two distinct containers relate, and you assert explicitly that it makes sense to compare two containers.

Upvotes: 3

Related Questions