0

I am trying to sort vector of pair of pair and int as below. But not getting expected output. In the actual output, the last element is supposed to come before the second element.Can someone please explain what i am missing?

int main()
{
   using elem_type = std::pair<std::pair<int,int>,int>;
   std::vector<elem_type> vec;

   vec.push_back(std::make_pair(std::make_pair(3, 1), 2));
   vec.push_back(std::make_pair(std::make_pair(6, 5), 4));
   vec.push_back(std::make_pair(std::make_pair(6, 4), 7));
   vec.push_back(std::make_pair(std::make_pair(5, 4), 6));

   auto cmp = [](const elem_type & left, const elem_type & right){
      return  ((left.first.first< right.first.first) 
               && 
              (left.first.second < right.first.second));
    };

  std::sort(vec.begin(), vec.end(), cmp);

  //print sorted vector
  for(size_t i = 0; i < vec.size(); ++i){
    std::cout << vec[i].first.first << " " << vec[i].first.second << " " << vec[i].second << "\n";
   }

}

Expected output 

3 1 2
5 4 6
6 4 7
6 5 4

Actual output

3 1 2
6 5 4
6 4 7
5 4 6
nipun510
  • 27
  • 6

1 Answers1

4

You haven't explained how you want to sort your triples, so all I can say is that your expectations are wrong.

Your comparison function considers your last three elements to be equal.

A triple (x0,x1,x2) is considered less than another triple (y0,y1,y2) if x0 < y0 and x1 < y1. For example, when comparing (6,4,7) and (6,5,4), neither triple is considered less than the other because the first number in each triple is the same (6 < 6 is false). Similarly, (5,4,6) is considered equal to (6,4,7) because neither is less than the other (4 < 4 is false).

The only thing you might reasonably expect is that (5,4,6) < (6,5,4), but your comparison function also says both of those are equal to (6,4,7). In other words, the function claims there are values a, b, c where a = b and b = c but a < c. This makes no sense, so your comparison function is broken.

If all you want is a lexicographical ordering, you don't need to do anything special:

std::sort(vec.begin(), vec.end());

std::pair sorts by its first component first; if those are equal, it compares the second components. That seems to be exactly the behavior you expect.

melpomene
  • 84,125
  • 8
  • 85
  • 148
  • Thanks melpomene, I missed trasitivity of incomparibility of strick weak ordering.My comparision function doesn't statisfy it.[link](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings) – nipun510 May 10 '19 at 23:38