STL and sorted list

D

Der Andere

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.

Cheers,
Matthias
 
R

Rolf Magnus

Der said:
I need to implement a sorted (ordered) list. STL has no sorted list
type as far as I know.

It has std::set.
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?

Only operator<, AFAIK.
 
D

Daniel T.

Der Andere said:
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?
Sure.

myList.sort();


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?

operator< is generally implemented for sort, but any binary functor that
can compare two objects and return true for the smaller (ie left most)
one will work.
 
D

Der Andere

I need to implement a sorted (ordered) list. STL has no sorted list type
as
Sure.

myList.sort();

As the list would have to be sorted after every (non-sorting) insertion,
probably the multiset is the better alternative.
 
D

Der Andere

I need to implement a sorted (ordered) list. STL has no sorted list
It has std::set.

You're right.
The problem that I had was that I also need to contain multiple occurences
of one element. But a different version of set (multiset) seems to be the
appropriate solution.
 
D

Daniel T.

Sure.

myList.sort();

As the list would have to be sorted after every (non-sorting) insertion,
probably the multiset is the better alternative.[/QUOTE]

True, however if it is a situation where the items are all added at
once, then not modified while the list is being iterated over, simply
calling list::sort() may be a more effecient alternative.
 
D

Der Andere

I need to implement a sorted (ordered) list. STL has no sorted list
type
True, however if it is a situation where the items are all added at
once, then not modified while the list is being iterated over, simply
calling list::sort() may be a more effecient alternative.

Oh I see. However, items are added and deleted throughout the execution of
the program, so list::sort() would have to called many times.

Regards,
Matthias
 
D

Der Andere

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 ...

Regards,
Matthias
 
D

Dave Moore

Der Andere said:
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::eek:stream& print(std::eek:stream &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
 
K

Karl Heinz Buchegger

Der said:
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 ...

Not if you provide the multiset with a predicate which tells it in which
way you want the ordering to be done.
 
?

=?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1o

Dave Moore ha escrito:
[...]
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:

[...]

In case you're curious, the kind of constructs you describe can be
obtained in a very convenient manner with Boost.MultiIndex, which will
ship in the next release of Boost:

http://www.boost-consulting.com/boost/libs/multi_index/

[yes, this is self-publicizing :) ]

Regards,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

STL Container? 4
Dictionary and List 1
STL container for sorted items 18
STL Vector Access 1
stl::list modified erase 13
C Containers Library vs STL 14
Diamond Inheritance and STL 7
STL list Usage 7

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top