Thread: Sort of vector of custom objects

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    21

    Question 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.
    Attached Files Attached Files
    Last edited by Mycroft Holmes; 02-23-2014 at 07:08 PM. Reason: typing error

  2. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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.
    Last edited by MutantJohn; 02-23-2014 at 08:30 PM.

  3. #3
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,616
    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. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    21
    Thanks for the suggestions. But will using for_each with lambda improve the performance as much as using heaps?

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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;
    ...
    };
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    21

    Arrow

    Quote Originally Posted by Elysia View Post
    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?
    Last edited by Mycroft Holmes; 02-24-2014 at 06:58 AM. Reason: Explanation for code

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,379
    Quote 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.

    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    21

    Talking 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.
    Attached Files Attached Files

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,379
    A few comments:
    • 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.
    • Instead of:
      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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Vector of pointers to vector of objects
    By Litz in forum C++ Programming
    Replies: 10
    Last Post: 11-06-2009, 03:29 PM
  2. Replies: 4
    Last Post: 04-28-2008, 04:13 PM
  3. custom class vector
    By -=SoKrA=- in forum C++ Programming
    Replies: 9
    Last Post: 07-08-2003, 01:14 PM
  4. STL Vector and Custom Struct!
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 06-23-2002, 07:58 AM
  5. help on some vector of custom class code
    By cozman in forum C++ Programming
    Replies: 1
    Last Post: 08-09-2001, 11:55 PM

Tags for this Thread