Блог пользователя PraveenDhinwa

Автор PraveenDhinwa, 11 лет назад, По-английски
  • 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.

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks man!!

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I think It's

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

better than make_pair

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please explain the reason behind this ??

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?)

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        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

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Use std::tie instead of make_pair

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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).