Prev: M,I.5'Pers ecution , harassm ent at wo rk
Next: [C] edit c-string passed as a parameter
From: Tim Frink on 2 Jan 2008 07:34
Hi,

I've an STL list of pointer pointing to some objects:

list< MyObject* > myList

The class "MyObject" has a public method

string getString() const;

which returns for each object its (unique) string ID.

Furthermore, I've a list of strings list< string > orderedList;

What I want to achieve now is to sort the pointers in "myList"
by their string IDs such that the new order corresponds to the
order of the strings in the list "orderedList". How could I do that?

One idea would be to create a new temporary list of MyObject* by
taking each string of orderedList, find the corresponding element
in myList and then add this pointer to the new list and finally
erase myList and use =operator to copy the elements of the new list
to myList. But I don't think that this is the most efficient and
elegant approach. Do you have a better solution?

Regards,
Tim
From: Francis Glassborow on 2 Jan 2008 07:50
Tim Frink wrote:
> Hi,
>
> I've an STL list of pointer pointing to some objects:
>
> list< MyObject* > myList
>
> The class "MyObject" has a public method
>
> string getString() const;
>
> which returns for each object its (unique) string ID.
>
> Furthermore, I've a list of strings list< string > orderedList;

I am not sure what this list is. How does it relate to the IDs? How was
it ordered?

>
> What I want to achieve now is to sort the pointers in "myList"
> by their string IDs such that the new order corresponds to the
> order of the strings in the list "orderedList". How could I do that?
>
> One idea would be to create a new temporary list of MyObject* by
> taking each string of orderedList, find the corresponding element
> in myList and then add this pointer to the new list and finally
> erase myList and use =operator to copy the elements of the new list
> to myList. But I don't think that this is the most efficient and
> elegant approach. Do you have a better solution?
>

In general the easiest way to order a sequence is by using the overload
of sort that takes a comparison function.
From: Tim Frink on 2 Jan 2008 08:01
>> Furthermore, I've a list of strings list< string > orderedList;
>
> I am not sure what this list is. How does it relate to the IDs? How was
> it ordered?

This is a list of the string IDs which was ordered by some other
method. The order is not lexical and can be arbitrary since it
depends on some (arbitrary) user input.

>> One idea would be to create a new temporary list of MyObject* by
>> taking each string of orderedList, find the corresponding element
>> in myList and then add this pointer to the new list and finally
>> erase myList and use =operator to copy the elements of the new list
>> to myList. But I don't think that this is the most efficient and
>> elegant approach. Do you have a better solution?
>>
>
> In general the easiest way to order a sequence is by using the overload
> of sort that takes a comparison function.

I think that a comparison function cannot be taken here since the
order of the strings in "orderedList" is not lexical/numerical.
From: Francis Glassborow on 2 Jan 2008 10:00
Tim Frink wrote:
>>> Furthermore, I've a list of strings list< string > orderedList;
>> I am not sure what this list is. How does it relate to the IDs? How was
>> it ordered?
>
> This is a list of the string IDs which was ordered by some other
> method. The order is not lexical and can be arbitrary since it
> depends on some (arbitrary) user input.

Really arbitrary? OK seems odd and the problem has all kinds of fail
points. For example what happens if an ID for an object is not in the
'ordered list' ?

>
>>> One idea would be to create a new temporary list of MyObject* by
>>> taking each string of orderedList, find the corresponding element
>>> in myList and then add this pointer to the new list and finally
>>> erase myList and use =operator to copy the elements of the new list
>>> to myList. But I don't think that this is the most efficient and
>>> elegant approach. Do you have a better solution?
>>>
>> In general the easiest way to order a sequence is by using the overload
>> of sort that takes a comparison function.
>
> I think that a comparison function cannot be taken here since the
> order of the strings in "orderedList" is not lexical/numerical.

OK. However I suspect that you are trying to patch up a solution when a
redesign is probably going to be more effective. Solutions will depend
on the number of objects we are dealing with. However here is an idea.

define a struct that consists of two members, an ID and a number.
create a vector of these and initialise them with instances formed from
the entries to ordered list and the ordinal for the position in the
'ordered list'. Sort the vector by the IDs. Now you have a look up table
for the location of each ID.

Create a vector of default objects of the correct size for the list of
objects. Now you can take each object look up its location and place it
in the vector. Finally you can create a new list from the vector (STL
sequences can be constructed from each other.)

However if you are using sequences of pointers you should almost
certainly be using some kind of smart pointer.



From: Daniel T. on 2 Jan 2008 11:06
Tim Frink <plfriko(a)yahoo.de> wrote:

> I've an STL list of pointer pointing to some objects:
>
> list< MyObject* > myList
>
> The class "MyObject" has a public method
>
> string getString() const;
>
> which returns for each object its (unique) string ID.
>
> Furthermore, I've a list of strings list< string > orderedList;
>
> What I want to achieve now is to sort the pointers in "myList"
> by their string IDs such that the new order corresponds to the
> order of the strings in the list "orderedList". How could I do that?

If, once sorted, the order isn't expected to change, then you can use a
std::set instead of a std::list. However, if the order in the list of
strings changes or the value returned by MyObject->getString() can
change, then a set isn't appropriate.

If you can use a std::set, then you really should use one. It can work
with the predicate I have below.

> One idea would be to create a new temporary list of MyObject* by
> taking each string of orderedList, find the corresponding element
> in myList and then add this pointer to the new list and finally
> erase myList and use =operator to copy the elements of the new list
> to myList. But I don't think that this is the most efficient and
> elegant approach.

That's a selection sort. O( n^2 ) but if the list is small, it may be
fine.

> Do you have a better solution?

Are you sure you need the whole list sorted? If you can get away with
sorting only a portion of the list, there are much faster algorithms
(like std::partition.)

I have a different solution... I think the best solution depends on the
size of the list. For my solution the actual sort is O(n log(n)), but
the compare is O(2n) and there is a bunch of house keeping stuff
(copying the list to a vector and back.)

Here are the two solutions (yours and mine) for comparison:

// all code below uses these:
typedef list< MyObj* > ObjList;
typedef list< string > StringList;

// Yours first (this is actually a little better than the idea you
// stated, because it sorts the list in-place rather than making a
// copy.) Performs an insertion sort which is O( n^2 )

struct getString_is : unary_function< MyObj, bool >
{
string value;
getString_is( const string& value ): value( value ) { }
bool operator()( const MyObj* obj ) const {
return obj->getString() == value;
}
};

struct order_list : unary_function< string, void >
{
ObjList* ol;
ObjList::iterator ol_it;
order_list( ObjList* ol ): ol( ol ) {
ol_it = ol->begin();
}
void operator()( const string& str ) {
ObjList::iterator it = find_if( ol_it, ol->end(),
getString_is( str ) );
if ( it != ol->end() ) {
iter_swap( it, ol_it );
++ol_it;
}
}
};

void yourSortIdea( ObjList& ol, const StringList& sl )
{
for_each( sl.begin(), sl.end(), order_list( &ol ) );
}

// My idea uses std::sort and a predicate. In order to use std::sort, I
// have to first put the list into a vector so despite the fact that the
// complexity of the algorithm is better, the overall speed might not be
// if the list is small

struct Pred : binary_function< MyObj, MyObj, bool >
{
vector< string > ordering;
Pred( const StringList& ordering ):
ordering( ordering.begin(), ordering.end() )
{ }
bool operator()( const MyObj* left, const MyObj* right ) const
{
bool result = false;
if ( left != right ) {
vector<string>::const_iterator lit =
find( ordering.begin(), ordering.end(), left->getString() );
vector<string>::const_iterator rit =
find( ordering.begin(), ordering.end(), right->getString() );
if ( lit < rit )
result = true;
}
return result;
}
};

void mySortIdea( ObjList& ol, const StringList& sl )
{
vector< MyObj* > tmp( ol.begin(), ol.end() );
sort( tmp.begin(), tmp.end(), Pred( sl ) );
ol.clear();
ol.insert( ol.end(), tmp.begin(), tmp.end() );
}
 |  Next  |  Last
Pages: 1 2
Prev: M,I.5'Pers ecution , harassm ent at wo rk
Next: [C] edit c-string passed as a parameter