Re: Container performance
In article <1176148520.271273.259940@e65g2000hsc.googlegroups.com>, Ion
Gazta?aga <igaztanaga@gmail.com> wrote:
Note that with sort(), the allocators of the auxiliary array of lists
are not used (except maybe to allocate the "end" node -> which can
throw -> which is makes this sort() a throwing algorithm -> another
reason to embed the end node in the container), because they are used
to temporarily store transferred nodes from the list to be sorted. We
could replace this array with another non-throwing thing (an intrusive
container, anyone?) and still sort the list without any fear. If I'm
right, allocators are not needed to sort, but they are there just to
make the implementation easier.
template <class T,class A>
class list _of
{
typedef typename std::list<T,A> list;
static void copy_a_run(list &in,list &out)
{
if(in.size() < 2)
{
in.swap(out);
return;
}
list t1,t2;
list::iterator i(in.begin()),j(in.begin()); ++j;
while !( *j < *i))
{
++i,++j;
}
out.splice(out.end(),in,in.begin(),j);
}
public:
static void sort(list in)
{
list t1,t2;
copy_a_run(in,t1);
while(!in.empty())
{
copy_a_run(in,t2);
t1.merge(t2);
}
in.swap(t1);
};
template <class T,class A>
inline void sort(std::list<T,A> &in) {list_of<T,A>::sort(in);}
in an implementation of std::list I would use inards avoiding changes
in the list sizes and other optimizations to this code using node *'s.
also eliminating the need for the temp lists in sort above.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]