template sort

[Grahamo]

Hi

I'm working with deployed code and am looking for ways to optimise it
and clean up memory leaks etc. I'm working with a template
ContainerOfPointers, which is exactly that. It has methods like insert,
clear, splice, adopt, at etc. It was written before the advent of STL,
hence it's presence in the code.

I'm looking at a piece of code that works on such templates,
specifically a sort template function which is defined below. I am
under the impression that stl algorithms and such like are going to be
faster than home grown ones (the compiler is smarter than me...not
difficult). so ideally I'd like to see if its possible to replace these
sort of routines with STL ones.


Could anybody offer any advice on what appoach I should take. My goal
is to replace home grown algorithms with stl ones (even if it's to do a
comparison and not to deploy so I can at least see the results). It
would be nice to replace the body of the sort template function below
with that to stl::sort but I don't have randomAccessIterators for my
ContainerOfPointers template. Should I embark on doing so or am I
pi*ssing into the proverbial wind.


template <class T>
void sort (ContainerOfPointers<T>& ref)
{
TTK_TEST_REF (ref); // does an assert
bool flag (true);
while (flag)
{
flag = false;
int end(ref.entries());
for (int i(1); i < end; i++)
{
if (*ref.at (i-1) > *ref.at (i))
{
DoSwap(ref.at (i-1) , ref.at (i));
flag = true;
}
}
}
}


swaps straight forward enough.

template <class T>
void DoSwap (T& ref1, T& ref2)
{
T tmp (ref1);
ref1 = ref2;
ref2 = tmp;
};


thanks for any insights.

have a nice day.

GrahamO

 

[Gianni Mariani]

Could anybody offer any advice on what appoach I should take. My goal
is to replace home grown algorithms with stl ones (even if it's to do a
comparison and not to deploy so I can at least see the results). It
would be nice to replace the body of the sort template function below
with that to stl::sort but I don't have randomAccessIterators for my
ContainerOfPointers template. Should I embark on doing so or am I
pi*ssing into the proverbial wind.


template <class T>
void sort (ContainerOfPointers<T>& ref)
{
TTK_TEST_REF (ref); // does an assert
bool flag (true);
while (flag)
{
flag = false;
int end(ref.entries());
for (int i(1); i < end; i++)
{
if (*ref.at (i-1) > *ref.at (i))
{
DoSwap(ref.at (i-1) , ref.at (i));
flag = true;
}
}
}
}

You can wrap your "ContainerOfPointers" with another class that does
provide iterators. Then you can use std::sort on the wrapper.

I suspect std::sort would be much much faster than the algorithm here.


Somthing like this:

template <class T>
class COPWrapperIterator;

template <class T>
class COPWrapper
{
ContainerOfPointers<T> & m_ref;

public:
COPWrapper( ContainerOfPointers<T>& ref )
: m_ref( ref )
{
}

COPWrapperIterator<T> begin();
COPWrapperIterator<T> end();

};

template <class T>
class COPWrapperIterator
{
COPWrapper<T> & m_copwrapper;
int m_index;
friend class COPWrapper<T>;
COPWrapperIterator( COPWrapper<T> & copwrapper, int index );
..... etc

};


Then your sort code would look somthing like:

template <class T>
void sort (ContainerOfPointers<T>& ref)
{
TTK_TEST_REF (ref); // does an assert

COPWrapper<T> wrapper( ref );

std::sort( wrapper.begin(), wrapper.end(), CompareLess() );

};

 

[Grahamo]

Thanks for that Gianni,

std::sort signatures are;

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

and

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

so I am presuming my COPWrapperIterator template class inherits from
the appopriate iterator type , in this class RandomAccessIterator, and
from there imlement the methods required by same iterator type. yes?

thanks for your help

G

 

[msalters]

(e-mail address removed) schreef:

std::sort signatures are;

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

and

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

so I am presuming my COPWrapperIterator template class inherits from
the appopriate iterator type , in this class RandomAccessIterator, and
from there imlement the methods required by same iterator type. yes?

Boost has boost::iterator which is a huge timesaving. However, it's
not needed. RandomAccessIterator in this case is just a descriptive
name.
It could have been called T, and is unrelated to a base class.
(www.boost.org)

E.g. an int* ia a proper RandomAccessIterator for an int[] array,
because all operations needed are provided.


HTH,
Michiel Salters

 

[Grahamo]

ah shi*te.... should have seen that!

thanks for your reply.

Graham