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
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
I would suggest doing it somthing like this:..
Of course, it's not actuall code, but you get the idea...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. }
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.
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
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.
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)
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.
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; } };
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
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.
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
Why if I have tr1?
Isnt this in standard?
Is it in boost also?
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