From: <llewelly@dbritsch.dsl.xmission.com>
To: Michael Vance <briareos@lokigames.com>
Cc: Tudor Hulubei <tudor.hulubei@ecora.com>, gcc@gcc.gnu.org
Subject: Re: list<>.size()
Date: Sat, 01 Apr 2000 01:46:00 -0000 [thread overview]
Message-ID: <Pine.LNX.4.21.0004010240220.25409-100000@dbritsch.dsl.xmission.com> (raw)
In-Reply-To: <20000331180854.F807@namaste.lokigames-lan.com>
On Fri, 31 Mar 2000, Michael Vance wrote:
> On Fri, Mar 31, 2000 at 08:46:00PM -0500, Tudor Hulubei wrote:
>
> > Since splice must be O(1), you can't count the elements you move from
> > one list to another, and therefore it is not possible to keep count
>
> You can if the size of those elements is obtainable in O(1) time, as
> in the MSVC implementation.
>
> > the elements in the target list.
> >
> > Do you have any idea how the Microsoft implementation works so that it
> > achieves O(1) for list<>.size()?
>
> They maintain a size_type member _Size in their list<>. For splice(),
> they simple increment _Size by the size of the spliced in list.
>
> Offhand, it appears that the iterators are then undefined...
>
> I'll retract my ill-thought "trivial", but hope to keep this
> discussion alive. I seem to remember an interview with one of the
> chief STL designers where he stated that list<>.size() should have
> been O(1)--did he not support the consistency of iterators after a
> splice()?
http://www.stlport.org/resources/StepanovUSA.html has an interview with
Alex Stepanov in which he states 'size() used to be linear time in case
of STL lists. It was the right decision since if a user wants to keep a
count it is easy to do, but usually you do not need it and it makes
splice linear time (it used to be constant). But the standard committee
insisted that I change it to constant time. I had no choice. We will
have to change this requirement eventually.'
[snip]
next prev parent reply other threads:[~2000-04-01 1:46 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2000-03-31 16:33 list<>.size() Michael Vance
2000-03-31 17:08 ` list<>.size() Daniel Berlin
2000-03-31 17:34 ` list<>.size() Michael Vance
2000-03-31 17:46 ` list<>.size() Tudor Hulubei
2000-03-31 18:08 ` list<>.size() Michael Vance
[not found] ` <d97lei1oh1.fsf@han.cs.umn.edu>
2000-03-31 19:46 ` list<>.size() Michael Vance
2000-04-01 1:46 ` llewelly [this message]
2000-03-31 18:01 ` list<>.size() Joe Buck
2000-03-31 18:11 ` list<>.size() Michael Vance
2000-04-03 9:05 ` list<>.size() Joe Buck
2000-04-03 13:36 ` list<>.size() Ross Smith
2000-03-31 20:09 ` list<>.size() Dima Volodin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.21.0004010240220.25409-100000@dbritsch.dsl.xmission.com \
--to=llewelly@dbritsch.dsl.xmission.com \
--cc=briareos@lokigames.com \
--cc=gcc@gcc.gnu.org \
--cc=tudor.hulubei@ecora.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).