Sorting a map<T*>

[barcaroller]

I have a map<T*> that stores pointers to objects. How can I tell map<T*> to
use the objects' operator<() and not the value of the pointers for sorting?

If that's not feasible, what alternatives do I have to sort a set of objects
that cannot and should not be copied (i.e. I can use only pointers to these
objects)?

Note: I am aware of the method of creating a new class that wraps the
pointers of the objects and then provides its own operator<(). However, I
am trying to avoid creating new classes.

 

[red floyd]

I have a map<T*> that stores pointers to objects. How can I tell map<T*> to
use the objects' operator<() and not the value of the pointers for sorting?

If that's not feasible, what alternatives do I have to sort a set of objects
that cannot and should not be copied (i.e. I can use only pointers to these
objects)?

Note: I am aware of the method of creating a new class that wraps the
pointers of the objects and then provides its own operator<(). However, I
am trying to avoid creating new classes.

Why? If it does the job?

 

[barcaroller]

There is no map<T*>. map takes (at least) two template parameters --
the key and the value.

I'm sorry; my mistake. I meant set<T*>.

 

[Thomas J. Gritzan]

I have a map<T*> that stores pointers to objects. How can I tell map<T*> to
use the objects' operator<() and not the value of the pointers for sorting?

std::map has 4 template parameters. The 3rd is a compare functor. Write a
functor that simply maps to the objects operator<().

In std::set, it's the second template parameter.

 

[Michael]

I have a set<T*> that stores pointers to objects. How can I tell set<T*> to
use the objects' operator<() and not the value of the pointers for sorting?

There's a way to create a set with two parameters: set<MyType,
key_comp>, where
key_comp is a key comparison function you define. For example,
set<int, less<int> >.

So then you'd just need to provide the appropriate comparison function
that uses
the objects' operator<(), suitably wrapped.

Michael

 

[Markus Schoder]

There's a way to create a set with two parameters: set<MyType,
key_comp>, where
key_comp is a key comparison function you define. For example, set<int,
less<int> >.

So then you'd just need to provide the appropriate comparison function
that uses
the objects' operator<(), suitably wrapped.

Actually you need a class with an appropriate operator(). A plain
function won't do here since you cannot pass it as a template parameter.

 

[Pete Becker]

Actually you need a class with an appropriate operator(). A plain
function won't do here since you cannot pass it as a template parameter.

Sure you can. Try it.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Markus Schoder]

Sure you can. Try it.

No you cannot. I guess you are confusing this with algorithms like
std::lower_bound where you can specify a predicate as a _function_
parameter. As a template parameter for std::set or std::map this does not
work. Think about it -- it needs to be a type.

 

[Greg Herlihy]

No you cannot. I guess you are confusing this with algorithms like
std::lower_bound where you can specify a predicate as a _function_
parameter. As a template parameter for std::set or std::map this does not
work. Think about it -- it needs to be a type.

But std::set's Compare type may be a function type - it does not need to be
a class type that has an overloaded operator() defined. So Pete's objection
is correct - and here is some code to demonstrate:

#include <set>

bool MyComp(int *a, int *b)
{
return *a < *b;
}

int main()
{
std::set<int*, bool (*)(int*, int*)> s(MyComp);

s.insert( new int(1) );
s.insert( new int(2) );
...
}

Greg

 

[Sylvester Hesp]

No you cannot. I guess you are confusing this with algorithms like
std::lower_bound where you can specify a predicate as a _function_
parameter. As a template parameter for std::set or std::map this does not
work. Think about it -- it needs to be a type.

And at what point in time did functions stop having types?

bool mycompfunc(int, int);
std::set<int, bool(*)(int, int)> myset(mycompfunc);

- Sylvester Hesp

 

[Markus Schoder]

And at what point in time did functions stop having types?

bool mycompfunc(int, int);
std::set<int, bool(*)(int, int)> myset(mycompfunc);

Ah, I did not realise that the set is actually initialised with the
compare object. For some reason I thought it does Compare()(x, y) with
the comparison type.

 

[Pete Becker]

No you cannot. I guess you are confusing this with algorithms like
std::lower_bound where you can specify a predicate as a _function_
parameter. As a template parameter for std::set or std::map this does not
work. Think about it -- it needs to be a type.

You're right. Spoke too quickly.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Pete Becker]

But std::set's Compare type may be a function type - it does not need to be
a class type that has an overloaded operator() defined. So Pete's objection
is correct - and here is some code to demonstrate:

#include <set>

bool MyComp(int *a, int *b)
{
return *a < *b;
}

int main()
{
std::set<int*, bool (*)(int*, int*)> s(MyComp);

s.insert( new int(1) );
s.insert( new int(2) );
...
}

You're right. Spoke too quickly.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[jiaxiong.xu]

barcaroller дµÀ£º

I have a map<T*> that stores pointers to objects. How can I tell map<T*> to
use the objects' operator<() and not the value of the pointers for sorting?

If that's not feasible, what alternatives do I have to sort a set of objects
that cannot and should not be copied (i.e. I can use only pointers to these
objects)?

Note: I am aware of the method of creating a new class that wraps the
pointers of the objects and then provides its own operator<(). However, I
am trying to avoid creating new classes.

template <typename _Key, typename _Tp, typename _Compare =
less<_Key>,
typename _Alloc = allocator<pair<const _Key, _Tp> > >class
map{
.....
};
you only need to assign _Compare to the functor which is used to
compare key as you like

 

[James Kanze]

No you cannot. I guess you are confusing this with algorithms like
std::lower_bound where you can specify a predicate as a _function_
parameter. As a template parameter for std::set or std::map this does not
work. Think about it -- it needs to be a type.

Now I've seen everything. Someone trying to correct Pete with
regards to the standard library.

Whether you're aware of it or not, pointer to a function *is* a
type, and there's no problem declaring an std::set to take a
pointer to a function, e.g.:

bool
cmp( T const* p1, T const* p2 )
{
return *p1 < *p2 ;
}
std::set< T*, bool (*)( T const*, T const* ) > mySet( cmp ) ;

Because the instances of a pointer to function are not
unipotent, it is necessary to pass an argument to the
constructor, to specify which one you want, but this is also
true for functional objects which aren't unipotent.

 

[Sylvester Hesp]

You're right. Spoke too quickly.

No he's not, and no you didn't

- Sylvester Hesp

 

[Markus Schoder]

You're right. Spoke too quickly.

You were right -- I was wrong. Sorry for the confusion. I overlooked the
fact that there is a parameter to the set constructor for the compare
object which of course allows passing a function.