Re: "Fixing" the O(1) splice / O(1) size std::list problem?

In article <d8ednfFYt6vBwE7YnZ2dnUVZ_silnZ2d@giganews.com>,
 pjp@dinkumware.com ("P.J. Plauger") wrote:


<g> That is ironic since it is the desire for this very function (with
the O(1) complexity) which has been the basis for a decade-long debate.

Ok, here's a reasonable use case:

I have a master database consisting of a list of Record:

struct Record
{
    std::string department;
    std::string data;
};

I want to create separate databases, one for each department, so that I
can send separate smaller lists to each individual department for
parallel processing. An "unmerge" if you will:

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.

I understand your desire to have O(N) logic in this splice function for
integrity checking purposes. However I am of the opinion such checking
belongs in a debug build (which by the way a client is free to ship).
Not everyone can afford debug checking in release builds.

-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 ]