multiset - Dev Shed

Dev Shed Forums Sponsor:

July 1st, 2005, 11:11 PM

UmneyDurak

Contributing User

Join Date: Jul 2004

Posts: 177

Time spent in forums: 2 Days 2 h 52 m 49 sec
Reputation Power: 8

multiset

Hi.
I'm hopping someone can help me with it. I heard that you can do sorting with multiset upon insert, but I can't seem to find any information on it. LIke which methods needs to be implemmented, how it's done etc. All I found so far is that, "yes you can do it.".

It's for C++.

Thanks.

July 4th, 2005, 07:35 AM

bergner

Contributing User

Join Date: Apr 2004

Posts: 144

Time spent in forums: 7 h 48 m 6 sec
Reputation Power: 8

You need to write your own comparator

The multiset class takes a number of template arguments. Only the first one is mandatory, the type of elements stored in the set. The second one is a class that is used to order the elements in the set. The ordering allows searches in the set to be done in O(log n) time. If you were not aware of it, the multiset is implemented as a red-black tree. Have a look at the STL less<T> class. It is the default comparator. From there you should be able to write your own version of it that orders elements to your liking. I'm not sure if this is the order you will traverse the tree as well with begin(), operator++ and end() though. I hope it helped a little. Remember that ordered and sorted are not necessarily the same thing.

July 4th, 2005, 06:41 PM

KitKat77

Contributing User

Join Date: Jun 2005

Location: planet<earth_like_t>

Posts: 365

Time spent in forums: 1 Week 3 Days 9 h 53 m 7 sec
Reputation Power: 146

Quote:

Originally Posted by UmneyDurak

I'm hopping someone can help me with it. I heard that you can do sorting with multiset upon insert, but I can't seem to find any information on it.

Here's Microsoft's documentation on the multiset class and the less template.

You don't need to do anything if you've defined an operator< function for your type/class. The function insert() uses less<T> which, in turn, uses T.operator<(T) internally. So when you call insert(), sorting is done for you.

Should you wish to know how one would perform template specialization on less<T>, say so.

July 4th, 2005, 09:38 PM

UmneyDurak

Contributing User

Join Date: Jul 2004

Posts: 177

Time spent in forums: 2 Days 2 h 52 m 49 sec
Reputation Power: 8

So basically if I have a class Foo and I do something like:
typdef multiset <Foo> FTable
FTable f;
If I do f.insert(some instance of Foo);
If I implemented operator < in Foo it will use that to sort it appropriately?

July 5th, 2005, 12:05 AM

animatronic

Contributing User

Join Date: Jan 2004

Posts: 287

Time spent in forums: 2 Weeks 6 m 56 sec
Reputation Power: 12

The < operator is very important in set's (and multiset's) as it is used for the insertion sort and in the find() method of the set.

here is an example using a multiset covering insertion, finding and erasing.

Code:

#include <iostream>
#include <set>
#include <string>

struct Foo
{
public:
	Foo( int key, const std::string & message ) : Key(key), Message(message)
	{
	}

	bool operator < ( const Foo & rhs ) const
	{
		return (Key < rhs.Key);
	}

	int Key;
	std::string Message;
};

int main(int argc, char* argv[])
{
	//declare
	std::multiset<Foo> FooSet;
	typedef std::multiset<Foo>::iterator IterType;

	//add some foo's
	FooSet.insert( Foo(0,"") );
	FooSet.insert( Foo(1,"Hello") );
	FooSet.insert( Foo(1,"World") );
	FooSet.insert( Foo(2,"") );
	FooSet.insert( Foo(2,"") );
	FooSet.insert( Foo(3,"Boo") );
	FooSet.insert( Foo(3,"Bar") );

	//find all the 1's and print
	std::pair<IterType,IterType> findBeginEnd = FooSet.equal_range( Foo(1,"") );
	IterType iter;
	for( iter = findBeginEnd.first; iter!=findBeginEnd.second; ++iter )
		std::cout << iter->Message << std::endl;

	//erase all the 2's
	findBeginEnd = FooSet.equal_range( Foo(2,"") );
	FooSet.erase( findBeginEnd.first, findBeginEnd.second );

	//print then erase 3 "Bar"
	findBeginEnd = FooSet.equal_range( Foo(3,"") );
	for( iter = findBeginEnd.first; iter!=findBeginEnd.second; )
	{
		if( iter->Message == "Bar" ) 
		{
			std::cout << iter->Message << std::endl;
			iter = FooSet.erase( iter );
		}
		else ++iter;
	}

	std::cin.get();

	return 0;
}

Hope than can help

July 5th, 2005, 02:10 AM

KitKat77

Contributing User

Join Date: Jun 2005

Location: planet<earth_like_t>

Posts: 365

Time spent in forums: 1 Week 3 Days 9 h 53 m 7 sec
Reputation Power: 146

Quote:

Originally Posted by UmneyDurak

That's exactly it.

July 19th, 2005, 08:18 PM

UmneyDurak

Contributing User

Join Date: Jul 2004

Posts: 177

Time spent in forums: 2 Days 2 h 52 m 49 sec
Reputation Power: 8

Hi.
I have another question about multiset. Can I provide and explicit function for it to use to compare when I define it?
Thanks.

July 19th, 2005, 08:48 PM

animatronic

Contributing User

Join Date: Jan 2004

Posts: 287

Time spent in forums: 2 Weeks 6 m 56 sec
Reputation Power: 12

Yeah just define a type that implements bool operator() ( Type const& lhs, Type const& rhs) const; returning true if the left object is less than the right and false for everything else.

Code:

struct Foo{};

struct FooComparer
{
	bool operator() ( Foo const & lhs, Foo const & rhs ) const
	{
		// ... do comparing
	}
};

std::multiset<Foo,FooComparer> fooSet;

July 21st, 2005, 01:52 AM

UmneyDurak

Contributing User

Join Date: Jul 2004

Posts: 177

Time spent in forums: 2 Days 2 h 52 m 49 sec
Reputation Power: 8

Wait why operator (), instead of < ? Only thing I could come up wit is that when it does compare if (obj1 < obj2) overloading parentecies, will override the less operator? I'm sure it's not right.
Tried googling, but I'm not sure what to even look for. All I got is some standard information about operator overloading in C++. In some cases people don't even bother writting their own stuff and just copy articles from other pages and pass as their own.

Thanks.

Last edited by UmneyDurak : July 21st, 2005 at 01:55 AM.

#10

July 21st, 2005, 07:49 AM

animatronic

Contributing User

Join Date: Jan 2004

Posts: 287

Time spent in forums: 2 Weeks 6 m 56 sec
Reputation Power: 12

The second default template parameter for set (and map) is std::less. std::less is defined like:

Code:

template<class T> less
{
	bool operator() ( T const & lhs, T const & rhs ) const
	{
		return lhs < rhs;
	}
};

so when you defined a set such as std::set<foo> its going to use std::less<foo> for doing its comparison. Its acturely std::less that calles up the overloaded < operator, on the class, all the set does is call up the () operator on its key comparer.

#11

July 21st, 2005, 10:12 PM

KitKat77

Contributing User

Join Date: Jun 2005

Location: planet<earth_like_t>

Posts: 365

Time spent in forums: 1 Week 3 Days 9 h 53 m 7 sec
Reputation Power: 146

Quote:

Originally Posted by UmneyDurak

Wait why operator (), instead of < ?

That's because the second parameter of a multiset<> is a function object. That's an object (class or struct) that defines a member function operator(). The less<> template I linked to earlier is a function object.

The purpose of the operator() function will be to return true or false wether it's first parameter should come before it's second parameter. How it decides that is entirely up to you.

#12

July 22nd, 2005, 11:25 PM

UmneyDurak

Contributing User

Join Date: Jul 2004

Posts: 177

Time spent in forums: 2 Days 2 h 52 m 49 sec
Reputation Power: 8

I think I understand it. Thanks.
Can you recommend a good book that talks about this in more details? All the ones I looked at so far just talk about simple stuff like how to loops, etc. I'm ok with pointers and stuff, it's just stuff like this I'm not that clear about.

Last edited by UmneyDurak : July 22nd, 2005 at 11:28 PM.

#13

July 24th, 2005, 06:15 PM

KitKat77

Contributing User

Join Date: Jun 2005

Location: planet<earth_like_t>

Posts: 365

Time spent in forums: 1 Week 3 Days 9 h 53 m 7 sec
Reputation Power: 146

Quote:

Originally Posted by UmneyDurak

At this time I'd say you're looking into reference work. The C++ Programming Language by Stroustrup is the language's reference so you'll find in it a section on C++'s function objects and why they are good for you. Also, I'd say check out ACCU's website for book recommendation for all levels.