sorting container

This is a discussion on sorting container within the C++ Programming forums, part of the General Programming Boards category; Hello I have a large stl container with name - surname (pair of two std::strings). I want to sort the ...

  1. #1
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630

    sorting container

    Hello

    I have a large stl container with name - surname (pair of two std::strings). I want to sort the whole container by surname.

    What approach should I use?
    Note that there are more than few 500 000 items (names/surnames).

    Thanks for help

  2. #2
    Registered User Queatrix's Avatar
    Join Date
    Apr 2005
    Posts
    1,342
    I would suggest doing it somthing like this:..
    Code:
    sort function
    {
       make a "current point" varible as "ZZZZZZZZZZZZZZZZZZZZZ" or somthing like it
       make a new array the same size as the original
    
       // never reset the "current point" varible
    
       loop through the whole new array
       {
          loop through the whole original array
          {
             if this surename is less than the one in the "current point" varible
             {
                set the "current point" varible to this surename 
             }
          }
          set this surename in the new array to the one in "current point" varible
       }
       // there, now you're new array is the old one, just sorted.
    }
    Of course, it's not actuall code, but you get the idea...

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,020
    EDIt: Just use a multimap. The elements will be sorted by the surname if you use it as a key.
    Last edited by King Mir; 05-02-2007 at 04:26 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Or, if you're already set on using something like a vector:

    Code:
    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <utility>
    #include <vector>
    
    typedef std::pair<std::string, std::string> TPair;
    typedef std::vector<TPair> TList;
    typedef TList::const_iterator TListIterConst;
    
    bool Comp(const TPair& PairA, const TPair& PairB)
    {
       return PairA.second < PairB.second;
    }
    
    void Dump(TListIterConst Begin, const TListIterConst& End)
    {
       while(Begin != End)
       {
          std::cout << Begin->second << ", " << Begin->first << std::endl;
          Begin++;
       }
    }
    
    int main()
    {
       TList List;
    
       List.push_back(TPair("foo", "bar"));
       List.push_back(TPair("orly", "yarly"));
       List.push_back(TPair("rofl", "copter"));
    
       Dump(List.begin(), List.end());
    
       std::sort(List.begin(), List.end(), Comp);
    
       Dump(List.begin(), List.end());
    
       return 0;
    }
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    It depends on the container. Use sort like in XSquared's example for vector or deque. Use the list's member sort method if you are using a list. For a map or set, if you aren't already sorted by surname, you should copy all the data to a vector and re-sort.

  6. #6
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630
    Can I put Comp function (from XSquared's example) in a class?
    Would you OOP guys do this? (I dont have any global functions in my programs)

  7. #7
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    41
    You could always put it in whatever class you think it belongs and make it static. You'd then pass it to sort() as ClassName::Comp.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    sort is a global function. So is operator<<. There's nothing wrong with making a function a non-member.

    You can make operator< for your class, but it probably doesn't make as much sense as a separate comparison function because your class can be sorted by name or surname and you'd have to pick only one of those for your operator< if you made one. It makes more sense to have to comparison functions, one for name and one for surname, and pass the correct one to sort. It's probably even better to make a function object:
    Code:
    struct CompSecond
    {
      bool operator()(const TPair& PairA, const TPair& PairB) const
      {
        return PairA.second < PairB.second;
      }
    };

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Or you could use TR1 binders.
    Code:
    typedef std::pair<std::string, std::string> person;
    std::vector<person> people;
    // ...
    std::sort(people.begin(), people.end(),
        tr1::bind(&person::second, _1) < tr1::bind(&person::second, _2));
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630
    Quote Originally Posted by CornedBee View Post
    Or you could use TR1 binders.
    Code:
    typedef std::pair<std::string, std::string> person;
    std::vector<person> people;
    // ...
    std::sort(people.begin(), people.end(),
        tr1::bind(&person::second, _1) < tr1::bind(&person::second, _2));
    Seems like the best option. What do you think?

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    If you have tr1, then I'd say yes. Something as simple as sorting by surname doesn't need a separate function object.

    It's been a while since I've played with this stuff, I'm wondering what the syntax is if you have a member function get_second() instead of a public member variable.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Exactly the same.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    l2u
    l2u is offline
    Registered User
    Join Date
    May 2006
    Posts
    630
    Why if I have tr1?
    Isnt this in standard?
    Is it in boost also?

  14. #14
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by l2u View Post
    Why if I have tr1?
    Isnt this in standard?
    Not yet. TR1 is a preview of what they want to put in the next standard.

    Is it in boost also?
    Yes. Boost.Bind was the base for the TR1 binders.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. sorting container
    By l2u in forum C++ Programming
    Replies: 6
    Last Post: 09-01-2007, 01:12 PM
  3. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM
  4. Map Container & Sorting :: STL
    By kuphryn in forum C++ Programming
    Replies: 2
    Last Post: 09-09-2002, 06:01 PM
  5. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21