-2

I'm writing a c++ program to sort int pairs according to its first element.

int a[5000][2];

I call the sort function with this command:

sort(a, a + n, cmp);

where n is the number of elements I want to sort, and cmp is defined like this:

bool cmp(int *a, int *b) {
    return a[0] < b[0];
}

I have already included <algorithm>. However, while compiling the file using g++, it failed with a large block of error info, all pointing to the lib file rather than my program. I'm sure the problem is with my calling sort function, because once I remove the sort function, the compilation succeeded.

Anyone knows what's wrong with my program?

Here's some of the error info:

In file included from /usr/include/c++/4.8/bits/stl_pair.h:59:0,
             from /usr/include/c++/4.8/bits/stl_algobase.h:64,
             from /usr/include/c++/4.8/bits/char_traits.h:39,
             from /usr/include/c++/4.8/ios:40,
             from /usr/include/c++/4.8/ostream:38,
             from /usr/include/c++/4.8/iostream:39,
             from milk2.cpp:7:
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’:
/usr/include/c++/4.8/bits/stl_algo.h:2226:70:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int (*)[2]; _Compare = bool (*)(int*, int*)]’
/usr/include/c++/4.8/bits/stl_algo.h:5500:55:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int (*)[2]; _Compare = bool (*)(int*, int*)]’
milk2.cpp:32:29:   required from here
/usr/include/c++/4.8/bits/stl_algo.h:2162:11: error: array must be initialized with a brace-enclosed initializer
   __val = _GLIBCXX_MOVE(*__i);

My program is milk2.cpp. The 7th line is:

#include <iostream>

and the 32nd line is the line calling sort function

Improve this question
3
  • 4
    "I'm sure the problem is in sort function" - nope. it's in your code. Commented Dec 7, 2015 at 0:22
  • Could you show at least some of the "large block of error info"? Commented Dec 7, 2015 at 0:24
  • milk2.cpp:32:29: required from here Look at line 32. Commented Dec 7, 2015 at 9:31

2 Answers 2

Reset to default
1

first of all show us errors. second thing is that, in the documentation of std::sort we can read about compare function:

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

so you cannot pass pointers to it since they are out of range :D im not sure how to use sort fucntion for two dimmensional array. but you can easily use it for your self-defined class. something like this (its not working code):

class foo {
public:
int x, y;
}

bool compare (foo one, foo two)
{
  return one.x > two.x;
}
int main () {
  foo data [N];
  sort(data, a + N, compare);
}

Update1: After some research and reading your updated post with the error i think that it is not about pointers exactly. Rather passing 2d array to the sort Function might be problematic. Fortunetly you sholud be ale to use std::sort for vector of vectors as was done here: How to sort a 2D array using the sort function in c++? There is also pointed out that arguments of the compare Function must be static. I think that you sholud modify your code in that way at first.

I have also found that it is possible to use std::sort for 2d array with this cool trick: https://www.quora.com/How-do-I-sort-a-2D-array-based-on-1-parameter-in-C++-using-an-STL-function Which you sholud try as well. It's about using static cast to pass to sort Function not 2d array but the array of Pairs.

And Here is the explanation why Array of arrays can not be used with sort: Sort a 2D character Array using sort() in C++ As written there, the point is that:

then you cannot sort "the pointers" because that data structure has no pointers at all... just 5000*2= 10 000 ints one after another

So your issue have combined reason of 1) using 2d array-> its not like you are sorting every second int, Rather your sort will work for all 10 000 ints without taking care that they are 2d... 2) so it's like sort is not sending adresses to your compare function. Instead it sholud send values which you are taking and using as pointers.

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

1 Comment

Sorry, I don't get what "the range" refers to. Could you tell me what it is?
1

EDITED

Instead of using a 2d int array (in essence treated as an 5000x2 1d array) you could represent your integer pairs as an array of your own integer pair struct

struct IntegerPair {
    IntegerPair(int a, int b) : a(a), b(b) { } 
    int a;
    int b;
};

Create your integer list using std::vector

#include <vector>
...
std::vector<IntegerPair> myIntegerPairs;

// enter your data
... myIntegerPairs.push_back(IntegerPair(ai,bi));

and use std::sort with a comparison function aimed at comparison of the first integer in your IntegerPair objects

std::sort(myIntegerPairs.begin(), myIntegerPairs.end(), compareByFirstInteger);
...
bool compareByFirstInteger(const IntegerPair &a, const IntegerPair &b)
{
    return a.a < b.a;
}
Improve this answer

3 Comments

You could just pass a and b by value -- it's no more copying than passing in pointers, and you save 2 pointer dereferences. It should be slightly faster.
Because what I want to sort is actually an (array of (array of 2)), a and b are both int[2]. Passing pointers seems the only way to write compare function, unless I use pair or define a struct. Do you know why passing pointers doesn't work?
See Dominiks last paragraph below, where he links to an existing SE thread ("Sort 2D character Array using sort() in C++). I think that threads answers your question well. If you want to use std::sort, you will have to use the struct solution described my answer, the "hackier" pair solution that Dominik links to in his Update 1 part of his answer below, or the vector method desrcribed in the existing SE "Sort 2D ..." thread. Alternatively, write your own custom sort function specifically for int[][] 2D vectors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.