"Der Andere" <ma**************@gmx.net> wrote in message news:<c9************@news.t-online.com>...
I need to implement a sorted (ordered) list. STL has no sorted list type
as far as I know. Is there a (straight) way to implement a sorted list using
STL?
BTW: The type of items in the list will be a class. Is it necessary to
implement the > or < operators or to write a compare-function that returns
the larger or smaller of two classes? Ideally, the list begins with the
smallest element.
Sorry, I was wrong there: The items in the list will be *pointers* to
instances of a class. If I use multiset::insert() then the items will be
ordered according to their (address) value, not according to the value of
the objects they point to. This is exactly what I do _not_ want ...
In that case you will have to use std::multiset's big brother,
std::multimap, where you duplicate the value from you structure that
you want to sort by as the key field.
For example:
#include <string>
#include <map>
#include <list>
#include <iostream>
#include <ostream>
using std::string;
using std::cout;
using std::endl;
struct mydata {
int m_ID;
string m_name;
mydata(const string& name, int ID) : m_ID(ID), m_name(name) {}
std::ostream& print(std::ostream &s) {
return s << m_ID << '\t' << m_name << '\n';
}
};
typedef std::multimap< int, mydata*> map_by_ID;
typedef std::multimap<string, mydata*> map_by_name;
typedef std::list<mydata> datastore;
int main () {
datastore data;
data.push_back(mydata("Alice", 4));
data.push_back(mydata("Alice", 671)); // just coz its a multimap
data.push_back(mydata("Bob", 3));
data.push_back(mydata("Chuck", 2));
data.push_back(mydata("Zelda", 2)); // just coz its a multimap
data.push_back(mydata("Dave", 1));
map_by_name namelist;
map_by_ID IDlist;
datastore::iterator di=data.begin();
for ( ; di!=data.end(); ++di) {
IDlist.insert( std::make_pair( di->m_ID, &(*di)));
namelist.insert(std::make_pair(di->m_name, &(*di)));
}
cout << "Data sorted by name:" << endl;
map_by_name::const_iterator CIN=namelist.begin();
for ( ; CIN!=namelist.end(); ++CIN)
CIN->second->print(cout);
cout << endl;
cout << "Data sorted by ID:" << endl;
map_by_ID::const_iterator CIID=IDlist.begin();
for ( ; CIID!=IDlist.end(); ++CIID)
CIID->second->print(cout);
cout << endl;
}
The above example could be cleaned up a bit but I hope you get the
gist. This is often a convenient way to implement a simplistic
database ... store the objects unsorted in some container, and then
create multiple sorted lists of pointers to allow fast searching
according to different criteria. Note that if items will be added to
the database, then you should *not* use std::vector or std::deque as
the unsorted container, because as they grow/shrink, then
pointers/iterators will eventually become invalidated. This is
guaranteed not to happen with std::list.
HTH, Dave Moore
