Re: "Fixing" the O(1) splice / O(1) size std::list problem?
In article <140220072211140069%cbarron413@adelphia.net>,
cbarron413@adelphia.net (Carl Barron) wrote:
std::map<std::string, std::list<Record> >
unmerge(std::list<Record>& c)
{
std::map<std::string, std::list<Record> > r;
for (std::list<Record>::iterator i = c.begin(), e = c.end(); i != e;)
{
std::string department = i->department;
std::list<Record>::iterator j = i;
std::list<Record>::size_type count = 1;
for (++j; j != e; ++j, ++count)
if (j->department != i->department)
break;
std::list<Record>& t = r[department];
t.splice(t.end(), c, i, j, count);
i = j;
}
return r;
}
* This is reasonable code.
* It makes use of splice-some-from-other
* splice-some-from-other is within a loop, so keeping it as efficient as
possible would be nice.
* The count of the number of nodes one wants to splice at a time is
trivially computed without affecting the performance of the entire
algorithm.
* This algorithm purposefully makes a single pass through the master
list in an effort to minimize cache misses.
Yes but what is the signifigant gain over
while(!c.empty())
{
std::string const &department = c.front().department();
std::list<Record> &t = r[department];
while(!c.empty() && c.front().department == department)
t.splice(t.end(),c,c.begin());
}
The # of compares is the same, the only difference is the # of
internal pointer changes and that is also O(N). so they are both O(N),
where N == c.size(). I suppose if you had 10 million entries in c and
10 distinct departments it might be signifigant but then is a big std::
list a good idea to hold the original data? Seems like a contrived
example.
I am of no opinion over adding a fourth splice overload, just
wondering what is gained by the addition.
I don't see a case where I know the iterators i,j and distance(i,j)
independent of traversing the list. If I have to traverse the list
little is gained, over splicing to a temp list while I traverse, or in
this case splicing each item to the proper list while traversing the
original list, such as above does,
Using your reasoning, the existing splice-some signature should not
exist:
void splice(iterator position, list& x, iterator first, iterator last);
It can always be accomplished with:
void splice(iterator position, list& x, iterator i);
If we get rid of the splice-some signature, we also get rid of the
motivation for an O(N) size. :-)
However I do not seriously think we can remove it, on backwards
compatibility concerns if nothing else.
-Howard
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]