How can I sort a vector group elements in c++?

Question

I'm trying to search the minimal element in a adjacency matrix. For get this, I want to sort elements row to row.

To optimize the sorting, I want only sort the significant elements of this vector, as this form:

[0,   5,   9,   7]
[inf, 0,   6,   3]
[inf, inf, 0,  12]
[inf, inf, inf, 0]

The sorted matrix must be this:

[0,   5,   7,   9]
[inf, 0,   3,   6]
[inf, inf, 0,  12]
[inf, inf, inf, 0]

I'm trying to use std::vector<int> and the C++ sort function, as this form, but it fails.

When I try to execute with 6 elements, the program show that error:

malloc(): memory corruption (fast): 0x000000000cb12490

And with other quantities, some times produces similar errors or return -1

My matrix is implemented with vector<vector<int> >

//Sort matrix row to row
for(int i = 0; i < numnodes; i++){
    sort(matrix[i].begin()+1+i, matrix[i].end());
    if(matrix[i][i+1] < minimal){
        minimal = matrix[i][i+1];
        row = i;
    }
}`

How can I solve this?

Is this possibly the same problem as this? http://stackoverflow.com/questions/36777834/sort-stdvectorint-but-ignore-a-certain-number — Christian Hackl, Jan 12 '17 at 09:50
@ChristianHackl nope. I want to sort the vector from i position to end — AlmuHS, Jan 12 '17 at 09:52
where does it exactly fail? as I see your code generates your expected result — pergy, Jan 12 '17 at 09:55
@UnholySheep Inf means infinite. In my real code, i have setted as 99999. When I try to execute this code, it produces memory errors I haven't debugger, only knows that it returns -1 — AlmuHS, Jan 12 '17 at 09:56
If you get errors you should probably include them as part of your question. And you should get a debugger and learn how to use it — UnholySheep, Jan 12 '17 at 09:59
@pergy It runs, but feels not sort correctly The results are fully diferent from original code — AlmuHS, Jan 12 '17 at 10:05
@AlmuHS well, numbers are in acsending order every raw and minimal value is picked. it cannot be sorted any better :P — pergy, Jan 12 '17 at 10:08
@pergy now feels sort correcty, but continues producing memory errors — AlmuHS, Jan 12 '17 at 10:33
Well, if you want all the infs as first values in the sorted vectors, you can use ints and define inf as... -inf — Bob__, Jan 12 '17 at 10:36
When you call sort(), you're creating an iterator to the beginning of the vector and incrementing multiple times it. Your matrix has the same number of rows as columns, yes? What happens on the last iteration of your for loop? I assume numnodes is equal to the number of elements in one vector. Given a 4x4 matrix, i=3. So, you're creating an iterator to the beginning of the array, and incrementing it (1+i) times. You're trying to access the fifth element of a four-element collection. Incrementing an iterator beyond the end of a collection is undefined behavior. — bindsniper001, Jan 12 '17 at 10:43

score 2 · Accepted Answer · answered Jan 12 '17 at 10:38

2

You should add guard for out of range access. Most probably the error you see is caused by matrix[i][i+1] when i + 1 is out of bounds for matrix[i]. I believe this should be a fixed version of the code.

//Sort matrix row to row
for(int i = 0; i + 1 < matrix[i].size() && i < numnodes; i++){
    sort(matrix[i].begin()+1+i, matrix[i].end());
    if(matrix[i][i+1] < minimal){
        minimal = matrix[i][i+1];
        row = i;
    }
}

answered Jan 12 '17 at 10:38

Ivaylo Strandjev

69,226
18
123
176

This sensibly ignores the final row, where OP was sorting an empty sequence. I assume numnodes == matrix.size() == matrix[i].size(), so the loop condition can be simplified to `i + 1 < numnodes` – Caleth Jan 12 '17 at 10:45
I just try it, but continues faling with 6 elements – AlmuHS Jan 12 '17 at 10:46
@Caleth this is my assumption too, but as I lack context, decided to play it safe – Ivaylo Strandjev Jan 12 '17 at 10:47
@AlmuHS can you provide minimal example where we are able to reproduce the problem. I am pretty sure there is no problem left in the code you gave to us – Ivaylo Strandjev Jan 12 '17 at 10:48
Now fails also with 10 elements – AlmuHS Jan 12 '17 at 10:49
Introduce number of nodes: 10 node pos x pos y 1 85940 460 2 50256 1820 3 48201 1994 4 96595 2968 5 77079 2821 6 57712 4370 7 85988 431 8 16513 3177 9 96088 2281 10 90012 3282 Process returned -1 (0xFFFFFFFF) execution time : 3.631 s Press ENTER to continue. – AlmuHS Jan 12 '17 at 10:50
We need **code** that produces the error. If I have the input to an unknown program this does not help me too much. What I said is that I don't see errors in the code section you pasted after my fix so the error is some other piece of code. I can not possibly spot it without seeing the remaining code. Also please instead of posting as comment edit and extend your questions – Ivaylo Strandjev Jan 12 '17 at 11:05
The entire code is here: https://github.com/AlmuHS/Practica2_AMC/tree/work-in-progress – AlmuHS Jan 12 '17 at 14:47

How can I sort a vector group elements in c++?

1 Answers1