Comparing method issue when using STL sort

Question

Consider the following code. It is supposed to sort vector of vectors of ints in lexicographical order, i.e. by first column at first and then by second and so on. In my application I only care about first 6 out of 8 columns so was returning true in the case when values are equal for the first 6 columns.

And it caused problems (segmentation fault). It was working for 1000 data and it crashed for 1001. The example code is toy but sorting is a part of quite complicated program. I found out after long debugging that it was the cause of troubles. The program tries to sort array of all zeros with one (1, 0, ..., 0) entry.

Please any expert in C++, can you tell me what is wrong with the original (listed) program?

I was compiling it on 32bit and 64bit Linux and Visual Studio on 32bit Windows. It was always crashing. After the change in comment everything seems fine.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int COLS = 8;

bool compare (const vector<int>& r1, const vector<int>& r2)
{         
   for (int i = 0; i < COLS-2; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK
};

int main(int argc, char **argv) 
{       
    int Na = 20;
    vector< vector<int> > v( Na );

    for (int r = 0; r < v.size(); r++)
      v[r].resize(COLS, 0);
    v[0][0] = 1;

    cout << "Sorting\n";
    sort( v.begin(), v.end(), compare );
    cout << "Eof Sorting\n";         

    return 0;
}

The code comment already explains the problem. Sort needs a compare for less than, not for equality. — Bo Persson
– Bo Persson, Commented Mar 25, 2011 at 22:44
@Bo Persson: That won't cause a memory access violation, just an illogical result. — Puppy
– Puppy, Commented Mar 25, 2011 at 22:46
@DeadMG - It might if std::sort runs amok when it can't find a consistent ordering. Depends on the implementation though. — Bo Persson
– Bo Persson, Commented Mar 25, 2011 at 22:49
Does this mean that if I have weak inequality (<=) instead of < in comparing function then its wrong if I use sort? — rycho
– rycho, Commented Mar 25, 2011 at 23:38

Jollymorphic · Accepted Answer · 2011-03-25 22:48:35Z

4

I think you are blowing the stack. The sort function is implemented recursively, so if you give inconsistent answers about the order relationships among elements, the algorithm may fail to terminate.

answered Mar 25, 2011 at 22:48

Jollymorphic

3,53018 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mark Ransom · Accepted Answer · 2011-03-25 22:49:37Z

4

Your comparison function must return false when the inputs are equal, not true.

answered Mar 25, 2011 at 22:49

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

2 Comments

rycho Over a year ago

Thats right. But I am still thinking why i.e. don't fully understand it

Mark Ransom Over a year ago

@user677514, my bet is on Jollymorphic's answer.

MacGucky · Accepted Answer · 2011-03-25 22:53:19Z

2

The problem is your compare-function:

bool compare (const vector<int>& r1, const vector<int>& r2)
{         
   for (int i = 0; i < COLS-2; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK
};

If the elements are equal the expression r1 < r2 is false - but in case of equality (in your case if first 6 ints are equal) you return true.

answered Mar 25, 2011 at 22:53

MacGucky

2,50417 silver badges17 bronze badges

Comments

Mark Wilkins · Accepted Answer · 2011-03-25 22:54:58Z

1

This is not necessarily related to the question (it would not contribute to a crash), but the code is skipping one column. The code compares 6 (8-2) columns and then (if using the uncommented code), it would compare the last column. The next-to-last is not examined. However, that might be the intent ... if so, though, a comment would probably be good if the code has to exist for any amount of time.

answered Mar 25, 2011 at 22:54

Mark Wilkins

41.3k5 gold badges61 silver badges111 bronze badges

Comments

Blastfurnace · Accepted Answer · 2011-03-26 00:13:18Z

1

If you want to sort in lexicographical order you can use the standard library:

bool compare (const vector<int>& r1, const vector<int>& r2)
{  
   return std::lexicographical_compare(r1.begin(), r1.begin()+6, r2.begin(), r2.begin()+6);
}

answered Mar 26, 2011 at 0:13

Blastfurnace

18.7k57 gold badges61 silver badges73 bronze badges

Comments

Will · Accepted Answer · 2011-03-25 22:48:58Z

0

I expect you are running off the end of one of your vectors, which will have undefined results in release builds.

On linux, run your program using the excellent Valgrind.

You can also make your code so it only examines actual slots in the vectors, such as:

bool compare (const vector<int>& r1, const vector<int>& r2)
{  
   const int max = std::min(r1.size(),r2.size());
   for (int i = 0; i<max; i++)
     if ( r1[ i ] != r2[ i ] )
      return (r1[ i ] < r2[ i ]);
   return r1.size() < r2.size();
};

However, if you are expecting an exact number of slots then that's a logic bug and making your compare function ignore it is not necessarily a good solution.

answered Mar 25, 2011 at 22:48

Will

76k43 gold badges177 silver badges256 bronze badges

1 Comment

rycho Over a year ago

In the real program there is assertion that sizes are equal.

Collectives™ on Stack Overflow

Comparing method issue when using STL sort

6 Answers 6

Comments

2 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

2 Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related