Joe Gottman <joegottman@worldnet.att.net> wrote:

:    How about using the insertion with hint?  If I have a multiset<String,
: CaseInsensitiveCompare>
: that contains elements "AA", "Aa", and "aA", can I use the insertion with
: hint to insert "aa" anywhere in the multiset that I want it?

Sorry for the previous, I missread the results.  Egcs does insert before
the hint except when the hint is begin().  It treats begin() and end()
the same.  My instalation is a year old and this bug may have been
fixed.

Everything except the standard now agrees.

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              ]

James Kuyper <kuyper@wizard.net> wrote:

: Joe Gottman wrote:
: >
: >    How about using the insertion with hint?  If I have a multiset<String,
: > CaseInsensitiveCompare>
: > that contains elements "AA", "Aa", and "aA", can I use the insertion with
: > hint to insert "aa" anywhere in the multiset that I want it?

: An implementation could choose to implement a hint that way, and offhand
: I can't think of any reason why it shouldn't, but it's not required to
: do so. The hint is provided to speed up the search, not to specify the
: insert location.

With all of the things I've found that the standard says without
saying them lately, I'm a bit skeptical.

There is a complexity requirement for this operation which requires
that if the item is inserted right before (typo in standard says
after, but insert is before) the hint of amortized constant time.
It is possible to devise a test which forces insertions to be right
before the hint and determines whether the time is amortized constant
or logarithmic.

A conformant implementation can not use
   iter insert (iter p, T v) { return insert(v); }
because insert(T) is logarithmic.

The first validity check on p is ! (*p < v).

Either p == begin() and it is valid or it has a predecessor.
Finding pred is -- which is amortized constant time.  The
second validity check on p is ! (v < *pred).

Since this is a balanced binary search tree (another thing the
standard says without saying it), either p has no left child
or pred has no right child.  The insertion point is determined
in amortized constant time and rebalancing is also amortized
constant time.

A nice simple algorithm to use for set.

I guess that a conforming implementation could test *p == v
and use insert(v) for multiset which it designed to insert
after matches to bypass this requirement.

The standard may not say that insertion will take place at the
point of a valid hint, but it does make enough requirements
that only a malicious implementation would do otherwise.

I think it is a shame that this function is required but the
requirement that it do the right thing is not quite there.

I will assume that it was an oversight not an intent.  I think
that the intent was that it act exactly like the same function
for sequences with the added requirement that an invalid hint
will be ignored and the insertion will then be in the correct
place.

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              ]

John Potter wrote:
>
> James Kuyper <kuyper@wizard.net> wrote:
>
> : Joe Gottman wrote:
> : >
> : >    How about using the insertion with hint?  If I have a multiset<String,
> : > CaseInsensitiveCompare>
> : > that contains elements "AA", "Aa", and "aA", can I use the insertion with
> : > hint to insert "aa" anywhere in the multiset that I want it?
>
> : An implementation could choose to implement a hint that way, and offhand
> : I can't think of any reason why it shouldn't, but it's not required to
> : do so. The hint is provided to speed up the search, not to specify the
> : insert location.
....
> It is possible to devise a test which forces insertions to be right
> before the hint and determines whether the time is amortized constant
> or logarithmic.

How could you force such inserts? When all keys are unique, you can
create a situation where the inserted element must be inserted just
before the hint. The minute that you have duplicate keys, either for the
hint or for the inserted element, you no longer guarantee that.
Therefore you can't create a situation with guaranteed amortized
constant time.

> A conformant implementation can not use
>    iter insert (iter p, T v) { return insert(v); }
> because insert(T) is logarithmic.

Agreed.

> The first validity check on p is ! (*p < v).
>
> Either p == begin() and it is valid or it has a predecessor.
> Finding pred is -- which is amortized constant time.  The
> second validity check on p is ! (v < *pred).
>
> Since this is a balanced binary search tree (another thing the
> standard says without saying it), either p has no left child

I doubt that. Please explain. What in the standard itself makes that
specific a requirement on the implementation? Don't argue that it's the
most efficient way to meet some requirement; the standard doesn't
require efficiency - that's a QoI issue.

Having found an equal key, insert() is free to insert the new element
either before or after it.

....
> The standard may not say that insertion will take place at the
> point of a valid hint, but it does make enough requirements
> that only a malicious implementation would do otherwise.

As I said, I can't think of any reason why it wouldn't.

> I think it is a shame that this function is required but the
> requirement that it do the right thing is not quite there.

That's nothing unusual; most of the standard is like that. There's
nothing that says that an implementation can't take 2 million years to
add two integers. That's a QoI issue.
---
[ 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              ]

James Kuyper <kuyper@wizard.net> wrote:

: John Potter wrote:

: > Since this is a balanced binary search tree (another thing the
: > standard says without saying it), either p has no left child

: I doubt that. Please explain. What in the standard itself makes that
: specific a requirement on the implementation? Don't argue that it's the
: most efficient way to meet some requirement; the standard doesn't
: require efficiency - that's a QoI issue.

No, it places complexity requirements on operations and validity of
existing iterators/pointers/references.  All of them can be met
with a balanced binary search tree.  I'm not sure that they can be
met with an AVL tree.  I would need to check the amortized const
time of rebalance after insertion.  We played this game a few months
ago and the conclusion was no counter example.  If you have one, I
would love to hear about it.

: Having found an equal key, insert() is free to insert the new element
: either before or after it.

Yep, that's a bug.

: > I think it is a shame that this function is required but the
: > requirement that it do the right thing is not quite there.

: That's nothing unusual; most of the standard is like that. There's
: nothing that says that an implementation can't take 2 million years to
: add two integers. That's a QoI issue.

I don't see it that way.  Using the hint is a correctness of the
container issue.  We are not talking about how well programs work
but about the ability to write correct programs.  In an associative
multi-container a group of elements with equivalent keys is a
sequence.  It is clear that insert with hint was intended to allow
treating it as such and not just as an efficiency boost.  The code
I have looked at treats it as such and with one exception gets it
right.  The exception is a feature of the code allowed by a bug in
the standard.  I know that it is a simple error in the code and I
may not have been the only one to stumble across it.  Of course,
the code I have had about three years of testing without anyone
noticing.

Yes, this is all opinion.  You're right, the standard does not
permit treating an equivalence subset as a sequence.

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              ]

Sigbjoern Revheim wrote:
>
> If I have the elements 1,2,2,3 in a mutiset<int> and then insert 2, it
> will be placed right before 3. Is this implementation dependent
> behaviour and can I risk that in some other implementation it will ble
> placed right after 1?

How could you tell? Why would it matter? A 2 is a 2 is a 2.

I presume what you're actually thinking about is multiset<Key,Compare>,
where Compare is something that defines as equivalent Key objects that
can actually be distinguished. The answer is: yes, the insertion point
is implementation dependent. The only thing that the standard guarantees
is that iteration from begin() to end() will be in non-decreasing order,
as defined by the Compare object.
---
[ 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              ]

James Kuyper wrote:
>
> Sigbjoern Revheim wrote:
> >
> > If I have the elements 1,2,2,3 in a mutiset<int> and then insert 2, it
> > will be placed right before 3. Is this implementation dependent
> > behaviour and can I risk that in some other implementation it will ble
> > placed right after 1?
>
> How could you tell? Why would it matter? A 2 is a 2 is a 2.

An rvalue 2 is an rvalue 2.

An lvalue 2 has an address, which may be different from
the address of another lvalue 2. The following program
prints ``insertion at end'' with the SGI STL:

#include <set>
#include <iostream>

int main ()
{
    typedef std::multiset<int> cont;
    cont s;

    cont::iterator it = s.insert (2);
    s.insert (2);
    if (++it == s.end())
 std::cout << "insertion at beginning\n";
    else
 std::cout << "insertion at end\n";
}

--

Valentin Bonnard


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

James Kuyper wrote:

> I presume what you're actually thinking about is multiset<Key,Compare>,
> where Compare is something that defines as equivalent Key objects that
> can actually be distinguished.

Yes, thats it. (Just wanted to give a simple example by using int).
What I actually do are inserting (non-overlapping) selections into a multiset
and sort them by startvalue. To check if a value is selected I insert it into
the multiset  as a new selection consisting of only that value. The new
inserted selection can have the same startvalue or a grater startvalue than
the selection it can be in. If I knew the insertion order was as I described
in my first message, then I only had to check the iterator position at the
left.
(I erase the new inserted selection after checking for the value).

> The answer is: yes, the insertion point is implementation dependent.

That was what I  was afraid of.

Thank you for your answer.
---
[ 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              ]

James Kuyper wrote:

> Sigbjoern Revheim wrote:
> >
> > If I have the elements 1,2,2,3 in a mutiset<int> and then insert 2, it
> > will be placed right before 3. Is this implementation dependent
> > behaviour and can I risk that in some other implementation it will ble
> > placed right after 1?
>
> How could you tell? Why would it matter? A 2 is a 2 is a 2.
>
> I presume what you're actually thinking about is multiset<Key,Compare>,
> where Compare is something that defines as equivalent Key objects that
> can actually be distinguished. The answer is: yes, the insertion point
> is implementation dependent. The only thing that the standard guarantees
> is that iteration from begin() to end() will be in non-decreasing order,
> as defined by the Compare object.
>

   How about using the insertion with hint?  If I have a multiset<String,
CaseInsensitiveCompare>
that contains elements "AA", "Aa", and "aA", can I use the insertion with
hint to insert "aa" anywhere in the multiset that I want it?

--
Joe Gottman
joegottman@worldnet.att.net

The philosophy of C++: "Nothing is false; everything else is true."




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

Joe Gottman wrote:
>
> James Kuyper wrote:
>
> > Sigbjoern Revheim wrote:
> > >
> > > If I have the elements 1,2,2,3 in a mutiset<int> and then insert 2, it
> > > will be placed right before 3. Is this implementation dependent
> > > behaviour and can I risk that in some other implementation it will ble
> > > placed right after 1?
> >
> > How could you tell? Why would it matter? A 2 is a 2 is a 2.
> >
> > I presume what you're actually thinking about is multiset<Key,Compare>,
> > where Compare is something that defines as equivalent Key objects that
> > can actually be distinguished. The answer is: yes, the insertion point
> > is implementation dependent. The only thing that the standard guarantees
> > is that iteration from begin() to end() will be in non-decreasing order,
> > as defined by the Compare object.
> >
>
>    How about using the insertion with hint?  If I have a multiset<String,
> CaseInsensitiveCompare>
> that contains elements "AA", "Aa", and "aA", can I use the insertion with
> hint to insert "aa" anywhere in the multiset that I want it?

An implementation could choose to implement a hint that way, and offhand
I can't think of any reason why it shouldn't, but it's not required to
do so. The hint is provided to speed up the search, not to specify the
insert location.
---
[ 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              ]

Joe Gottman <joegottman@worldnet.att.net> wrote:

:    How about using the insertion with hint?  If I have a multiset<String,
: CaseInsensitiveCompare>
: that contains elements "AA", "Aa", and "aA", can I use the insertion with
: hint to insert "aa" anywhere in the multiset that I want it?

Sounds reasonable.  I tried it with egcs.  The answer is almost.  It
seems a bit funny that "insert" happened after the hint not before.
However, the standard says that the complexity is amortized constant
time if the insertion happens right after the hint.  Matt's book says
right before the hint.  The standard says that the hint is where the
search should start which seems to exclude end.  Matt says the hint
is non-singular which includes end.  Quite sure which is law, not sure
which is right. <g>  I don't think that the complexity could be met
without taking the hint seriously.

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              ]

If I have the elements 1,2,2,3 in a mutiset<int> and then insert 2, it
will be placed right before 3. Is this implementation dependent
behaviour and can I risk that in some other implementation it will ble
placed right after 1?



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