Thread: Sort of vector of custom objects

1. Sort of vector of custom objects

Hello everyone. I'm working on a code for ascertaining the minimum penalty of an assignment problem.

The basic complication of my code is this:
I have a vector of objects of a custom struct. The struct has a member, which is an integer. I need to keep the vector sorted according to that member, even when objects are added to or deleted from the vector. To illustrate the problem, I'll give an example.

Code:
```typedef struct examplestruct{int i;
char c;
...} es;

int function(void)
{vector<es> ObjectTable;
//insert an object so that the vector remains sorted according to i
insertobject( newobject, &ObjectTable);
//deleting the top element of the vector
deleteobject(&ObjectTable);
return 0;}```
I have tried to do it using bubblesort. But it's too slow. Can anyone tell me a quicker way to do this? Something like implementing heap sort? I still have got no idea how to make a heap out of it. Any help will be appreciated.

The detailed premises of the problem is this: There are a number of jobs, and with each job a completion time and a cost coefficient. We are to ascertain the optimal sequence of jobs for which the penalty is minimum. Now, suppose we are given jobs A, B, C, D and E. We find out the lower bound of penalties for all the jobs. Suppose we find B has the lowest penalty. Then we find out the lower bound of penalties for BA, BC, BD and BE. We continue this until we have the best value and a complete sequence. The way I have implemented this in a code: I have created two structs. One is Job, with the completion time and cost coefficient as members. The other is Node. Nodes have a Job Array and a Penalty as members. Now, we have a vector of Nodes which we need to keep sorted according to the penalty. We need to insert new Nodes and delete the expanded Nodes.

I have included my code. The pushInTable function inserts the new Nodes in a sorted vector. But it slows down remarkably when we give more than 20 jobs as input. Any remarks to improve the execution time of the code is welcome.

2. I think you can use for_each with a lambda or std::sort with a lambda as well.

Edit : This is some code I use where one of my structures is sorted by an unsigned long int.

Code:
```    std::sort(tmp.begin(), tmp.end(),
[](const point &p1, const point &p2) {
return p1.peanokey < p2.peanokey;
});```
Edit edit : I didn't actually read all of your post but it should be fairly simple to keep your insertions ordered just so long as your insertion routine will relocate insertion sites if the equality conditions are not met.

3. If less-than is all you need to make a comparison, you might as well make it an operator. Not saying that using a lambda is a bad idea. In fact, sorting needs might be different from other logic that you need in your program.

4. Thanks for the suggestions. But will using for_each with lambda improve the performance as much as using heaps?

5. I don't think for_each is a heap sort or something you really want to use if performance matters. You're better off using std::sort which I think has shown some pretty good benchmarks, if I'm not mistaken.

6. If you need to keep things sorted every time you insert an object, you really should be using something like a heap (std::set could be useful). Otherwise you will end up sorting every time you insert an object, which is prohibitive (O(N) inserts * O(NlogN) per sort = O(N^2logN)).

Code:
```typedef struct examplestruct{
int i;
char c;
...
} es;```
This can be simplified to
Code:
```struct es
{
int i;
char c;
...
};```

7. Originally Posted by Elysia
If you need to keep things sorted every time you insert an object, you really should be using something like a heap (std::set could be useful). Otherwise you will end up sorting every time you insert an object, which is prohibitive (O(N) inserts * O(NlogN) per sort = O(N^2logN)).
Actually, in my code, that's what I have done. Sorting it every time an element is added seems cumbersome. In my code, the objects are sorted according to the member LB.
Here is the code for inserting node a into the MainTable which is sorted according to node.LB:

Code:
```int pushInTable ( node a, vector<node>& MainTable)
{
int i;
if (MainTable.size() > 0)
{
for ( i = 0; (i < MainTable.size())&&(MainTable[i].LB < a.LB); i++ )
{
}
MainTable.insert( MainTable.begin() + i, a);
}
else
MainTable.push_back (a);
return 0;
}```
Could the same thing be done with set? Could you please tell me how to implement it?

8. Originally Posted by Elysia
Otherwise you will end up sorting every time you insert an object, which is prohibitive (O(N) inserts * O(NlogN) per sort = O(N^2logN)).
A simple insertion into the sorted position means O(N) inserts * O(N) per insertion => O(N^2), i.e., it would be about as bad as insertion sort, because that is what it would be if enough objects were inserted.

Originally Posted by Mycroft Holmes
Could the same thing be done with set? Could you please tell me how to implement it?
If you have defined operator< for node, e.g.,
Code:
```bool operator<(const node& lhs, const node& rhs)
{
return lhs.LB < rhs.LB;
}```
It could be as simple as:
Code:
```int pushInTable(node a, set<node>& MainTable)
{
MainTable.insert(a);
return 0;
}```
However, if two different nodes could have the same LB value, then you should use a multiset instead.

9. Thank you all!

Well, I got it now. The execution time has improved tremendously. It wouldn't have been possible for me to do this without the help of you guys. Thank you all!

PS. I've attached the improved code here, if anyone wishes to see it.

• The typedef of the job and node structs is unnecessary since this is C++.
• Since all the members of the job and node structs are public, operator< does not have to be a friend.
Code:
```node a;
a.Expanded = it->Expanded;
a.JobArray = it->JobArray;
a.LB = it->LB;
expandednodes = expandNode (a, JobTable, jobnos);```
It seems simpler to me to just write:
Code:
`expandednodes = expandNode(*it, JobTable, jobnos);`
• Instead of looping over expandednodes to insert one by one into MainTable, you can write: MainTable.insert(expandednodes.begin(), expandednodes.end())
• You can use the generic algorithm std::find_if instead of writing a loop to find if JobTable[i].name == chosen_node.JobArray[j].name. If you do use such a loop, then flag should be a bool, not an int.