STL and sorted list

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

re: STL and sorted list

Der Andere wrote:
[color=blue]
> I need to implement a sorted (ordered) list. STL has no sorted list
> type as far as I know.[/color]

It has std::set.
[color=blue]
> 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?[/color]

Only operator<, AFAIK.
[color=blue]
> Ideally, the list begins with the smallest element.[/color]

re: STL and sorted list

In article <c9hnnu$jeq$07$1@news.t-online.com>,
"Der Andere" <matieuloeschmich@gmx.net> wrote:
[color=blue]
>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?[/color]

Sure.

myList.sort();

[color=blue]
>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?[/color]

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.

re: STL and sorted list

> >I need to implement a sorted (ordered) list. STL has no sorted list type
as[color=blue][color=green]
> >far as I know. Is there a (straight) way to implement a sorted list using
> >STL?[/color]
>
> Sure.
>
> myList.sort();[/color]

As the list would have to be sorted after every (non-sorting) insertion,
probably the multiset is the better alternative.
[color=blue][color=green]
> >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[/color][/color]
returns[color=blue][color=green]
> >the larger or smaller of two classes?[/color]
>
> 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.[/color]

re: STL and sorted list

> > I need to implement a sorted (ordered) list. STL has no sorted list[color=blue][color=green]
> > type as far as I know.[/color]
>
> It has std::set.[/color]

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.

[color=blue][color=green]
> > 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?[/color]
>
> Only operator<, AFAIK.
>[color=green]
> > Ideally, the list begins with the smallest element.[/color]
>[/color]

re: STL and sorted list

In article <c9ivhg$lb4$02$1@news.t-online.com>,
"Der Andere" <matieuloeschmich@gmx.net> wrote:
[color=blue][color=green][color=darkred]
>> >I need to implement a sorted (ordered) list. STL has no sorted list type[/color][/color]
>as[color=green][color=darkred]
>> >far as I know. Is there a (straight) way to implement a sorted list using
>> >STL?[/color]
>>
>> Sure.
>>
>> myList.sort();[/color]
>
>As the list would have to be sorted after every (non-sorting) insertion,
>probably the multiset is the better alternative.[/color]

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.

re: STL and sorted list

> >> >I need to implement a sorted (ordered) list. STL has no sorted list
type[color=blue][color=green]
> >as[color=darkred]
> >> >far as I know. Is there a (straight) way to implement a sorted list[/color][/color][/color]
using[color=blue][color=green][color=darkred]
> >> >STL?
> >>
> >> Sure.
> >>
> >> myList.sort();[/color]
> >
> >As the list would have to be sorted after every (non-sorting) insertion,
> >probably the multiset is the better alternative.[/color]
>
> 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.[/color]

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

re: STL and sorted list

> I need to implement a sorted (ordered) list. STL has no sorted list type
as[color=blue]
> 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.[/color]

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

re: STL and sorted list

"Der Andere" <matieuloeschmich@gmx.net> wrote in message news:<c9k75u$fh$04$1@news.t-online.com>...[color=blue][color=green]
> > I need to implement a sorted (ordered) list. STL has no sorted list type[/color]
> as[color=green]
> > 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.[/color]
>
> 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 ...
>[/color]
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

re: STL and sorted list

Der Andere wrote:[color=blue]
>[color=green]
> > I need to implement a sorted (ordered) list. STL has no sorted list type[/color]
> as[color=green]
> > 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.[/color]
>
> 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 ...[/color]

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

--
Karl Heinz Buchegger
kbuchegg@gascad.at

re: STL and sorted list

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

[...]

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