CODEWITHSUNDEEP
c++set
Vojin
Vojin

Reputation: 153

How do I print all elements in set?

I have trouble printing out elements in set. 

std::set<triple, Compare> edges;
for (int i = 0; i < n; i++)
            for (std::list<std::pair<int, int>>::iterator j = graph[i].begin(); j != graph[i].end(); j++)
                edges.insert(makeTriple((*j).second, i, (*j).first));

        for (std::set<triple, Compare>::iterator j = edges.begin(); j != edges.end(); j++)
            printf("%d and %d\n\n", (*j).first + 1, (*j).second + 1);

Only 7 elements are printed of of 13. Compare function looks like:

bool operator()(const triple &a, const triple &b) const
    {
        if (a.distance == b.distance && a.first == b.first)
            return (a.second < b.second);
        if (a.distance == b.distance && a.second == b.second)
            return (a.first < b.first);
        return (a.distance < b.distance);
    }

Upvotes: 2

Views: 4668

Answers (2)

Christophe
Christophe

Reputation: 73366

The printing is fine: it shows you what is in the set. A shorter version could be: 

   for (auto j = edges.begin(); j != edges.end(); j++)
        printf("%d and %d\n\n", j->first + 1, j->second + 1);

or even: 

   for (auto e: edges)
        cout << e.first+1 <<" and "<< e.second+1<<endl<<endl;

The problem is in the comparator. At the insertion, the set compares the element that you want to insert to the elements already in the set. If there is some "equality" (based on your comparator), the element is not inserted.

Your symptoms tell us that your comparator doesn't meet the compare requirements of the standard library, which is a strict weak ordering.

You can easily test it yourself and compare your different triples. If you take Compare comp;, those that are !comp(a,b) && !comp(b,a) are considered equal.

Take the following triplets (distance, first, second): for a (1, 2, 3) and for b (1,3, 2). You can easily !comp(a,b)&&!comp(b,a) turns to !(1<1)&&!(1<1) which is true. So se set would consider them as equal and only one of the two would be in your end results.

How to correct it?

You need to handle the case where the distances are equal but first is different and second is different. So in the end, what matters the more, first or second ?

Assuming that it's first you could write: 

bool operator()(const triple &a, const triple &b) const
{
    if (a.distance == b.distance && a.first == b.first)
        return (a.second < b.second);
    if (a.distance == b.distance)
        return (a.first < b.first);
    return (a.distance < b.distance);
}

or in a more compact way: 

bool operator()(const triple &a, const triple &b) const
{
    return tie(a.distance,a.first, a.second)< tie(b.distance,b.first, b.second);
}

Unfortunately for you, the compact way is C++11 so if auto doesn't work at school, tie won't either

Upvotes: 1

Ted Lyngmo
Ted Lyngmo

Reputation: 117298

Your Compare function does not fulfill the requirement

The return value of the function call operation applied to an object of a type satisfying Compare, when contextually converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

The most obvious fix would be:

bool operator()(const triple &a, const triple &b) const {
    if (a.distance == b.distance) {
        if(a.first == b.first)  return a.second < b.second;
        else                    return a.first < b.first;
    } else                      return a.distance < b.distance;
}

This can however be done simpler with std::tie from <tuple>:

bool operator()(const triple &a, const triple &b) const {
    return
        std::tie(a.distance, a.first, a.second) < std::tie(b.distance, b.first, b.second);
}

Demo

Upvotes: 1

Related Questions