Topic: Two STL Questions
Author: Francis Glassborow <francis@robinton.demon.co.uk>
Date: 2000/05/19 Raw View
In article <py6U4.463$usz4.2097361@news.xtra.co.nz>, Mark Rodgers
<mark.rodgers@cadenza.co.nz> writes
>Francis Glassborow <francis@robinton.demon.co.uk> wrote in message
>> Yes we will look if asked to do so (no one has yet)
>
>Fair enough. I was wondering what was the next thing to do, and now
>I know. What do you need by way of a request? Has the discussion
>here been sufficient, or do we need to present some sort of formal
>argument as to why we really do think it is broken?
Unless you provide a substantial case, you would be unlikely to get a
different response from the UK. Certainly you should not assume that
those making the decision read this newsgroup. I can assure you that the
original NAD decision was not made lightly so it is in your best
interest to take time providing a solid argument as to why you think it
is.
Francis Glassborow Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/19 Raw View
Francis Glassborow <francis@robinton.demon.co.uk> wrote in message
> I can assure you that the original NAD decision was not made lightly
> so it is in your best interest to take time providing a solid
> argument as to why you think it is.
Jolly good, however I've opted instead to make my request in the form
of another defect report. 192 raised issues that don't concern me
as much and I don't want the baby thrown out with the bath water.
Also, to some extent, I sympathise with the "too big a change" rationale
for 192, so don't really want to resurrect that issue in its entirety,
and would find it hard to present a good argument as to why we should.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/10 Raw View
Howard Hinnant <hinnant@anti-spam_metrowerks.com> wrote in message
> (Just my personal opinion only) This sounds like a redesign as opposed to
> a defect. I see no evidence that "before" was meant instead of "after".
Well I don't have any real evidence that the change was a typo because
I don't know its history. Who wrote those words? What were they using
as a source?
All I do know is that I have HP source code from 1995 that looks before
and not after. So what was actually proposed? Did someone deliberately
change it?
My suspicion is that someone wrote down what they thought the HP code
did (either as part of making the proposal or as a result of the
proposal) and the error was never picked up. IMHO that would
constitute a defect.
That fact is I don't particularly care why it is broken. All I care
about is the fact that it _is_ broken and I hope it will be fixed. I
have not heard any reason not to fix it, and would be sad if legalistic
pedantry prevented it from being fixed sooner rather than later.
>In the meantime I'm aware of at least 3 vendors* that do the before
>check. Two of those (counting myself) do a before check first and then
>the after check. I know of no vendors who currently only do the after
>check (but have not done a survey).
Which is exactly why I think there is urgency. Let's fix it now
while no-one's code is broken. If we wait, then there may well be
vendors that come along and only do the after check. I'd like to
nip that in the bud.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "John E. Potter" <jpotter@falcon.lhup.edu>
Date: 2000/05/11 Raw View
On Wed, 10 May 2000, Howard Hinnant wrote:
> In article <FKvR4.297$H2a4.1114333@news.xtra.co.nz>, "Mark Rodgers"
> <mark.rodgers@cadenza.co.nz> wrote:
>
> > Anyway, given that you now check both before and after, would you have
> > any objection if the standard were changed to say "before" instead of
> > "after"? One single word change, not the "too big a change" mentioned
> > in the 192 rationale. Your library would remain conformant, and the
> > fix (which is what I think it would be) would benefit us as users.
>
> (Just my personal opinion only) This sounds like a redesign as opposed to
> a defect.
This is the most important. If it is a redesign, we can drop the
subject. If it is a defect, there is hope of repair.
> I see no evidence that "before" was meant instead of "after".
Would the original HP documentation 1995 count as evidence? Does
anyone know when it changed from "before" to "after"?
> And "after" poses no serious problems as long as end() is handled in a
> reasonable manner.
After end is a problem only for an implementer. Not being able to say
before begin is the real problem for a user.
> However I agree that the redesign is better than the
> original (which is why I modified our implementation in this way).
> Perhaps this could be changed in a next revision of the standard, and
> perhaps the after check could be left in but deprecated to ease the
> transition.
>
> In the meantime I'm aware of at least 3 vendors* that do the before
> check. Two of those (counting myself) do a before check first and then
> the after check. I know of no vendors who currently only do the after
> check (but have not done a survey). So it seems to me that you could
> count on the before check existing as a defacto-standard. And if it turns
> out that your vendor does not do the before check, you might politely ask
> them if they would. If they won't, it is not a big deal to #ifdef your
> code and conditionally decrement the hint before calling insert. I know
> that's not a perfect solution, but it's the best I've got off the cuff.
It is no solution unless you like the undefined behavior of --begin().
I appreciate your comments, regardless of how mine may sound.
I see the real problem as determinism in equal containers. If that
is an intent, then "before" is a requirement.
For insert(value), I see before upper_bound used. It seems to be
add to the end of the list of equal keys. Is that where "after"
came from? I am happy with anything for this operation including
before lower_bound, before/after first match during descent, or
a random left/right on any match. Whatever gives the implementer
the ability to provide the best service.
For insert(pos, value), I want determinism. It looks and feels
like the same function for sequences. The code that I have seen
implements it as a demand subject to the order requirements of
the container.
The standard is inconsistent in the requirements for this function
between sequences and associatives.
I see three possibilities, there may be others.
1) The intent was for it to be a conditional demand.
2) The intent was for it to be nondeterministic.
3) Nobody ever thought about it.
I can't really believe 2. The intent was to allow noticing that
there is a match and purposely putting it someplace else? I
don't think so.
If 3 is the case, does the inconsistency create a defect? This
is the real question and responses from you and others who will
need to decide that are appreciated.
Please note that the NAD requirement for constant time failure
to insert in unique containers is not in this question. That is
clearly a redesign and not a defect.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Beman Dawes <beman@esva.net>
Date: 2000/05/15 Raw View
Mark Rodgers wrote:
> >In the meantime I'm aware of at least 3 vendors* that do the before
> >check. Two of those (counting myself) do a before check first and then
> >the after check. I know of no vendors who currently only do the after
> >check (but have not done a survey).
>
> Which is exactly why I think there is urgency. Let's fix it now
> while no-one's code is broken. If we wait, then there may well be
> vendors that come along and only do the after check. I'd like to
> nip that in the bud.
That issue (192) has already been closed as not a defect. If you
disagree with that, you have several choices:
* Convince some committee member to ask for a reopening of the issue.
* Ask the UK Panel (I guess by emailing Francis Glassborow or one of
the other UK members) to look at the issue. They agreed to review
issues the public didn't agree with the committee's decision, and can
ask the committee to reopen the discussion if they agree you have a
strong enough point. AFAIK no one has ever taken them up on their
offer.
* Joint the committee. That way you get to have a direct say in the
resolution of all issues.
--Beman Dawes
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Francis Glassborow <francis@robinton.demon.co.uk>
Date: 2000/05/16 Raw View
In article <391D7F0B.97B@esva.net>, Beman Dawes <beman@esva.net> writes
>* Ask the UK Panel (I guess by emailing Francis Glassborow or one of
>the other UK members) to look at the issue. They agreed to review
>issues the public didn't agree with the committee's decision, and can
>ask the committee to reopen the discussion if they agree you have a
>strong enough point. AFAIK no one has ever taken them up on their
>offer.
Yes we will look if asked to do so (no one has yet)
You can also ask your own NB (but if you are US based, they have already
considered it)
>
>* Joint the committee. That way you get to have a direct say in the
>resolution of all issues.
Yes, but you would then have to convince the same people who already
gave NAD decision.
Francis Glassborow Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/17 Raw View
Francis Glassborow <francis@robinton.demon.co.uk> wrote in message
> Yes we will look if asked to do so (no one has yet)
Fair enough. I was wondering what was the next thing to do, and now
I know. What do you need by way of a request? Has the discussion
here been sufficient, or do we need to present some sort of formal
argument as to why we really do think it is broken?
> You can also ask your own NB (but if you are US based, they have
> already considered it)
I've always wondered if New Zealand were involved. I suspect not,
so I doubt I have anyone else to ask. If we are participating, and
someone knows who to contact, please let me know.
Thanks
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Beman Dawes <beman@esva.net>
Date: 2000/05/17 Raw View
Francis Glassborow wrote:
> >* Joint the committee. That way you get to have a direct say in the
> >resolution of all issues.
>
> Yes, but you would then have to convince the same people who already
> gave NAD decision.
True, but a fresh presentation might cause the LWG to reconsider a NAD.
It has happened a couple of times in the past.
--Beman
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Michiel Salters <salters@lucent.com>
Date: 2000/05/09 Raw View
James Kuyper wrote:
> Michiel Salters wrote:
> > In a container of N elements, N+1 valid insertion locations exist.
> > There are N+1 iterators for that container. There is one logical
> > and complete mapping between those sets. insert() uses another,
> > incomplete and illogical mapping.
> Not as far as I can see. For sequences, insert() uses before, and for
> associative containers it's the sort sequence that determines the
> location, not the hint. The hint is used only to speed up the search for
> the insert location, not to control it.
I'm aware of the fact the iterators are hints.
Let's rephrase it:
There are N+1 possible hints to give, and N+1 possible iterators.
There is one trivial mapping from iterator to hint that is complete,
N+1 to N+1. The mapping required by the standard also is trivial,
but not complete. There is no iterator corresponding to the hint
"before the first", and there is no hint corresponding with
container::end().
I therefore argue, that based on the principle of least surprises,
the iterator to hint mapping should be "insert before".
Michiel Salters
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/09 Raw View
Howard Hinnant <hinnant@anti-spam_metrowerks.com> wrote
> Metrowerks used to check after (and only after) just like the standard
> said to. However our latest releases (5.2 and later) check before first,
> then after (unless you are already at end()). The after check is
> maintained for backward compatibility and conformance reasons.
Thank you for clearing that up. So was your code written from scratch,
or did you change what was in the HP implementation?
Anyway, given that you now check both before and after, would you have
any objection if the standard were changed to say "before" instead of
"after"? One single word change, not the "too big a change" mentioned
in the 192 rationale. Your library would remain conformant, and the
fix (which is what I think it would be) would benefit us as users.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: apotter@csrlink.net (Ann Potter)
Date: 2000/05/09 Raw View
On Tue, 9 May 2000 02:21:01 CST, "Mark Rodgers"
<mark.rodgers@cadenza.co.nz> wrote:
> One single word change, not the "too big a change" mentioned
> in the 192 rationale. Your library would remain conformant, and the
> fix (which is what I think it would be) would benefit us as users.
I do not find that sufficient. As long as the equal containers
allow non-deterministic behavior, we have gained nothing. For
insert(pos, value) to be useful, pos must be used whenever it
maintains the order invarient. I am willing to accept QOI for
performance but not for correctness. That is still less than the
"too big a change" and agrees with common implementations.
I think the code was written before the formal documentation. I
think the intent was "If consistent with the order, insert(pos,value)
functions the same as for sequences; otherwise, it is the same as
insert(value). BTW, if pos is valid, there will be no more than two
uses of the compare object; otherwise, the number of uses is logN."
Only the BTW got into the standard.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: hinnant@anti-spam_metrowerks.com (Howard Hinnant)
Date: 2000/05/10 Raw View
In article <FKvR4.297$H2a4.1114333@news.xtra.co.nz>, "Mark Rodgers"
<mark.rodgers@cadenza.co.nz> wrote:
> Thank you for clearing that up. So was your code written from scratch,
> or did you change what was in the HP implementation?
Our current implementation was written from scratch. But it has not
always been so.
> Anyway, given that you now check both before and after, would you have
> any objection if the standard were changed to say "before" instead of
> "after"? One single word change, not the "too big a change" mentioned
> in the 192 rationale. Your library would remain conformant, and the
> fix (which is what I think it would be) would benefit us as users.
(Just my personal opinion only) This sounds like a redesign as opposed to
a defect. I see no evidence that "before" was meant instead of "after".
And "after" poses no serious problems as long as end() is handled in a
reasonable manner. However I agree that the redesign is better than the
original (which is why I modified our implementation in this way).
Perhaps this could be changed in a next revision of the standard, and
perhaps the after check could be left in but deprecated to ease the
transition.
In the meantime I'm aware of at least 3 vendors* that do the before
check. Two of those (counting myself) do a before check first and then
the after check. I know of no vendors who currently only do the after
check (but have not done a survey). So it seems to me that you could
count on the before check existing as a defacto-standard. And if it turns
out that your vendor does not do the before check, you might politely ask
them if they would. If they won't, it is not a big deal to #ifdef your
code and conditionally decrement the hint before calling insert. I know
that's not a perfect solution, but it's the best I've got off the cuff.
-Howard
*Gleaned from private conversations and public statements such as
newsgroup posts.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Matt Austern <austern@sgi.com>
Date: 2000/05/04 Raw View
ark@research.att.com (Andrew Koenig) writes:
> >> 1. What the standard specifies is not what is useful.
>
> >I'm not at all clear why that should be so. There's considerable
> >forward-backward symmetry in the definition of the associative
> >containers. I'm willing to believe I've missed something, but it's not
> >immediately obvious to me why insert-after should be any more or less
> >useful, nor more or less easily implementable, than insert-before.
>
> Insert-after is less useful than insert-before because there is no
> way to use insert-after to put an element at the beginning of a
> sequence, but there is a way to use insert-before to put an element
> at the end, the beginning, or anywhere in between.
And that, in turn, is because STL ranges are asymmetrical. We
indicate a range of iterators by [first, last), where '*first' is the
first value in the range and 'last' points just beyond the last value
in the range. That is, we have a past-the-end iterator but we don't
have a before-the-beginning iterator. This corresponds to the
semantics of C arrays.
If we had before-the-beginning iterators, but no past-the-end
iterators, then insert after would be more useful than insert before.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/04 Raw View
James Kuyper <kuyper@wizard.net> wrote
> I'm willing to believe I've missed something, but it's not
> immediately obvious to me why insert-after should be any more or less
> useful, nor more or less easily implementable, than insert-before.
Specifying that the position where we expect the values should be
inserted is immediately before the given position, has several
advantages:
1. It is consistent with the insert operations on sequences.
2. It provides a natural way to specify beginning and end. If
we expect that the thing we wish to insert belongs at the
beginning then we say c.insert(c.begin(), ...). If we expect
it belongs at the end, we say c.insert(c.end(), ...). As
specified there is no way to hint that the position should be at
the beginning, and the way to specify that it should be at the
end is convoluted: iterator p=c.end();--p;c.insert(p, ...).
3. When working with sorted sequences and insert_iterators,
inserting before produces linear complexity (ignoring
rebalancing) because the hint is always right. When inserting
after it produces n.log(n) complexity because the hint is always
wrong.
OTOH, I do not see any advantages in insert-after.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/04 Raw View
On Wed, 3 May 2000 16:00:12 CST, James Kuyper <kuyper@wizard.net> wrote:
> Mark Rodgers wrote:
> >
> > 1. What the standard specifies is not what is useful.
>
> I'm not at all clear why that should be so. There's considerable
> forward-backward symmetry in the definition of the associative
> containers. I'm willing to believe I've missed something, but it's not
> immediately obvious to me why insert-after should be any more or less
> useful,
Change insert for sequences to after.
Try inserting at the beginning of an associative.
Try giving a meaning to inserting at end of an associative.
Everything is [) ranges. After is nonsense.
> nor more or less easily implementable, than insert-before.
Ok. Explain why the standard specifies after. Please do not tell
me that the standard specifies a useless operation. Please tell
me what wonderful gains I get from an operation which is not
required to do what I ask when it is valid. Example: given a
multiset with five equal entries and a request to insert another
before the third, what do I gain from the standard telling me
that it will go in one of six places and if it happens to be
after, it must be faster?
We know it is broken. We know it is NAD. We know implementations
which do what we expect. We do not understand.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/04 Raw View
On Thu, 4 May 2000 03:52:28 CST, Matt Austern <austern@sgi.com> wrote:
> If we had before-the-beginning iterators, but no past-the-end
> iterators, then insert after would be more useful than insert before.
Well, yes, but so what? We don't have before-the-beginning iterators.
We do have past-the-end iterators. We do have a maybe-after-insert.
It is not quite as useful as a maybe-before-insert. I don't see how
your comments relate to the fact that insert is useless or address
the question of why it is standardized to be broken. The SGI
implementation does exactly what I think it should. Comments in this
thread indicate that it is nonconforming. I see some motivation for
fixing the standard, but none for breaking the existing implementations.
Why is it that no one seems to want to explain why the standard says
what it says.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/04 Raw View
On Wed, 3 May 2000 10:22:56 CST, smeyers@aristeia.com (Scott Meyers)
wrote:
> On Tue, 2 May 2000 05:05:11 CST, John Potter wrote:
> > Dave Abrahams has presented the case that all of those
> > functions should take a const_iterator rather than an iterator. The
> > iplementation can remove the const in constant time.
> It seems to me that it would be a much smaller (and equally effective)
> change to the standard to require some kind of conversion function from
> const_iterator to iterator, possibly iterator member functions (analogous
> to the base() member function for converting reverse_iterators to
> iterators) in conjunction with something in iterator_traits to make it
> possible to perform the conversion on const_iterators that are actually
> pointers.
Neat! You are talking about a named explicit conversion function, not
one of those nasty operator X() thingies. Since const_iterator is
often just a wrapper (adapter) for iterator, the appropriate name might
be base_cast. It does not have the (un)const in it, but it is grepable
like the standard casts.
Can you express it as a defect in the standard?
What does Dave think about the alternative?
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Michiel Salters <salters@lucent.com>
Date: 2000/05/04 Raw View
James Kuyper wrote:
> Mark Rodgers wrote:
> > Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
> > > I stand by my interpretation of the standard though. As you mentioned,
> > > SGI's
> > > approach, while arguably better, is not what it's "supposed" to do.
> > It's not just SGI's approach, its everyone's approach AFAICT. Consider
> > that
> > 1. What the standard specifies is not what is useful.
> I'm not at all clear why that should be so. There's considerable
> forward-backward symmetry in the definition of the associative
> containers. I'm willing to believe I've missed something, but it's not
> immediately obvious to me why insert-after should be any more or less
> useful, nor more or less easily implementable, than insert-before.
Because we can obtain an iterator after the container (container::end()),
but not before the container (container::begin() points to the first
element). This should be reflected in the behavior of insert.
In a container of N elements, N+1 valid insertion locations exist.
There are N+1 iterators for that container. There is one logical
and complete mapping between those sets. insert() uses another,
incomplete and illogical mapping.
Michiel Salters
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Robert Klemme <robert.klemme@myview.de>
Date: 2000/05/04 Raw View
"Gillmer J. Derge" schrieb:
> > The big problem here is that this is a linear-time operation unle=
ss I
> > have a random access iterator, and it's not unreasonable to want =
to
> > convert a list<Widget>::const_iterator to a list<Widget>::iterato=
r in
> > constant time. Surely there's a way, no?
>=20
> I don't think there is. The standard requires that an iterator can be
> converted to a const_iterator but not the other way around (why?).
i think the reason is the same why you cannot turn a const object into a
non-const object without playing some tricks. the reason is obvious:
you can always treat a non-const objekt like a const object, because you
do not change it. but it can be critical to treat a const object like a
non-const object, i.e. modify it, because others might rely on the
constness of this object. similar holds for a const_iterator which is
an iterator to an assumed const container.
regards
robert
--=20
Robert Klemme
Software Engineer
-------------------------------------------------------------
myview technologies GmbH & Co. KG
Riemekestra=DFe 160 ~ D-33106 Paderborn ~ Germany
E-Mail: mailto:robert.klemme@myview.de
Telefon: +49/5251/69090-321 ~ Fax: +49/5251/69090-399
-------------------------------------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/04 Raw View
Scott Meyers <smeyers@aristeia.com> wrote in message
>
> It seems to me that it would be a much smaller (and equally effective)
> change to the standard to require some kind of conversion function from
> const_iterator to iterator, possibly iterator member functions (analogous
> to the base() member function for converting reverse_iterators to
> iterators) in conjunction with something in iterator_traits to make it
> possible to perform the conversion on const_iterators that are actually
> pointers.
Hmmm. Originally you asked for "a moral equivalent of a const_cast".
This struck me as odd: I didn't think such a thing could exist because
const_cast is decidedly immoral. Providing a method to cast away the
constness of const_iterators seems like a very bad idea. It may be
a necessary evil (just as const_cast may be), but perhaps we should
try to do without it if we can.
OTOH, if we wish to insert into a container, we say something like
insert(iter, value);
Why? We have no intention of changing the object pointed to by iter;
we just want to alter its position in the container. This alters the
container (and hence insert is not a const function), but not the
containee. It seems iter should really be const_iter, and the change
proposed by issue #180 seems to be a good idea.
Thus we seem to have a choice between a small Bad Thing, or a larger
Right Thing. I'll leave it to your conscience to decide which to
support. :-)
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/05/05 Raw View
John Potter wrote:
>
> On Wed, 3 May 2000 16:00:12 CST, James Kuyper <kuyper@wizard.net> wrote:
>
> > Mark Rodgers wrote:
> > >
> > > 1. What the standard specifies is not what is useful.
> >
> > I'm not at all clear why that should be so. There's considerable
> > forward-backward symmetry in the definition of the associative
> > containers. I'm willing to believe I've missed something, but it's not
> > immediately obvious to me why insert-after should be any more or less
> > useful,
>
> Change insert for sequences to after.
I agree, that would be a problem, for all the reasons you imply.
> Try inserting at the beginning of an associative.
assoc.insert(assoc.begin(),t);
If 't' has a key value that unambiguously puts it at the beginning of
the container, it will go there. If a matching key already exists in the
container, insert will fail if the container type requires unique keys.
Otherwise it will succeed in placing it in an unknown location in or
adjacent to the current block of equivalent keys at the beginning. If
you care which one of those equivalent keys comes first, you should use
a different comparison function, or possibly a different container type,
such as std::map<std::vector<T>>.
....
> > nor more or less easily implementable, than insert-before.
>
> Ok. Explain why the standard specifies after. Please do not tell
It doesn't. It only says what happens if the insertion location happens
to be after the hint. In those rare circumstances where the
implementation has a choice in the insertion place, the standard doesn't
even imply that 'after' is the preferred location. In precisely those
circumstances, there is no way for a user to ensure the applicability of
the guarantee.
> me that the standard specifies a useless operation. Please tell
> me what wonderful gains I get from an operation which is not
> required to do what I ask when it is valid. Example: given a
> multiset with five equal entries and a request to insert another
> before the third, what do I gain from the standard telling me
> that it will go in one of six places and if it happens to be
> after, it must be faster?
In that circumstance, you gain nothing. That doesn't mean the guarantee
is useless, just that it isn't useful in that circumstance.
The 'linear' guarantee isn't specific to equivalent keys. It isn't even
specific to containers that allow multiple keys. It applies to all
hinted insertions into any associative container. The linear time
guarantee is useful mainly for unequal keys known to be unique (whether
or not the container allows non-unique keys), because that's the only
situation where the user can ensure it's applicability.
A linear time guarantee for a before insertion would, as far as I can
tell, be equally convenient, it merely requires a re-organization of the
code that uses it. Off-hand I can't think of any reason why the most
convenient hint to use should be more likely to be the one the will end
up after the insertion point, rather than the one that will end up
before it.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/05/05 Raw View
Michiel Salters wrote:
>
> James Kuyper wrote:
>
> > Mark Rodgers wrote:
>
> > > Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
>
> > > > I stand by my interpretation of the standard though. As you mentioned,
> > > > SGI's
> > > > approach, while arguably better, is not what it's "supposed" to do.
>
> > > It's not just SGI's approach, its everyone's approach AFAICT. Consider
> > > that
>
> > > 1. What the standard specifies is not what is useful.
>
> > I'm not at all clear why that should be so. There's considerable
> > forward-backward symmetry in the definition of the associative
> > containers. I'm willing to believe I've missed something, but it's not
> > immediately obvious to me why insert-after should be any more or less
> > useful, nor more or less easily implementable, than insert-before.
>
> Because we can obtain an iterator after the container (container::end()),
> but not before the container (container::begin() points to the first
> element). This should be reflected in the behavior of insert.
>
> In a container of N elements, N+1 valid insertion locations exist.
> There are N+1 iterators for that container. There is one logical
> and complete mapping between those sets. insert() uses another,
> incomplete and illogical mapping.
Not as far as I can see. For sequences, insert() uses before, and for
associative containers it's the sort sequence that determines the
location, not the hint. The hint is used only to speed up the search for
the insert location, not to control it. You might want to control the
insertion order of equivalent keys, but the right way to do that is to
either use a comparison operator that treats them as inequivalent, or to
use a map<Key,Container<T>>, where Container is one that allows you to
control the order.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/05 Raw View
James Kuyper <kuyper@wizard.net> wrote in message
news:3910E714.45CAB8D8@wizard.net...
> John Potter wrote:
> > Try inserting at the beginning of an associative.
>
> assoc.insert(assoc.begin(),t);
>
> If 't' has a key value that unambiguously puts it at the beginning of
> the container, it will go there.
But in logarithmic time. How can I get amortized constant time if I know
it really does belong at the beginning? A particular implementation might
choose to look before as well as after, but I want something guaranteed by
the standard.
> A linear time guarantee for a before insertion would, as far as I can
> tell, be equally convenient...
Consider the case where I know the value belongs at the end and want
amortized constant time insertion. I don't believe you really mean to
imply that
iterator p = c.end();
if (! c.empty())
--p;
c.insert(p, value);
is just as convienent as
c.insert(c.end(), value);
> ... it merely requires a re-organization of the code that uses it.
Given that no implementations I know of implement insert-after, I don't
think being afraid of breaking existing code should deter us from fixing
the defect in the standard.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: scorp@btinternet.com (Dave Harris)
Date: 2000/05/05 Raw View
mark.rodgers@cadenza.co.nz (Mark Rodgers) wrote:
> Hmmm. Originally you asked for "a moral equivalent of a const_cast".
> This struck me as odd: I didn't think such a thing could exist because
> const_cast is decidedly immoral. Providing a method to cast away the
> constness of const_iterators seems like a very bad idea. It may be
> a necessary evil (just as const_cast may be), but perhaps we should
> try to do without it if we can.
It would be OK as long as it requires a reference to a non-const iterator
(or the container itself). For example, we can already use code like:
iterator safe_cast( const_iterator i, iterator j ) {
size_t d = distance<const_iterator>( j, i );
advance<iterator,size_t>( j, d );
return j;
}
This needs a conversion in the safe direction, from non-const to const,
and of course has various range limits (eg the iterators should come from
the same collection) and may be slow, but it's not immoral. It would be
safe to add this to the STL, if people needed it for the sake of
convenience and efficiency.
I agree it would be very dubious to allow a cast which wasn't equivalent
to the safe things we can already do.
> Thus we seem to have a choice between a small Bad Thing, or a larger
> Right Thing. I'll leave it to your conscience to decide which to
> support. :-)
I agree with this, too :-) The bad collections API is the main reason we
need to cast at all.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/06 Raw View
Problem 1: before/after. You seem to agree that there is no reason
for after. Since those of us who care want before, I guess you have
no objections. I would like to know why "before" was changed to
"after" at some point in time. It is not a typo; so, there must have
been a reason. Anyone?
On Fri, 5 May 2000 02:45:37 CST, James Kuyper <kuyper@wizard.net> wrote:
> John Potter wrote:
> >
> > Try inserting at the beginning of an associative.
>
> assoc.insert(assoc.begin(),t);
>
> If 't' has a key value that unambiguously puts it at the beginning of
> the container, it will go there. If a matching key already exists in the
> container, insert will fail if the container type requires unique keys.
> Otherwise it will succeed in placing it in an unknown location in or
> adjacent to the current block of equivalent keys at the beginning.
Problem 2: The "hint" requires testing to see if it is valid in order
to meet the complexity requirements. What is the problem with stating
that a valid "hint" must be used?
A class which might be nice in the next revision of the standard. Just
the basic parts. Concept credit to Dietmar Kuehl.
template <class T>
class stable_priority_queue {
multiset<T> q;
public :
const_reference top() const { return *--q.end(); }
void push(const value_type& x) { c.insert(q.lower_bound(x), x); }
void pop() { q.erase(--q.end()); }
};
Isn't that nice? It works quite well on some implementations. The
problem is that the standard does not support it.
> If
> you care which one of those equivalent keys comes first, you should use
> a different comparison function, or possibly a different container type,
> such as std::map<std::vector<T>>.
Replace the multiset<T> above with map<T, queue<T> >. If you don't
notice the increased complexity, I assure you the cpu will.
To repeat the question, what is gained by making the "hint" only a
hint to be ignored when it can't always be ignored?
Problem 3: Insert_iterator. The effects of operator= are given as
iter = container->insert(iter, value);
++ iter;
While this is correct for sequences, it is wrong for associatives.
container->insert(iter, value);
would be correct with insert before, while
iter = container->insert(iter, value);
would be correct with insert after. Insert_iterator should be
specialized for associatives to give linear time.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: scorp@btinternet.com (Dave Harris)
Date: 2000/05/08 Raw View
jpotter@falcon.lhup.edu (John Potter) wrote:
> Problem 1: before/after. You seem to agree that there is no reason
> for after. Since those of us who care want before, I guess you have
> no objections. I would like to know why "before" was changed to
> "after" at some point in time. It is not a typo; so, there must have
> been a reason. Anyone?
Here's a guess. If you are merging a stream of values which is itself in
ascending order, the correct insertion point for each value will be after
the one before. Perhaps not immediately after, but it will never be
before.
I'm thinking here of a destructive, in-place merge. Like A=a,b,f,g;
B=c,d,h yields A=a,b,c,d,f,g,h. The insert for c returns an iterator which
is exactly right for inserting d in constant time.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: hinnant@anti-spam_metrowerks.com (Howard Hinnant)
Date: 2000/05/08 Raw View
In article <390f7ad6.22292519@news.csrlink.net>, jpotter@falcon.lhup.edu
(John Potter) wrote:
> Care to mention the "some
> implementers" mentioned in the NAD?
I am one of the people referred to in the rationale of issue 192 (Metrowerks).
In article <tskQ4.587$h%W3.2556186@news.xtra.co.nz>, "Mark Rodgers"
<mark.rodgers@cadenza.co.nz> wrote:
> Given that no implementations I know of implement insert-after, I don't
> think being afraid of breaking existing code should deter us from fixing
> the defect in the standard.
Metrowerks used to check after (and only after) just like the standard
said to. However our latest releases (5.2 and later) check before first,
then after (unless you are already at end()). The after check is
maintained for backward compatibility and conformance reasons.
-Howard
Senior Library and Performance Engineer
Metrowerks
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Gillmer J. Derge" <gderge1@nycap.rr.com>
Date: 2000/05/02 Raw View
John Potter wrote:
> The standard does not specify where a new item will be inserted
> within the range of existing matches; however, it will stay
> where it is inserted.
Note that if it's important, you can increase the likelihood that the new
item will be inserted where you want by using the form of insert that takes
an iterator hint. For example:
T x;
theSet.insert(theSet.lower_bound(x), x);
theSet.insert(theSet.upper_bound(x), x);
A very literal reading of the standard implies that the implementation is not
required to use the hint. "Iterator p is a hint pointing to where the insert
should start to search." Regarding complexity, the standard reads, "...
amortized constant if t is inserted right after p." It does not, however,
explicitly say under what circumstances or in what way the hint must be
used. /If/ it is used and /if/ it is used in such a way that the insert
occurs right after p, then the complexity will be amortized constant. Still,
I suspect that any reasonable implementation would use the hint as expected.
-----
Gillmer J. Derge
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Jean-Daniel Nicolet" <jdn@llinkvest.ch>
Date: 2000/05/02 Raw View
Scott Meyers wrote:
> - If I have a multiset<Widget> mw and I insert a new widget w into it,
> does the standard specify where in the range [mw.lower_bound(w),
> mw.upper_bound(w)) the new copy of w will be inserted? My reading of
> the standard says no, but it would not stun me if I missed something.
Given the mathematical definition of the strict weak ordering relation that
underlies container construction, there cannot be any way to specify the
insertion place in an equal range, because such elements are, well, regarded
as equivalent (they belong to the same equivalence class of the equivalence
relation induced by the ordering relation) and so nothing distinguishes one
element of an equivalent class from another, at least from the ordering
point of view.
So there is no way for the standard to go in that direction, unless some
additionnal property of either the container or the inserted items is used,
that is something going beyond the sole use of the key and the attached
ordering relation properties.
If you nonetheless need to control the instertion place, there is a
possibility: extend the ordering relation with an additional field, making
all elements strictly distinct during insertion, like follows:
class Item
{
Key m_key; // Key used till yet to build the order relation
double m_location; // Extension field to make all items distinct
...
};
class InsertionFunctor
{
bool operator()( const Item& lhs, const Item& rhs ) const
{ return lhs.getKey() < rhs.getKey() || (!(rhs.getKey() <
lhs.getKey()) && lhs.getLocation() < rhs.getLocation()); }
// The '<' operator used here is the original relation
};
The above functor is actually a lexicographical extension of the original
relation. The left part of the logical clause tests for the original
ordering relation. If true, then we are not in the case of an equal range.
Else, we check the underlying equivalence relation, which is defined as x ~
y <==> !(x < y) && !(y < x). The first half is guaranteed by the short
circuit evaluation of the if. We check for the second part (the !(y < x))
and, if true, we know that both keys are in the same equivalence class, so
we use the additional location field to order them, thus forcing the
insertion place. This functor will then be used to instantiate the container
(i.e. it will be used during construction).
Now, given two successive items in the container, say t and u, and you have
a new item, say x, that you want to insert between the two, do the
following:
- First, make sure that the usual key matches that condition (i.e that t.Key
<= x.Key <= u.key, the '<=' relation here meaning "either strictly smaller
than or equivalent to".
- Second, compute an intermediate location for your new item, as follows:
x.setLocation( (t.getLocation() + u.getLocation()) * 0.5 ).
Now, inserting x into the container using the above-defined insertion
functor will place the item at the desired location into the container. For
retrieval, you can still use the usual ordering relation, though you must
then use the external algorithms instead of the ones provided by the
container, because the container methods will use the ordering functor given
at construction, which is the artifical one in our case, not the natural one
you had to begin with.
The way to compute the intermediate location relies on the underlying double
member having sufficient precision to be able to obtain a truly different
number than the two used to compute it, so using an integer is nearly
impossible here, unless you know in advance how many items will be inserted,
or you devise a renumbering scheme, much like in the old days of BASIC, when
you had to renumber the lines to be able to insert a new line between two
already existing ones.
A practical problem that may arise here is how to find t in the first place
? We suppose in that case that you have some way of knowing it (else we
don't see any reason to ask for a strict ordering if there is no external
way to distinguish items). The u item may be found by simply taking a copy
of the iterator on t and incrementing it (constant time complexity for
both). Then the iterator on t can be used as insertion hint in the container
and if your implementation is clever enough to use it, the insertion itself
will occur in constant time, that is better than in the general case, where
you only can count on a log(n) complexity bound. There is obviously a reason
for that apparent bonus: you did the finding work yourself to determine the
iterator on t. If you apply a conventional find to determine t's iterator,
then you have already paid the logarithmic price. Else you have used some
external knowledge of the problem (having a hand on t) to reduce the
insertion work.
The above way of doing things may seem a little overkill at first, but it
relies on a very useful and powerful technique: using two different,
although compatible, ordering relations to manipulate a container, one
during the insertion phase, and the other during retrieval. It is guaranteed
to work, provided one of the ordering relation being stricter than the
other. The exact mathematical definition of "stricter" goes beyond the scope
of this answer, but it is intuitively clear what is meant. It goes down to
something like the extension trick presented here above.
Hoping to have opened some new ways of dealing with containers and order
relations.
Jean-Daniel Nicolet
Software Consultant
Geneva
Switzerland
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/05/02 Raw View
Dave Abrahams wrote:
>
> in article 390d619a.3791304@news.csrlink.net, John Potter at
> jpotter@falcon.lhup.edu wrote on 5/2/00 12:17 AM:
>
> >> You didn't miss anything, except perhaps that you can insert into a
> >> multiset in amortized constant time provided you provide an iterator
> >> argument and the insertion occurs just after the iterator. I consider
> >> this a rather weak guarantee at best, though.
> >
> > Surely you jest. Insert *after* is absurd. Insert is before, append
> > is after. The SGI implementation honors insert before and does give
> > amortized constant time. The standard offers nothing.
>
> Table 69--Associative container requirements
>
>
> ----------------------------------------------------------------------------
> expression return type assertion/note complexity
> pre/post-condition
>
> ---------------------------------------------------------------------------
> a.insert(p,t) iterator inserts t if and only if there is logarithmic in
> no element with key equivalent to general, but amor-
> the key of t in containers with tized constant if
> unique keys; always inserts t in t is inserted
> containers with equivalent keys. right after p.
> always returns the iterator point-
> ing to the element with key equiva-
> lent to the key of t. iterator p
> is a hint pointing to where the in-
> sert should start to search.
>
> > A common use
> > is inserter(container, container.end()). Now how do you "insert"
> > after end?
>
> I don't know. Maybe this is a defect.
It's not a defect. Note that 'p' is only a hint for associative
containers; the container is not required to pay any attention to it.
insert() is allowed to insert the element anywhere within the block of
equivalent elements. The constant time guarantee applies only if element
is inserted after 'p', and there's nothing you can do to guarantee that
location if the two elements have keys that compare equal.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Gillmer J. Derge" <gderge1@nycap.rr.com>
Date: 2000/05/02 Raw View
John Potter wrote:
> Surely you jest. Insert *after* is absurd. Insert is before, append
> is after. The SGI implementation honors insert before and does give
> amortized constant time. The standard offers nothing. A common use
> is inserter(container, container.end()). Now how do you "insert"
> after end?
No jesting. The iterator is a "hint" as to where the implementation should
begin its search for the proper insert location. Thus, if the hint is taken,
the insert occurs somewhere after the iterator. Obviously, you don't insert
after end, so in that case, the hint would be ignored.
I strongly doubt that SGI does an insert before. In fact, consider what a set
is -- an /ordered/ container. You can't specify the insert location at all,
regardless of your chosen semantics of "insert" vs. "append," since the insert
location is dictated by the ordering. All you can do is offer a hint or
suggestion. All of this is specified by the standard.
Excerpts from section 23.1.2, Table 69:
a.insert(p, t)
always inserts t in containers with equivalent keys. always returns the
iterator pointing to the element with key equivalent to the key of t.
iterator p is a hint pointing to where the insert should start to search.
logarithmic in general, but amortized constant if t is inserted right after p.
-----
Gillmer J. Derge
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/02 Raw View
Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
> I strongly doubt that SGI does an insert before.
Well they must have changed it then. Certainly every implementation
I've looked at - original HP, Rogue Wave, and STLport - have inserted
before in constant time, and after in logarithmic time, in defiance
of what it says in the standard.
I think the standard simply made a mistake. Originally I thought this
was to avoid going backwards. If we have position i, and want to know
whether the insert goes before i, we need to see if
*(i-1) <= value <= *i
To do this we need to have bidirectional iterators, and I thought that
perhaps the standard didn't wish to require associative containers to
support bidirectional iterators. However I was wrong - see 23.1.2/6.
"iterator of an associative container is of the bidirectional
iterator category."
One of the times this becomes important is when you use an insert
iterator to copy a sorted sequence into an associative container.
Consider this:
std::vector<char> v;
v.push_back('A');
v.push_back('B');
v.push_back('C');
std::set<char> s;
std::copy(v.begin(), v.end(), std::inserter(s, s.end()));
(or
std::copy(v.begin(), v.end(), std::inserter(s, s.begin()));
- it doesn't matter since s.begin() == s.end())
Now look at the implementation insert_iterator::operator=. For the
first element ('A'), we do this:
iter = container->insert(container->end(), 'A');
// 'A' does not go after end() so hint is useless
// => insert takes log(n) time
// iter now points to 'A';
++iter; // iter points to end();
The same happens when we insert B and C. After each one, iter
always points to end(), which is never where we want to insert
the next one. OTOH, if we tried to insert before the hint,
the hint would always be correct.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/02 Raw View
On Sat, 29 Apr 2000 04:28:32 CST, smeyers@aristeia.com (Scott Meyers)
wrote:
> Two STL Questions, both inspired by questions from the students in the
> class I taught earlier this week (in case you think I make these up myself
> :-}):
>
> - If I have a multiset<Widget> mw and I insert a new widget w into it,
> does the standard specify where in the range [mw.lower_bound(w),
> mw.upper_bound(w)) the new copy of w will be inserted? My reading of
> the standard says no, but it would not stun me if I missed something.
No. Even if you use the insert with hint form, there is still nothing
to say where it will go.
> - Given a Container::const_iterator, is there a constant-time way to
> create the corresponding Container::iterator? What I'm looking for is
> the moral equivalent of a const_cast, but for iterators. The only
> thing I could come up with was
>
> Container c;
> Container::const_iterator ci;
> ... // make ci point into c
> Container::iterator i(c.begin());
> advance(i, distance(Container::const_iterator(c.begin), ci));
>
> The big problem here is that this is a linear-time operation unless I
> have a random access iterator, and it's not unreasonable to want to
> convert a list<Widget>::const_iterator to a list<Widget>::iterator in
> constant time. Surely there's a way, no?
No. Why is it not unreasonable?
Both of these questions have been discussed recently either here or
in clc++m.
On the second one, if you simply want to modify the iteratee, the
normal const_cast on *i will do the job. If you want to do something
like call container.erase, I think there may be a defect report on
this subject. Dave Abrahams has presented the case that all of those
functions should take a const_iterator rather than an iterator. The
iplementation can remove the const in constant time.
Of course, if you have an implementation where set::iterator and
set::const_iterator are the same type, there is a constant time
conversion for those cases. ;-)
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: smeyers@aristeia.com (Scott Meyers)
Date: 2000/05/02 Raw View
On Mon, 1 May 2000 16:10:06 CST, Dave Abrahams wrote:
> Is it possible that this question was inspired by the same problem that
> generated open library issue #180
I'd say it's VERY possible :-)
Scott
--
"Effective STL" Seminar June 7-9 Portland, Oregon
Details at http://www.trekservices.com/estl/
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Gillmer J. Derge" <gderge1@nycap.rr.com>
Date: 2000/05/02 Raw View
Mark Rodgers wrote:
> Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
>
> > I strongly doubt that SGI does an insert before.
>
> Well they must have changed it then. Certainly every implementation
> I've looked at - original HP, Rogue Wave, and STLport - have inserted
> before in constant time, and after in logarithmic time, in defiance
> of what it says in the standard.
You're right. I should have looked. It very clearly inserts before (the
iterator is even called "__before"). The documentation at SGI's web site
also agrees with their implementation.
I stand by my interpretation of the standard though. As you mentioned, SGI's
approach, while arguably better, is not what it's "supposed" to do.
-----
Gillmer J. Derge
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/02 Raw View
On Tue, 2 May 2000 07:17:54 CST, "Gillmer J. Derge"
<gderge1@nycap.rr.com> wrote:
> I stand by my interpretation of the standard though. As you mentioned,
> SGI's approach, while arguably better, is not what it's "supposed" to do.
Does the standard really say what it is supposed to do with the "hint".
set<int> s;
set<int>::iterator i(s.end());
for (int x = 0; x < N; ++ x)
i = s.insert(i, x);
If I time this and find that it is NlgN, does that make the
implementation non-conforming?
Using insert before.
for (int x = 0; x < N; ++ x, ++ i)
i = s.insert(i, x);
This being linear would not make it non-conforming, just useful.
Hum, maybe I see the nonsense. The ++ from back to end is lgN.
for (int x = 0; x < N; ++ x)
s.insert(i, x);
Now we get linear, but the standard inserter uses the one above
which does not give linear for either before or after.
Looks like a loose-loose situation. The only other use would be
to allow placing an item where we want it in a multiset, but there
is no assurance that it will be either before or after when the
keys match.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/05/03 Raw View
John Potter wrote:
>
> On Tue, 2 May 2000 07:17:54 CST, "Gillmer J. Derge"
> <gderge1@nycap.rr.com> wrote:
>
> > I stand by my interpretation of the standard though. As you mentioned,
> > SGI's approach, while arguably better, is not what it's "supposed" to do.
>
> Does the standard really say what it is supposed to do with the "hint".
No.
> set<int> s;
> set<int>::iterator i(s.end());
> for (int x = 0; x < N; ++ x)
> i = s.insert(i, x);
> If I time this and find that it is NlgN, does that make the
> implementation non-conforming?
Yes. Since there are no duplicate keys, and the hint provided is an
iterator pointing precisely the previous key, each insertion must be
constant-time. Thus, the overall time should be O(N).
> Using insert before.
> for (int x = 0; x < N; ++ x, ++ i)
> i = s.insert(i, x);
> This being linear would not make it non-conforming, just useful.
Correct.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/03 Raw View
On Tue, 2 May 2000 04:36:41 CST, "Mark Rodgers"
<mark.rodgers@cadenza.co.nz> wrote:
I agree with Mark's analysis.
> I think the standard simply made a mistake.
I thought that it was a typo until I read the NAD response which
states that some implementations use after and do not want to
change.
> Consider this:
>
> std::vector<char> v;
> v.push_back('A');
> v.push_back('B');
> v.push_back('C');
>
> std::set<char> s;
> std::copy(v.begin(), v.end(), std::inserter(s, s.end()));
> (or
> std::copy(v.begin(), v.end(), std::inserter(s, s.begin()));
> - it doesn't matter since s.begin() == s.end())
Just to play devil's advocate, you don't need this.
std::set<char> s(v.begin(), v.end());
is linear.
Let's try something else.
Given set<T> a, b filled.
vector<T> v;
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(v, v.end()));
// works and is linear because vector<>::insert uses before.
list<T> l;
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(l, l.end()));
// works and is linear because list<>::insert uses before.
set<T> s;
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(s, s.end()));
// works but is NlgN because set<>::insert uses after.
I have used a standard set algorithm with set and it does not work
nicely. How do I get linear performance?
There must be something that I do not understand since I can not
find an example where insert after would be good. Could someone
show me one? Please note the above and do not use an example where
insert(iter1, iter2) could be used.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Gillmer J. Derge" <gderge1@nycap.rr.com>
Date: 2000/05/03 Raw View
John Potter wrote:
> On Tue, 2 May 2000 07:17:54 CST, "Gillmer J. Derge"
> <gderge1@nycap.rr.com> wrote:
>
> > I stand by my interpretation of the standard though. As you mentioned,
> > SGI's approach, while arguably better, is not what it's "supposed" to do.
>
> Does the standard really say what it is supposed to do with the "hint".
> set<int> s;
> set<int>::iterator i(s.end());
> for (int x = 0; x < N; ++ x)
> i = s.insert(i, x);
> If I time this and find that it is NlgN, does that make the
> implementation non-conforming?
Yes. It says that the complexity is "amortized constant, if t is inserted
right after p." That's about all it says, but it does say that much.
> Using insert before.
> for (int x = 0; x < N; ++ x, ++ i)
> i = s.insert(i, x);
> This being linear would not make it non-conforming, just useful.
Correct. One obvious, but not necessarily good, solution would be for insert
to check both before and after the hint. Then if, for example, the check for
after was done second, both cases would be linear, but after would have a
larger constant factor. Again, I'm not suggesting that this is actually a good
idea.
-----
Gillmer J. Derge
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/03 Raw View
Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
> I stand by my interpretation of the standard though. As you mentioned,
SGI's
> approach, while arguably better, is not what it's "supposed" to do.
It's not just SGI's approach, its everyone's approach AFAICT. Consider
that
1. What the standard specifies is not what is useful.
2. What the standard specifies is not what anyone does currently.
3. What the standard specifies is not what the original submission did.
IMHO this is a defect in the standard and the solution is to change two
words - "right after" to "immediately before".
"logarithmic in general,
but amortized constant
if t is inserted immediately
before p."
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Mark Rodgers" <mark.rodgers@cadenza.co.nz>
Date: 2000/05/03 Raw View
John Potter <jpotter@falcon.lhup.edu> wrote in message
>
> I thought that it was a typo until I read the NAD response which
> states that some implementations use after and do not want to
> change.
I would be interested to know which implementations. All the
implementations I have seen look before and do _not_ look after,
so they will have to change, unless the standard does.
> Just to play devil's advocate, you don't need this.
>
> std::set<char> s(v.begin(), v.end());
>
> is linear.
I realise that, but the code was cut down to illustrate the point.
In reality there are still situations where you have an existing,
already constructed associative container and you need to copy
(a possibly sorted) range into it. Unfortunately, associative
containters do not have an insert(pos,first,last).
>There must be something that I do not understand since I can not
>find an example where insert after would be good. Could someone
>show me one?
I would be interested too. As I said earlier, I initially thought
after was specified to avoid the need for bidirectional iterators,
but that's not it.
Mark
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: smeyers@aristeia.com (Scott Meyers)
Date: 2000/05/03 Raw View
On Tue, 2 May 2000 05:05:11 CST, John Potter wrote:
> On Sat, 29 Apr 2000 04:28:32 CST, smeyers@aristeia.com (Scott Meyers)
> wrote:
> > - Given a Container::const_iterator, is there a constant-time way to
> > create the corresponding Container::iterator? What I'm looking for is
>
> On the second one, if you simply want to modify the iteratee, the
> normal const_cast on *i will do the job. If you want to do something
> like call container.erase, I think there may be a defect report on
> this subject. Dave Abrahams has presented the case that all of those
> functions should take a const_iterator rather than an iterator. The
> iplementation can remove the const in constant time.
It seems to me that it would be a much smaller (and equally effective)
change to the standard to require some kind of conversion function from
const_iterator to iterator, possibly iterator member functions (analogous
to the base() member function for converting reverse_iterators to
iterators) in conjunction with something in iterator_traits to make it
possible to perform the conversion on const_iterators that are actually
pointers.
Scott
--
"Effective STL" Seminar June 7-9 Portland, Oregon
Details at http://www.trekservices.com/estl/
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/03 Raw View
On Wed, 3 May 2000 01:15:11 CST, "Gillmer J. Derge"
<gderge1@nycap.rr.com> wrote:
> One obvious, but not necessarily good, solution would be for insert
> to check both before and after the hint. Then if, for example, the
> check for after was done second, both cases would be linear, but
> after would have a larger constant factor. Again, I'm not suggesting
> that this is actually a good idea.
I have heard it elsewhere with the thought that it might be. There
was a DR filed on this and it has been processed as NAD. I would
like to understand that and also consider QOI.
First, my desires as a user of the library. Iter insert (iter, value)
exists for sequences and associatives. For sequences it inserts before.
For associatives, it inserts in some correct place. For multis, there
could be many such places. I want associatives to insert before when
that is a valid place. It allows before begin through before end. If
it inserts after, before begin is impossible and the absurdity of after
end is allowed. If it inserts somewhere for multis, it prevents some
useful applications. Efficiency would also be nice.
Consider the following pseudocode for assoc(multi) where insert(value)
handles the bad hints.
if (size == 0)
insert(value)
else if (iter == end)
if (value >(>=) *back)
put it last
else
insert(value)
else if (value <(<=) *iter)
if (iter == begin)
put it first
else
pred = iter - 1
if (value >(>=) *pred)
put it between
else
insert(value)
else if (value >(>=) *iter) // needed to cover after, no test for multi
succ = iter + 1
if (succ != end && value <(<=) *succ)
put it between
else
insert(value)
else
insert(value)
A minor change allows an implementation to give me what I want and
still conform to the standard. The time cost is constant.
Is this QOI? I don't think so. It gives me what I want without
standardization. I can write non-portable programs that work well
on that implementation. The standard gives me nothing useful on this.
Is this a defect? I think it is, but I guess the alternative is
that there was no intention to make multi containers useful for
the things I want to do with them and there was no intention to
make iter insert(iter, value) consistent.
Efficiency: The standard inserter will use this function. The
standard specifies the operation of inserter so that it will work
properly for sequences. That breaks it for associatives.
set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(c, end());
This is an NlgN operation when it could be linear. It makes no
difference whether insert(iter, value) is before or after. In
either case, there will be a ++ on an iter to last. That is a
lgN climb up the tree to end.
Can inserter be specialized for associatives so that it will work?
The only reason that I can think of for the desire for after is
that insert(iter, value) could be used to implement
insert(iter, iter). This is an implementation detail and should
not be a factor in creating an unusable interface.
I guess this is a bit more than .02, but can someone please
explain the need for "after"? Care to mention the "some
implementers" mentioned in the NAD?
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 2000/05/03 Raw View
Mark Rodgers wrote:
>
> Gillmer J. Derge <gderge1@nycap.rr.com> wrote in message
>
> > I stand by my interpretation of the standard though. As you mentioned,
> SGI's
> > approach, while arguably better, is not what it's "supposed" to do.
>
> It's not just SGI's approach, its everyone's approach AFAICT. Consider
> that
>
> 1. What the standard specifies is not what is useful.
I'm not at all clear why that should be so. There's considerable
forward-backward symmetry in the definition of the associative
containers. I'm willing to believe I've missed something, but it's not
immediately obvious to me why insert-after should be any more or less
useful, nor more or less easily implementable, than insert-before.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/04 Raw View
On Wed, 3 May 2000 07:20:33 CST, "Mark Rodgers"
<mark.rodgers@cadenza.co.nz> wrote:
> Unfortunately, associative containters do not have an
> insert(pos,first,last).
Would it do any good? They have insert(first, last) which only gives
one lgN search for pos followed by N insertions. The test of pred or
succ of pos could also be lgN. Using copy(x.begin(), x.end(),
inserter(assoc, pos)) could easily be NlgN. Before and after would
have nothing to do with it. The insert should work well and the copy
has no chance.
Still trying to understand the need for "after".
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <andrewalex@hotmail.com>
Date: 2000/05/04 Raw View
Scott Meyers <smeyers@aristeia.com> wrote in message
news:MPG.1378adce1db2be509896ec@news.supernews.com...
> It seems to me that it would be a much smaller (and equally
effective)
> change to the standard to require some kind of conversion function
from
> const_iterator to iterator, possibly iterator member functions
(analogous
> to the base() member function for converting reverse_iterators to
> iterators) in conjunction with something in iterator_traits to make
it
> possible to perform the conversion on const_iterators that are
actually
> pointers.
Why not a simple template function at namespace std level? This way
you don't have to work hard to support pointers.
The thing would work like this:
namespace std
{
template <typename IterDest, class typename IterSrc>
IterDest iterator_const_cast(IterSrc iter);
template <typename T>
typename vector<T>::iterator
iterator_const_cast(vector<T>::const_iterator iter)
{
...
}
...
// A more elaborate version would use
iterator_traits<T>::value_type*
template <class T>
T* iterator_const_cast(const T* iter)
{
return const_cast<T*>(iter);
}
}
Andrei
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Dave Abrahams <abrahams@mediaone.net>
Date: 2000/05/04 Raw View
in article MPG.1378adce1db2be509896ec@news.supernews.com, Scott Meyers at
smeyers@aristeia.com wrote on 5/3/00 12:22 PM:
> It seems to me that it would be a much smaller (and equally effective)
> change to the standard to require some kind of conversion function from
> const_iterator to iterator, possibly iterator member functions (analogous
> to the base() member function for converting reverse_iterators to
> iterators) in conjunction with something in iterator_traits to make it
> possible to perform the conversion on const_iterators that are actually
> pointers.
While the change would be smaller, the resulting library interface would be
even bigger and more complicated than it already is. Since there's
absolutely no reason a non-const iterator should be required in order to
indicate an insertion position, adding a conversion function also makes
using the library needlessly cumbersome. Finally, the conversion function
you've proposed is essentially a const_cast in terms of its (lack of)
safety. Functionality that doesn't invoke undefined behavior should be
implementable without such a dangerous construct.
but-maybe-if-we-bring-in-cane-toads-they'll-eat-the-beetles-ly y'rs,
Dave
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: smeyers@aristeia.com (Scott Meyers)
Date: 2000/04/29 Raw View
Two STL Questions, both inspired by questions from the students in the
class I taught earlier this week (in case you think I make these up myself
:-}):
- If I have a multiset<Widget> mw and I insert a new widget w into it,
does the standard specify where in the range [mw.lower_bound(w),
mw.upper_bound(w)) the new copy of w will be inserted? My reading of
the standard says no, but it would not stun me if I missed something.
- Given a Container::const_iterator, is there a constant-time way to
create the corresponding Container::iterator? What I'm looking for is
the moral equivalent of a const_cast, but for iterators. The only
thing I could come up with was
Container c;
Container::const_iterator ci;
... // make ci point into c
Container::iterator i(c.begin());
advance(i, distance(Container::const_iterator(c.begin), ci));
The big problem here is that this is a linear-time operation unless I
have a random access iterator, and it's not unreasonable to want to
convert a list<Widget>::const_iterator to a list<Widget>::iterator in
constant time. Surely there's a way, no?
Thanks,
Scott
--
"Effective STL" Seminar June 7-9 Portland, Oregon
Details at http://www.trekservices.com/estl/
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Frans Meijer" <frans.meijer@xs4all.nl>
Date: 2000/04/30 Raw View
Scott Meyers <smeyers@aristeia.com> schreef in berichtnieuws
MPG.137375a793083c729896e9@news.supernews.com...
: Two STL Questions, both inspired by questions from the students
in the
: class I taught earlier this week (in case you think I make these
up myself
: :-}):
:
: - If I have a multiset<Widget> mw and I insert a new widget w
into it,
: does the standard specify where in the range
[mw.lower_bound(w),
: mw.upper_bound(w)) the new copy of w will be inserted? My
reading of
: the standard says no, but it would not stun me if I missed
something.
: [...]
Given that the STL implementations (I know) use red-black trees to
implement set I would guess that there is no such specification in
the standard. Red-black trees re-balance themselves after insert
and erase operations, which will likely change the order of
elements with equal keys. If the standard would require these to
remain in the 'insert' order all those implementations would be
violating that requirement.
--
X-Replace-Address
return this->is(my<opinion>(only));
For replies, remove underscores from kanga_roo@xs_4_all.nl
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/04/30 Raw View
On Sun, 30 Apr 2000 04:23:17 CST, "Frans Meijer"
<frans.meijer@xs4all.nl> wrote:
> Given that the STL implementations (I know) use red-black trees to
> implement set I would guess that there is no such specification in
> the standard. Red-black trees re-balance themselves after insert
> and erase operations, which will likely change the order of
> elements with equal keys. If the standard would require these to
> remain in the 'insert' order all those implementations would be
> violating that requirement.
The rebalancing of red-black trees does not involve changing the
linear in-order of the nodes. No reference to the data elements
is required to rebalance. It is simply color changes and
rotations which all preserve order.
The standard does not specify where a new item will be inserted
within the range of existing matches; however, it will stay
where it is inserted.
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Gillmer J. Derge" <gderge1@nycap.rr.com>
Date: 2000/05/01 Raw View
Scott Meyers wrote:
> - Given a Container::const_iterator, is there a constant-time way to
> create the corresponding Container::iterator? What I'm looking for is
> the moral equivalent of a const_cast, but for iterators. The only
> thing I could come up with was
>
> Container c;
> Container::const_iterator ci;
> ... // make ci point into c
> Container::iterator i(c.begin());
> advance(i, distance(Container::const_iterator(c.begin), ci));
>
> The big problem here is that this is a linear-time operation unless I
> have a random access iterator, and it's not unreasonable to want to
> convert a list<Widget>::const_iterator to a list<Widget>::iterator in
> constant time. Surely there's a way, no?
I don't think there is. The standard requires that an iterator can be
converted to a const_iterator but not the other way around (why?). Here's
another pseudo-solution.
Instead of using Container::const_iterator, use
const_iterator<Container::iterator> where const_iterator is an adapter,
similar in concept to reverse_iterator, that provides const semantics through
a non-const iterator. Then, as long as you define appropriate conversions
(which are now constant time), you can cast in both directions using
static_cast rather than const_cast. The adapter's implementation is fairly
straightforward, but if desired, I can post source code for my prototype
version.
It seems as though a container could reasonably be required to provide
iterator and const_iterator types that are interchangeable via casts. If
nothing else, the const_iterator could be implemented exactly as
reverse_iterator is -- through an adapter class like I described above. As
you've pointed out, the current situation causes iterators to be a somewhat
flawed generalization of pointers.
-----
Gillmer J. Derge
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Dave Abrahams <abrahams@mediaone.net>
Date: 2000/05/01 Raw View
in article 8eecg3$scm$1@news1.xs4all.nl, Frans Meijer at
frans.meijer@xs4all.nl wrote on 4/30/00 5:23 AM:
> Given that the STL implementations (I know) use red-black trees to
> implement set I would guess that there is no such specification in
> the standard. Red-black trees re-balance themselves after insert
> and erase operations, which will likely change the order of
> elements with equal keys. If the standard would require these to
> remain in the 'insert' order all those implementations would be
> violating that requirement.
Actually, the rebalancing code I've seen works without changing the order of
any elements. It manipulates the internal structure of the tree using a
series of transformations which don't change element order. This turns out
to be crucial for exception-safety: once the insert position for an element
is determined, and its tree node is allocated, the (single-element) insert
operation is guaranteed to succeed, since rebalancing doesn't require any
new comparisons.
To answer Scott's original questions:
> - If I have a multiset<Widget> mw and I insert a new widget w into it,
> does the standard specify where in the range [mw.lower_bound(w),
> mw.upper_bound(w)) the new copy of w will be inserted? My reading of
> the standard says no, but it would not stun me if I missed something.
You didn't miss anything, except perhaps that you can insert into a multiset
in amortized constant time provided you provide an iterator argument and the
insertion occurs just after the iterator. I consider this a rather weak
guarantee at best, though.
> - Given a Container::const_iterator, is there a constant-time way to
> create the corresponding Container::iterator? What I'm looking for is
> the moral equivalent of a const_cast, but for iterators. The only
> thing I could come up with was
>
> Container c;
> Container::const_iterator ci;
> ... // make ci point into c
> Container::iterator i(c.begin());
> advance(i, distance(Container::const_iterator(c.begin), ci));
>
> The big problem here is that this is a linear-time operation unless I
> have a random access iterator, and it's not unreasonable to want to
> convert a list<Widget>::const_iterator to a list<Widget>::iterator in
> constant time. Surely there's a way, no?
I don't think so. I can't think of a reason such a conversion would be
neccessary, unless it was to work around another problem in the library
specification.
Is it possible that this question was inspired by the same problem that
generated open library issue #180
<http://wwwold.dkuug.dk/JTC1/SC22/WG21/docs/lwg-active.html#180>?
-Dave
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: 2000/05/01 Raw View
On Mon, 1 May 2000 16:10:06 CST, Dave Abrahams <abrahams@mediaone.net>
wrote:
> To answer Scott's original questions:
>
> > - If I have a multiset<Widget> mw and I insert a new widget w into it,
> > does the standard specify where in the range [mw.lower_bound(w),
> > mw.upper_bound(w)) the new copy of w will be inserted? My reading of
> > the standard says no, but it would not stun me if I missed something.
>
> You didn't miss anything, except perhaps that you can insert into a
> multiset in amortized constant time provided you provide an iterator
> argument and the insertion occurs just after the iterator. I consider
> this a rather weak guarantee at best, though.
Surely you jest. Insert *after* is absurd. Insert is before, append
is after. The SGI implementation honors insert before and does give
amortized constant time. The standard offers nothing. A common use
is inserter(container, container.end()). Now how do you "insert"
after end?
John
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Dave Abrahams <abrahams@mediaone.net>
Date: 2000/05/01 Raw View
in article 390d619a.3791304@news.csrlink.net, John Potter at
jpotter@falcon.lhup.edu wrote on 5/2/00 12:17 AM:
>> You didn't miss anything, except perhaps that you can insert into a
>> multiset in amortized constant time provided you provide an iterator
>> argument and the insertion occurs just after the iterator. I consider
>> this a rather weak guarantee at best, though.
>
> Surely you jest. Insert *after* is absurd. Insert is before, append
> is after. The SGI implementation honors insert before and does give
> amortized constant time. The standard offers nothing.
Table 69--Associative container requirements
----------------------------------------------------------------------------
expression return type assertion/note complexity
pre/post-condition
---------------------------------------------------------------------------
a.insert(p,t) iterator inserts t if and only if there is logarithmic in
no element with key equivalent to general, but amor-
the key of t in containers with tized constant if
unique keys; always inserts t in t is inserted
containers with equivalent keys. right after p.
always returns the iterator point-
ing to the element with key equiva-
lent to the key of t. iterator p
is a hint pointing to where the in-
sert should start to search.
> A common use
> is inserter(container, container.end()). Now how do you "insert"
> after end?
I don't know. Maybe this is a defect.
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]