PraveenDhinwa's blog

By PraveenDhinwa, 10 years ago, In English
  • Using constructors in C++

struct point { int x, y; point() {} // default constructor point (int _x, int _y) { x = _x; y = _y; } };

Another way


struct point { int x, y; point() {} // default constructor point (int x, int y): x(x), y(y) {} };
  • Using Comparison function in C++. For information of operator overloading visit link

struct point { int x, y; point() {} point (int x, int y) : x(x), y(y) {} // overloading of < operator bool operator<(const point &rhs) const{ // your main logic for the comparator goes here return make_pair(x,y) < make_pair(rhs.x, rhs.y); } };

Now A Sample Implementation

Thanks to Break-Neck for pointing out the problem with earlier a <= b in the code of cmp function, see the comment of Break-Neck comment for more details and also see the well commented cmp function.
You can also view link to know more about strict weak ordering in stl.


// please write your includes do not forget to include vector or direcly use include bits/stdc++.h bool cmp(int a,int b) { return a < b; // please view the first comment so as to understand the concept of strict weak ordering to be used in comparison if you want to use std:sort etc functions. Strict weak ordering means that specify the case when a is strictly less than b to true, all other cases to false. } int main() { int n; cin >> n; vector a; for (int i = 0; i < n; i++) { int x; cin >> x; a.push_back(x); } sort (a.begin(), a.end(), cmp); for (int i = 0; i < a.size(); i++) cout << a[i] << " "; return 0; }

PS. Please do comment if the article was useful or needs some changes or more explanation.

  • Vote: I like it
  • +29
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

It's very important: NEVER use a <= b in comparators for STL algorithms and data structures. All comparators must be like a < b. If one use comparation from the author's example for std::sort, std::map, std::set, they'll have WA. There is one thing more: in DEBUG mode Visul Studio always check that "less" operation is correct – never a < b and b < a and etc. Globaly, you should get STL less-comparators like "If I want the first parameter to be always before the second one (and never after) I must return true, otherwise false".

Hope this'll help you and you won't have some stupid bugs because of that.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you talking about strict weak ordering? it generates run-time error in VS. But what is disappointing is that its checking routine is incorrect actually and sometimes (or all the time) my comparator conforms to this standard but VS raises RE. Do you know why? and how to avoid?

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks man!!

    That was a stupid mistake, Thanks again to remind about strict weak ordering of stl :)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you mean the C++ standard library. STL is the pre-standard implementation from before 1994.

»
10 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I think It's

return (x == rhs.x) ? y < rhs.y : x < rhs.x;

better than make_pair

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain the reason behind this ??

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      as I know

      make_pair(x,y) < make_pair(rhs.x,rhs.y)
      

      is equivalent to

      pair<int,int> *a = new pair<int,int>(x,y), *b = new pair<int,int>(rhs.x,rhs.y);
      return (*a) < (*b);
      

      I mean that new objects must be created to use operator "<", which is reloaded for pair<T1,T2> (mb it's not?)

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        That's wrong. Temporary objects are allocated on stack, not in heap.

        However, if optimizer is not clever enough (which is rather rate situation), usage of pairs leads to extra memory assignments and constructor calls. You'd better try to benchmark both implementations (probably with looking at assembly code produced by your compiler) and tell everyone, what's the difference on your system

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Even better: tie(x,y) < tie(rhs.x, rhs.y). Does not copy (although that would be optimized away anyway in all likelihood.

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Use std::tie instead of make_pair

»
10 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Usually nowadays I make use of C++11 features to remove some of the boilerplate:

struct point { int x, y; };
// ...
sort(begin(a), end(a), [](const point& a, const point& b) { 
   return tie(a.x,a.y) < tie(b.x,b.y); });

If I want to create an instance of point, I just do { x, y } (possibly with a cast in the rare cases where the type cannot be inferred).

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You don't need to use [&], [] is enough.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good catch! I always forget what the default is, but it doesn't make a difference here anyways :)