On Feb 11, 9:03 pm, sjhoweATdialDOTpipexDOT...@giganews.com ("Stephen
Howe") wrote:
> > I admit this situation is not ideal by any means, really it should
> > have been fixed in the original standard one way or the other.
>
> How can it be fixed?
> It is impossible that some variations of splice() and size() to be O(1) at
> the same time, one after the other.
>
> > However seeing as there is zero chance of fixing the problem now...
>
> And how could it have been "fixed" some time ago?

The standard could mandate one of O(1) size or O(1) slice. I
personally believe either would be better than the current situation,
where I (among others I'm sure) have written my own list class so I
can get O(1) slice everywhere.

> Okay. You could mandate that all implementations cache the size and adopt a
> lazy policy - if invalid - dont recompute the size until it is actually
> needed either internally or externally. That would mean if noone ever called
> splice(), size() is always O(1), and if there were 100's of splice() calls
> they also will be O(1), but if you alternate calls to size() and splice(),
> the size() will be O(N).
>
> I dont see how you can "fix" this so that both splice() is O(1) in all
> circumstances and size() is O(1) in all circumstances, desirable though it
> may be. The standard knows this. It is insoluble.

Yes, it is :) Therefore all we can do (I believe) is to try to limit
the freedom of the standard to express what happens in relality, ie
this tradeoff, rather than implying things like vector and set also
don't have to have O(1) size (unless of course some people want that.
All implementations of vector and set I have access to have O(1)
size).

Chris

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

On Feb 11, 11:49 pm, howard.hinn...@gmail.com (Howard Hinnant) wrote:
> In article <CNmdnX75cJxtilPYRVny...@pipex.net>,
>  sjhoweATdialDOTpipexDOT...@giganews.com ("Stephen Howe") wrote:
>
> > > If I write a function taking a referece to a list, I cannot tell the
> > > complexity of size(). It depends on whether someone else just did a splice
> > > to or from that list, without an intervening call to size(). Sometimes
> > O(1),
> > > sometimes not?
>
> > Yes. And I see no way round that. The current status quo is the best that
> > there is. I see no point in altering it in favour of either camp. A quality
> > implementation may miminise the effects and try and ensure both size() and
> > splice() are O(1) most of the time, but if a programmer writes alternative
> > calls to each, then size() is likely to be O(N).
>
> Imho the current status quo is the worst possible outcome.
>
> The best would be one of:
>
> 1.  Require O(1) size().
> 2.  Remove list::size().

Personally I'd much prefer one of these two options, however my not-
that-well informed opinion was that each side of the size/splice list
mess had at least one "over my dead body" on the committee, so the
chances of getting a change would be very hard :(

> Imho, size() is no different than subscripting in this regard.  And I
> believe predominant use cases of list::size() in existing non-demo code
> support my view that an O(n) size() approaches the danger of an O(n)
> subscripting operator.
>
> I ask everyone to scan existing (non-demo) code for uses of list::size()
> today...

I actually did this a few months ago, when I first found out about
this problem. I can tell you the results from code I use.

1) A list was being used as a FIFO, and size() was being used to check
if the  list ever got "too large", at which point an "emergency
action" was taken. This was when I first noticed that size() is O(n)
in g++, as it turned up in a profile. The FIFO was changed to a deque.

2) In another place, a list was being constructed using splice whole
list and insertions throughout the list. After the list was
constructed, it's size() was taken to know how much memory would be
needed to then allocate it statically. As this size() only occured
once, I left it.

3) In one place a splice-bits-from-one-list-to-another was being used.
It would have been possible to keep track of how much was being moved
fairly easily. However in that case I didn't need size(), so I decided
to just implement a new simple doubly-linked list class.

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

> The standard could mandate one of O(1) size or O(1) slice.

But if it did, it would mean implementors would have no latitude of
implementation and that would imply O(N) slice() or O(N) size()
respectively. The current wording in the standard means that the caching
implementation (which I think you mentioned in your first message and I also
mentioned in one of my messages) can be implemented. And that gives splice()
is always O(1) and that size() is always O(1) if you never call splice() and
O(N) only for some of the splice subcases. And any necessary recompute of
size means it is O(1) then onwards until (if at all) splice() is called.
That is pretty good.

Perhaps what you really want is for implementors to be steered towards a
caching implementation of size for list by the standard?

> Yes, it is :) Therefore all we can do (I believe) is to try to limit
> the freedom of the standard to express what happens in relality, ie
> this tradeoff, rather than implying things like vector and set also
> don't have to have O(1) size (unless of course some people want that.
> All implementations of vector and set I have access to have O(1)
> size).

Then perhaps the complexity requirements of vector and set's size() should
be guaranteed to be O(1).
After all, they can be.

Stephen Howe


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

"Stephen Howe" wrote:
> > The standard could mandate one of O(1) size or O(1) slice.
>
> But if it did, it would mean implementors would have no latitude of
> implementation and that would imply O(N) slice() or O(N) size()
> respectively.

Yes, the point is that it would be predictable. Not knowing whether
std::list<> has O(N) slice or O(N) size() means that you must design
on the pessimistic assumption that it is whichever of the two that is
least convenient for your application. If the least convenient one is
sufficiently inconvenient, you have to use your own container class,
rather than the standard one.

Defining two different list templates might be better.

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

Howard Hinnant wrote:
[snip]
>
> Imho the current status quo is the worst possible outcome.
>
> The best would be one of:
>
> 1.  Require O(1) size().
> 2.  Remove list::size().
>
> An O(n) size() is nothing but a trap waiting to catch the next
> programmer, expert or not.  Not having it at all would be far higher
> quality than having it, and having it be O(n).  If list::size() didn't
> exist, and you needed that information, std::distance(l.begin(),
> l.end()) is neither difficult, nor error prone.

In my experience implementing containers (for Boost.Interprocess) I
started modifying the SGI STL implementation (which has O(N) size and
O(1) splice), I think that option 1 is the correct, because:

1. Every other STL container (deque, vector, map/set...) in every
implementation I know has constant-time size(). Users expect O(1)
size.
2. The standard avoids defining inefficient functions, like operator[]
for lists, which would be also O(N)
3. The new splice function you propose (the one that takes the
distance) can make many O(N) splice operations O(1).
4. I think that usually size() is called many more times than
splice().

Due to user requests, I reimplemented the list using O(1) size and
O(N) splice but adding the new splice function. I've experimented the
advantage of this new splice when reimplementing "merge" for the list
container, which is typically based on splice(). "merge" can use the
new splice function to achieve the same complexity as the old "merge"
based on non constant-time lists. In many other algorithms I had, it
was possible to know the distance between the nodes, so I had no
performance loss.

Just my 2 cents,

Ion

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

Howard Hinnant wrote:
> One way I like to think about this view is to draw an analogy with the
> string constructors.  Consider:
>
> const char* message = ...;
> // for whatever reason you acquire the strlen(message):
> unsigned len = ...;
> // Now you want to construct a std::string:
> std::string s(message);  // Wasteful!
>                          // string must recompute strlen(message)
>
> // This is better:
> std::string s(message, len);
>
> The client had this information for whatever reasons already.  It makes
> little sense to throw that information away just to have the string
> constructor recompute it.  Similarly for splice.

This is exactly kind of thinking I'd like to see applied consistently in
the C++ standard library. Member functions (especially constructors)
have special role in providing efficient interface.


B.


--
Remove -trap- when replying. Usun -trap- gdy odpisujesz.

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

"Ion Gazta   aga" <igaztanaga@gmail.com> wrote in message
news:1171398208.102218.231120@j27g2000cwj.googlegroups.com...

> Howard Hinnant wrote:
> [snip]
>>
>> Imho the current status quo is the worst possible outcome.
>>
>> The best would be one of:
>>
>> 1.  Require O(1) size().
>> 2.  Remove list::size().
>>
>> An O(n) size() is nothing but a trap waiting to catch the next
>> programmer, expert or not.  Not having it at all would be far higher
>> quality than having it, and having it be O(n).  If list::size() didn't
>> exist, and you needed that information, std::distance(l.begin(),
>> l.end()) is neither difficult, nor error prone.
>
> In my experience implementing containers (for Boost.Interprocess) I
> started modifying the SGI STL implementation (which has O(N) size and
> O(1) splice), I think that option 1 is the correct, because:
>
> 1. Every other STL container (deque, vector, map/set...) in every
> implementation I know has constant-time size(). Users expect O(1)
> size.
> 2. The standard avoids defining inefficient functions, like operator[]
> for lists, which would be also O(N)
> 3. The new splice function you propose (the one that takes the
> distance) can make many O(N) splice operations O(1).
> 4. I think that usually size() is called many more times than
> splice().
>
> Due to user requests, I reimplemented the list using O(1) size and
> O(N) splice but adding the new splice function. I've experimented the
> advantage of this new splice when reimplementing "merge" for the list
> container, which is typically based on splice(). "merge" can use the
> new splice function to achieve the same complexity as the old "merge"
> based on non constant-time lists. In many other algorithms I had, it
> was possible to know the distance between the nodes, so I had no
> performance loss.

But merge splices *entire* lists, so it can know both how many
elements it moves and where the head node lies. As I've pointed
out before, this is one of several overloads of splice that can
(and should) be performed in constant time. It's only when you
splice just part of a list into another that you need to know
the length of what you're moving -- and you *should* know that
it's a safe splice in the bargain. Both operations can be done
at once, in O(N) time.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


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

In article <xu-dnXYddKAjzU_YnZ2dnUVZ_qarnZ2d@giganews.com>,
 "P.J. Plauger" <pjp@dinkumware.com> wrote:

> "Ion Gazta=F1aga" <igaztanaga@gmail.com> wrote in message=20
> news:1171398208.102218.231120@j27g2000cwj.googlegroups.com...
>=20
> > Due to user requests, I reimplemented the list using O(1) size and
> > O(N) splice but adding the new splice function. I've experimented the
> > advantage of this new splice when reimplementing "merge" for the list
> > container, which is typically based on splice(). "merge" can use the
> > new splice function to achieve the same complexity as the old "merge"
> > based on non constant-time lists. In many other algorithms I had, it
> > was possible to know the distance between the nodes, so I had no
> > performance loss.
>=20
> But merge splices *entire* lists, so it can know both how many
> elements it moves and where the head node lies. As I've pointed
> out before, this is one of several overloads of splice that can
> (and should) be performed in constant time. It's only when you
> splice just part of a list into another that you need to know
> the length of what you're moving -- and you *should* know that
> it's a safe splice in the bargain. Both operations can be done
> at once, in O(N) time.

I can well imagine list::merge taking advantage of=20
splice-some-from-other.  It might look like (untested code follows):

template <class T, class Allocator>
template <class Compare>
void
list<T, Allocator>::merge(list& x, Compare comp)
{
    if (this =3D=3D &x)
        return;
    if (alloc() !=3D x.alloc())
        throw runtime_error("list::merge called with unequal=20
allocators");
    iterator first1 =3D begin();
    iterator last1 =3D end();
    iterator first2 =3D x.begin();
    iterator last2 =3D x.end();
    for (; first1 !=3D last1 && first2 !=3D last2; ++first1)
    {
        if (comp(*first2, *first1))
        {
            iterator j =3D first2;
            size_t count =3D 1;
            for (++j; j !=3D last2; ++j, ++count)
                if (!comp(*j, *first1))
                    break;
            splice(first1, x, first2, j, count);  // here!
            first2 =3D j;
        }
    }
    if (first2 !=3D last2)
        splice(first1, x);
}

This might be more efficient than the alternative of splicing one node=20
at a time:

template <class T, class Allocator>
template <class Compare>
void
list<T, Allocator>::merge(list& x, Compare comp)
{
    if (this =3D=3D &x)
        return;
    if (alloc() !=3D x.alloc())
        throw runtime_error("list::merge called with unequal=20
allocators");
    iterator first1 =3D begin();
    iterator last1 =3D end();
    iterator first2 =3D x.begin();
    iterator last2 =3D x.end();
    for (; first1 !=3D last1 && first2 !=3D last2; ++first1)
        if (comp(*first2, *first1))
            splice(first1, x, first2++);
    if (first2 !=3D last2)
        splice(first1, x);
}

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

"Howard Hinnant" <howard.hinnant@gmail.com> wrote in message=20
news:howard.hinnant-6EA91E.11483014022007@news-server.twcny.rr.com...

In article <xu-dnXYddKAjzU_YnZ2dnUVZ_qarnZ2d@giganews.com>,
 "P.J. Plauger" <pjp@dinkumware.com> wrote:

> "Ion Gazta=F1aga" <igaztanaga@gmail.com> wrote in message
> news:1171398208.102218.231120@j27g2000cwj.googlegroups.com...
>
> > Due to user requests, I reimplemented the list using O(1) size and
> > O(N) splice but adding the new splice function. I've experimented the
> > advantage of this new splice when reimplementing "merge" for the list
> > container, which is typically based on splice(). "merge" can use the
> > new splice function to achieve the same complexity as the old "merge"
> > based on non constant-time lists. In many other algorithms I had, it
> > was possible to know the distance between the nodes, so I had no
> > performance loss.
>
> But merge splices *entire* lists, so it can know both how many
> elements it moves and where the head node lies. As I've pointed
> out before, this is one of several overloads of splice that can
> (and should) be performed in constant time. It's only when you
> splice just part of a list into another that you need to know
> the length of what you're moving -- and you *should* know that
> it's a safe splice in the bargain. Both operations can be done
> at once, in O(N) time.

I can well imagine list::merge taking advantage of
splice-some-from-other.  It might look like (untested code follows):

....

[pjp] At a quick glance, I'd say that your code does just what
our implementation does. The difference is that the "partial
splice with count" function is internal to list, and only gets
called after the iterators have been laundered to avoid granny
knots. Exposing such a function to the outside world, and requiring
that it operate in constant time, is a different kettle of fish,
however. It *forbids* the container from taking the time to ensure
that operations are safe.

I still haven't seen a compelling use case for O(1) "partial
splice", with or without a promised element count.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


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

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

> I still haven't seen a compelling use case for O(1) "partial
> splice", with or without a promised element count.

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

In article
<howard.hinnant-80A36F.15120914022007@johnf2.biosci.ohio-state.edu>,
Howard Hinnant <howard.hinnant@gmail.com> wrote:

> In article <d8ednfFYt6vBwE7YnZ2dnUVZ_silnZ2d@giganews.com>,
>  pjp@dinkumware.com ("P.J. Plauger") wrote:
>
> > I still haven't seen a compelling use case for O(1) "partial
> > splice", with or without a promised element count.
>
> <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.
>
   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,

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

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                      ]

Brief bit of background:

The C++ standard says that size() on containers "should" be constant
time. The only reason for the "should" appears to be
list::splice(iterator, list, iterator, iterator), which moves a
sublist from one list into another list. To make list.size() constant
time, this function must count the number of elements which are being
spliced. This has created two groups of list implementations. One has
O(1) size and one has O(1) splice. It would be nice to choose exactly
one of these as 'standard', but each group has a number of "over my
dead body" believers.

However, I believe the "fix" in the standard provides too much
freedom. For example, people wonder if std::set provides O(1) size,
but all implementations I've seen do provide O(1) size for std::set.

My suggested fix, for C++0x, is as follows:

1) Say that size for containers is O(1), with the exception that
specific member functions can say that the first invocation of size()
after they are called is not O(1).

2) label list::splice(iterator, list, iterator, iterator) with this
exception, and no other function in the standard.

How efficently can this be implemented?

I have adapted g++'s std::list (which doesn't provide O(1) size) to
this method. Apart from the obvious fact that splice makes size()
O(n), I have found the only measurable difference is that the size of
a std::list increases by a size_t (obviously, to store the size of the
list).

What is the outcome?

People who previously always had an O(1) size() for list are
uneffected.
People who don't use list::splice(iterator, list, iterator, iterator)
can count on always have O(1) size() for all containers.
There is still freedom of implementation between size() and a single
splice function in list.

I would personally like to make this even stronger, by enforcing
list::splice(iterator, list, iterator, iterator) was O(1), and size()
is O(1) except after that function is called.

Comments? Suggestions?

Chris

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

In article <1171021092.511507.179430@p10g2000cwp.googlegroups.com>,
 "Chris Jefferson" <4zumanga@gmail.com> wrote:

> Brief bit of background:
>
> The C++ standard says that size() on containers "should" be constant
> time. The only reason for the "should" appears to be
> list::splice(iterator, list, iterator, iterator), which moves a
> sublist from one list into another list. To make list.size() constant
> time, this function must count the number of elements which are being
> spliced. This has created two groups of list implementations. One has
> O(1) size and one has O(1) splice. It would be nice to choose exactly
> one of these as 'standard', but each group has a number of "over my
> dead body" believers.
>
> However, I believe the "fix" in the standard provides too much
> freedom. For example, people wonder if std::set provides O(1) size,
> but all implementations I've seen do provide O(1) size for std::set.
>
> My suggested fix, for C++0x, is as follows:
>
> 1) Say that size for containers is O(1), with the exception that
> specific member functions can say that the first invocation of size()
> after they are called is not O(1).
>
> 2) label list::splice(iterator, list, iterator, iterator) with this
> exception, and no other function in the standard.
>
> How efficently can this be implemented?
>
> I have adapted g++'s std::list (which doesn't provide O(1) size) to
> this method. Apart from the obvious fact that splice makes size()
> O(n), I have found the only measurable difference is that the size of
> a std::list increases by a size_t (obviously, to store the size of the
> list).
>
> What is the outcome?
>
> People who previously always had an O(1) size() for list are
> uneffected.
> People who don't use list::splice(iterator, list, iterator, iterator)
> can count on always have O(1) size() for all containers.
> There is still freedom of implementation between size() and a single
> splice function in list.
>
> I would personally like to make this even stronger, by enforcing
> list::splice(iterator, list, iterator, iterator) was O(1), and size()
> is O(1) except after that function is called.
>
> Comments? Suggestions?

I think this is a fair suggestion.  And I also share your personal
preference.  In addition to your suggestion I would like to see:

---
void splice(iterator position, list& x,
            iterator first, iterator last,
            size_type n);

Effects: Inserts elements in the range [first, last) before position and
removes the elements from x.

Requires: [first, last) is a valid range in x. The result is undefined
if position is an iterator in the range [first, last). Invalidates only
the iterators and references to the spliced elements. n ==
distance(first, last).

Throws: Nothing.

Complexity: Constant time.
---

The rationale for this function is that most applications which need to
"splice some from other" either known a-priori distance(first, last), or
can compute it prior to the call without affecting the big-O complexity
of their overall algorithm (a list merge-sort is exactly such an
application).

Debugging builds could easily check the precondition distance(first,
last) == n.

This gives clients a guaranteed "splice-some-from-other" without the
need to risk invalidating a subsequent O(1) size().

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

On 9 Feb., 19:21, howard.hinn...@gmail.com (Howard Hinnant) wrote:
> In article <1171021092.511507.179...@p10g2000cwp.googlegroups.com>,
>  "Chris Jefferson" <4zuma...@gmail.com> wrote:
> I think this is a fair suggestion.  And I also share your personal
> preference.

Me too, but read on.

> In addition to your suggestion I would like to see:
>
> ---
> void splice(iterator position, list& x,
>             iterator first, iterator last,
>             size_type n);
>
> Effects: Inserts elements in the range [first, last) before position and
> removes the elements from x.
>
> Requires: [first, last) is a valid range in x. The result is undefined
> if position is an iterator in the range [first, last). Invalidates only
> the iterators and references to the spliced elements. n ==
> distance(first, last).
>
> Throws: Nothing.
>
> Complexity: Constant time.
> ---
>
> The rationale for this function is that most applications which need to
> "splice some from other" either known a-priori distance(first, last), or
> can compute it prior to the call without affecting the big-O complexity
> of their overall algorithm (a list merge-sort is exactly such an
> application).
>
> Debugging builds could easily check the precondition distance(first,
> last) == n.
>
> This gives clients a guaranteed "splice-some-from-other" without the
> need to risk invalidating a subsequent O(1) size().

There is only one tiny point, that I don't like in that proposed
overload:
The fact that n seems redundant from the point of the user comparing
the existing range [first, last). I expect a steady stream of
questions in
this and other newsgroups "Why did they do this? Isn't it an
unnecessary
duplication of information?". From this point of view, these questions
are
reasonable, I think and AFAIK the first example of an "algorithm" in
the
standard, that has this property.
Just a stupid question on a gut level: Wouldn't the reduced interface

void splice(iterator position, list& x,
            iterator first, size_type n);

solve this and the previous mentioned problem?

The problem concerning distinguishing input iterators and integral
types
are already a known problem solved by implementors (23.1.1 p. 9) and
could be strengthened by changing the name to

void splice_n(iterator position, list& x,
            iterator first, size_type n);

where we have a reminding similarity to fill_n. The wording would be
similar
to yours, just replacing last by first + n (with either a reference to
25 p. 11
concerning the meaning of this or an explicit note that first + n is
not
explicitly evaluated).

What do you think?

Greetings from Bremen,

Daniel Kr   gler



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

In article <1171053234.539872.262060@k78g2000cwa.googlegroups.com>,
 "Daniel Kr=FCgler" <daniel.kruegler@googlemail.com> wrote:

> > ---
> > void splice(iterator position, list& x,
> >             iterator first, iterator last,
> >             size_type n);
> >
> > Effects: Inserts elements in the range [first, last) before position =
and
> > removes the elements from x.
> >
> > Requires: [first, last) is a valid range in x. The result is undefine=
d
> > if position is an iterator in the range [first, last). Invalidates on=
ly
> > the iterators and references to the spliced elements. n =3D=3D
> > distance(first, last).
> >
> > Throws: Nothing.
> >
> > Complexity: Constant time.
> > ---
> >
> > The rationale for this function is that most applications which need =
to
> > "splice some from other" either known a-priori distance(first, last),=
 or
> > can compute it prior to the call without affecting the big-O complexi=
ty
> > of their overall algorithm (a list merge-sort is exactly such an
> > application).
> >
> > Debugging builds could easily check the precondition distance(first,
> > last) =3D=3D n.
> >
> > This gives clients a guaranteed "splice-some-from-other" without the
> > need to risk invalidating a subsequent O(1) size().
>=20
> There is only one tiny point, that I don't like in that proposed
> overload:
> The fact that n seems redundant from the point of the user comparing
> the existing range [first, last). I expect a steady stream of
> questions in
> this and other newsgroups "Why did they do this? Isn't it an
> unnecessary
> duplication of information?". From this point of view, these questions
> are
> reasonable, I think and AFAIK the first example of an "algorithm" in
> the
> standard, that has this property.

One way I like to think about this view is to draw an analogy with the=20
string constructors.  Consider:

const char* message =3D ...;
// for whatever reason you acquire the strlen(message):
unsigned len =3D ...;
// Now you want to construct a std::string:
std::string s(message);  // Wasteful!
                         // string must recompute strlen(message)

// This is better:
std::string s(message, len);

The client had this information for whatever reasons already.  It makes=20
little sense to throw that information away just to have the string=20
constructor recompute it.  Similarly for splice.

> Just a stupid question on a gut level: Wouldn't the reduced interface
>=20
> void splice(iterator position, list& x,
>             iterator first, size_type n);
>=20
> solve this and the previous mentioned problem?

I believe this signature will force an O(n) splice (exactly what we're=20
trying to avoid).  The implementation will either have to splice nodes=20
one at a time until it has spliced n of them.  Or it will have to=20
advance an iterator from first n times, and then do one splice.  Either=20
way, you're O(n).

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

> I would personally like to make this even stronger, by enforcing
> list::splice(iterator, list, iterator, iterator) was O(1), and size()
> is O(1) except after that function is called.
>
> Comments? Suggestions?

Well this amounts to caching the size and "invalidating" it only if the
wrong form of splice is called, so it the cached size needs recalculating if
size() is called. Certainly the complexity wording could be tightened up, if
the above method is regarded as the done way of implementing list. If gives
programmers additional guarantees.

Stephen Howe


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

On 9 Feb., 23:44, howard.hinn...@gmail.com (Howard Hinnant) wrote:
> One way I like to think about this view is to draw an analogy with the
> string constructors.  Consider:
>
> const char* message = ...;
> // for whatever reason you acquire the strlen(message):
> unsigned len = ...;
> // Now you want to construct a std::string:
> std::string s(message);  // Wasteful!
>                          // string must recompute strlen(message)
>
> // This is better:
> std::string s(message, len);
>
> The client had this information for whatever reasons already.  It makes
> little sense to throw that information away just to have the string
> constructor recompute it.  Similarly for splice.

OK, I see your point. Interestingly, while I took a look at the above
mentioned
constructor of basic_string, that is

basic_string(const charT* s, size_type n ,
const Allocator& a = Allocator());

I found that there are no requirements on s despite the fact that it
must not be
0. The requires section mentions:

"s shall not be a null pointer and n < npos"

1) Shouldn't there be a requirement, that the provided array of charT
must at least
have a remaining length of n beginning from s?
2) Wouldn't it be acceptable to allow s == 0, iff n == 0?

But I'm leaving the original theme...

> > Just a stupid question on a gut level: Wouldn't the reduced interface
>
> > void splice(iterator position, list& x,
> >             iterator first, size_type n);
>
> > solve this and the previous mentioned problem?
>
> I believe this signature will force an O(n) splice (exactly what we're
> trying to avoid).  The implementation will either have to splice nodes
> one at a time until it has spliced n of them.  Or it will have to
> advance an iterator from first n times, and then do one splice.  Either
> way, you're O(n).

You are absolutely right. The idea came to me by just looking at the
interface, thereby forgetting the view on the actual data structure of
a linked
list ;-)
But one argument remains for me: Comparing to the above mentioned
string-c'tor where I'm allowed to provide any n < strlen(s), this
would not
be OK here. Honestly, I have no idea to resolve this issue other than
you did. Actually a challenging theoretical problem...

Greetings from Bremen,

Daniel



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

Stephen Howe wrote:
>> I would personally like to make this even stronger, by enforcing
>> list::splice(iterator, list, iterator, iterator) was O(1), and
>> size() is O(1) except after that function is called.
>>
>> Comments? Suggestions?
>
> Well this amounts to caching the size and "invalidating" it only if
> the wrong form of splice is called, so it the cached size needs
> recalculating if size() is called. Certainly the complexity wording
> could be tightened up, if the above method is regarded as the done
> way of implementing list. If gives programmers additional
> guarantees.
>

Only if you write all the processing for the list. Otherwise you still don't
know the complexity of size().

If I write a function taking a referece to a list, I cannot tell the
complexity of size(). It depends on whether someone else just did a splice
to or from that list, without an intervening call to size(). Sometimes O(1),
sometimes not?


Bo Persson



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

On Fri,  9 Feb 2007 22:44:37 GMT, Howard Hinnant wrote:

>One way I like to think about this view is to draw an analogy with the
>string constructors.  Consider:
>
>const char* message = ...;
>// for whatever reason you acquire the strlen(message):
>unsigned len = ...;
>// Now you want to construct a std::string:
>std::string s(message);  // Wasteful!
>                         // string must recompute strlen(message)
>
>// This is better:
>std::string s(message, len);

Going a tad off at a tangent, the wording in [string.cons] par.5 looks
very odd to me: the argument n is acquired from the caller, so what
does it mean to say "the array [...] of length n"? I see no reason not
to pass, say, n == 1 even if the array has 100 elements. And of course
there's always the option to include or not the terminating null
character (is the "length" of "test" 4 or 5?). Wouldn't the following
rewording be in order?

  Effects: Constructs an object of class basic_string with size()==n
           and whose string value consists of the first n elements
           of the array whose first element is pointed to by s, in
           the same order they appear in that array.
           Post conditions indicated in table 54 will be met:

Genny.

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

> If I write a function taking a referece to a list, I cannot tell the
> complexity of size(). It depends on whether someone else just did a splice
> to or from that list, without an intervening call to size(). Sometimes
O(1),
> sometimes not?

Yes. And I see no way round that. The current status quo is the best that
there is. I see no point in altering it in favour of either camp. A quality
implementation may miminise the effects and try and ensure both size() and
splice() are O(1) most of the time, but if a programmer writes alternative
calls to each, then size() is likely to be O(N).

Stephen Howe


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

On Feb 10, 6:57 pm, "Bo Persson" <b...@gmb.dk> wrote:
> Stephen Howe wrote:
> >> I would personally like to make this even stronger, by enforcing
> >> list::splice(iterator, list, iterator, iterator) was O(1), and
> >> size() is O(1) except after that function is called.
>
> Only if you write all the processing for the list. Otherwise you still don't
> know the complexity of size().
>
> If I write a function taking a referece to a list, I cannot tell the
> complexity of size(). It depends on whether someone else just did a splice
> to or from that list, without an intervening call to size(). Sometimes O(1),
> sometimes not?

I admit this situation is not ideal by any means, really it should
have been fixed in the original standard one way or the other. However
seeing as there is zero chance of fixing the problem now, the standard
should at least minimise it's effect?

Chris

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

howard.hinnant@gmail.com (Howard Hinnant) wrote (abridged):
> One way I like to think about this view is to draw an analogy with the
> string constructors.

But with the string constructor the length is needed to support embedded
nuls. There is no way for the constructor to know the length of the string
unless it is passed explicitly. It's not redundant.

Where-as with splice, the length is redundant. So the analogy is not very
strong.

-- Dave Harris, Nottingham, UK.

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

> void splice(iterator position, list& x,
>             iterator first, iterator last,
>             size_type n);
>
> Effects: Inserts elements in the range [first, last) before position and
> removes the elements from x.

But if you are going to do that, why not have

inplace_merge(bid_iterator first, bid_iterator mid, bid_iterator last,
size_type n1, size_type n2)

where

n1 = distance(first, mid);
n2 = distance(mid, last);

It saves having to determine the distance on startup of the algorithm,
particularly if  inplace_merge() is called with truly bidirectional
iterators.

Similarly for other algorithms that take forward/bidirectional iterators.

Stephen Howe


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

> I admit this situation is not ideal by any means, really it should
> have been fixed in the original standard one way or the other.

How can it be fixed?
It is impossible that some variations of splice() and size() to be O(1) at
the same time, one after the other.

> However seeing as there is zero chance of fixing the problem now...

And how could it have been "fixed" some time ago?

>, the standard
> should at least minimise it's effect?

Okay. You could mandate that all implementations cache the size and adopt a
lazy policy - if invalid - dont recompute the size until it is actually
needed either internally or externally. That would mean if noone ever called
splice(), size() is always O(1), and if there were 100's of splice() calls
they also will be O(1), but if you alternate calls to size() and splice(),
the size() will be O(N).

I dont see how you can "fix" this so that both splice() is O(1) in all
circumstances and size() is O(1) in all circumstances, desirable though it
may be. The standard knows this. It is insoluble.

Stephen Howe


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

In article <CNmdnX75cJxtilPYRVnyhAA@pipex.net>,
 sjhoweATdialDOTpipexDOTcom@giganews.com ("Stephen Howe") wrote:

> > If I write a function taking a referece to a list, I cannot tell the
> > complexity of size(). It depends on whether someone else just did a splice
> > to or from that list, without an intervening call to size(). Sometimes
> O(1),
> > sometimes not?
>
> Yes. And I see no way round that. The current status quo is the best that
> there is. I see no point in altering it in favour of either camp. A quality
> implementation may miminise the effects and try and ensure both size() and
> splice() are O(1) most of the time, but if a programmer writes alternative
> calls to each, then size() is likely to be O(N).

Imho the current status quo is the worst possible outcome.

The best would be one of:

1.  Require O(1) size().
2.  Remove list::size().

An O(n) size() is nothing but a trap waiting to catch the next
programmer, expert or not.  Not having it at all would be far higher
quality than having it, and having it be O(n).  If list::size() didn't
exist, and you needed that information, std::distance(l.begin(),
l.end()) is neither difficult, nor error prone.

>From Stroustrup's "The C++ Programming Language, 3rd ed", section
16.3.3, Element Access:

> Of the standard sequences, only vector and deque support subscripting.  The
> reason is the desire not to confuse users by providing fundamentally
> inefficient operations.  For example, subscripting could have been provided
> for list, but doing that would have been dangerously inefficient (that is,
> O(n)).

Imho, size() is no different than subscripting in this regard.  And I
believe predominant use cases of list::size() in existing non-demo code
support my view that an O(n) size() approaches the danger of an O(n)
subscripting operator.

I ask everyone to scan existing (non-demo) code for uses of list::size()
today.  The odds that you'll find list::size() being improperly used are
shockingly high.  And just the exercise of scanning for the use of
list::size() is a scary experience in itself.  It is difficult to merely
search for uses of "list" and "size".  The most effective way to find
uses of list::size() in a large code base is to actually edit the size()
member out of <list> and try to compile.

The next exercise is far simpler:  Scan for uses of "splice some from
other".  Is it being improperly used?  Is the length of "some" known or
easily computed before the splice?

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

In article <memo.20070211154118.3204A@brangdon.cix.compulink.co.uk>,
 brangdon@cix.co.uk (Dave Harris) wrote:

> howard.hinnant@gmail.com (Howard Hinnant) wrote (abridged):
> > One way I like to think about this view is to draw an analogy with the
> > string constructors.
>
> But with the string constructor the length is needed to support embedded
> nuls. There is no way for the constructor to know the length of the string
> unless it is passed explicitly. It's not redundant.
>
> Where-as with splice, the length is redundant. So the analogy is not very
> strong.

The length *might* be redundant, depending upon how the client is using
the constructor.

> I think and AFAIK the first example of an "algorithm" in the standard, that
> has this property.

Here is an example of redundant information being passed in:

allocator::deallocate(pointer p , size_type n);

Requires: n shall equal the value passed as the first
argument to the invocation of allocate which returned p.

If I understand correctly, the rationale for this design decision was
efficiency.  The client likely needs the (p,n) paired information
anyway, so there is little motivation to store it internal to the
allocator.  Just trust the client to pass the right paired information
back on deallocate.

Note that I'm not suggesting the current splice signature be removed.
If the client does not care to pass in the length of the splice range,
he does not have to.  I'm just trying to offer the client who is
concerned about performance, and knowledgeable in this area, the option
to pass this information in, as an optimization.  This seems like a mild
position to me, compared to the position of refusing the client the
ability to pass in this helpful information.

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

In article <GIadnVlC574o4lLYRVnysAA@pipex.net>,
 sjhoweATdialDOTpipexDOTcom@giganews.com ("Stephen Howe") wrote:

> > void splice(iterator position, list& x,
> >             iterator first, iterator last,
> >             size_type n);
> >
> > Effects: Inserts elements in the range [first, last) before position and
> > removes the elements from x.
>
> But if you are going to do that, why not have
>
> inplace_merge(bid_iterator first, bid_iterator mid, bid_iterator last,
> size_type n1, size_type n2)
>
> where
>
> n1 = distance(first, mid);
> n2 = distance(mid, last);
>
> It saves having to determine the distance on startup of the algorithm,
> particularly if  inplace_merge() is called with truly bidirectional
> iterators.

I'm not going to state that we shouldn't do that.  However I will state
that the need is greater for the splice-some-from-other algorithm.  In
this case the extra information changes the complexity from O(n) to
O(1).  That's a big change.  In the cases you sight, there would be an
efficiency gain, but not to the extent that it would change the
complexity of the algorithm.

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