By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,227 Members | 1,310 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,227 IT Pros & Developers. It's quick & easy.

STL and sorted list

P: n/a
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
Jul 22 '05 #1
Share this Question
Share on Google+
10 Replies


P: n/a
Der Andere wrote:
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.
Ideally, the list begins with the smallest element.


Jul 22 '05 #2

P: n/a
In article <c9*************@news.t-online.com>,
"Der Andere" <ma**************@gmx.net> wrote:
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.
Jul 22 '05 #3

P: n/a
> >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();


As the list would have to be sorted after every (non-sorting) insertion,
probably the multiset is the better alternative.
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 returnsthe 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.

Jul 22 '05 #4

P: n/a
> > I need to implement a sorted (ordered) list. STL has no sorted list
type as far as I know.


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.

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.
Ideally, the list begins with the smallest element.

Jul 22 '05 #5

P: n/a
In article <c9*************@news.t-online.com>,
"Der Andere" <ma**************@gmx.net> wrote:
>I need to implement a sorted (ordered) list. STL has no sorted list typeas >far as I know. Is there a (straight) way to implement a sorted list using
>STL?


Sure.

myList.sort();


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


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.
Jul 22 '05 #6

P: n/a
> >> >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();


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


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
Jul 22 '05 #7

P: n/a
> 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
Jul 22 '05 #8

P: n/a
"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
Jul 22 '05 #9

P: n/a
Der Andere wrote:
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 ...


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
kb******@gascad.at
Jul 22 '05 #10

P: n/a
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

Jul 22 '05 #11

This discussion thread is closed

Replies have been disabled for this discussion.