John Potter wrote:
>
> On Thu,  3 Aug 2000 18:09:04 GMT, Craig Powers <enigma@hal-pc.org>
> wrote:
>
> > John Potter wrote:

[...]

> > STLPort 4.0b8 results, with my modifications to _tree.c:
> > insert(value)
> > 0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
> > 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

[...]

> Let's just say that they are what I would like.  Without checking, I
> think the insert(value) could be improved.  It should not take two
> compares to insert the second item.  Maybe in a set, but not in a
> multiset.

That would be because I only worked on improving insert with hint.
There is an obvious opportunity for optimization on insert without
hint for equal containers which I just implemented, with these results:

insert(value)
0 1 3 5 8 11 15 19 23 27 32 37 42 47 53 59 65 71 77 83
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19


Essentially, there was an extra compare at each step past the first.

I'll see if I can make a similar improvement to insert_unique.  Once
I've tested this fully (to verify to the best of my ability that there
were no unintended consequences), I will also forward the updated
_tree.c to Boris for possible inclusion in the next version of STLPort.

--
Craig Powers
cpowers@lynx.neu.edu
enigma@hal-pc.org

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

On Thu,  3 Aug 2000 18:09:04 GMT, Craig Powers <enigma@hal-pc.org>
wrote:

> John Potter wrote:
>
> [...]
>
> > The standard is totally useless for equal containers since it has no
> > requirement to honor the hint.

> STLPort 4.0b8 results, with my modifications to _tree.c:
> insert(value)
> 0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(end, value)
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(previous_insert, value)
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
> insert(begin, value)
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
>
>
> Obviously, the comparison numbers look a -lot- better than the other
> two implementations, and for the second pair of tests, the resulting
> sequence is reversed.  Are the results as they should be?

Let's just say that they are what I would like.  Without checking, I
think the insert(value) could be improved.  It should not take two
compares to insert the second item.  Maybe in a set, but not in a
multiset.

> > Note that the results expected were 19...0, but the only non-conformance
> > was in taking too long to place the values in the "wrong" place.  Fixing
> > the STL-port will not help, the standard is broken.  The only question
> > is whether it is intentional or a defect.
>
> I'm aware of the concern about the standard requirement that insert
> immediately after hint occur in constant time (or amortized constant
> time, don't recall which and don't have the standard to look it up)
> is broken and that the requirement should be before.

It would be constant number of compares, but amortized constant time
because of rebalancing needed on some inserts.

> Is there
> another issue that your test is showing here?  i.e., is the reverse
> order either (required by the standard but not desired by the user)
> or (contradicted by the standard, it should be in forward order
> instead)?

The standard says nothing about where equal items are placed.

For insert(value), that is correct, IMO.  This also argees with find
which may return an iterator to any one of a group of equal items.
Lower_bound can be used to find the first, upper_bound for the last,
and the user can control things.

For insert(pos, value), the only requirement is to rapidly place the
item after (may become before) the hint IF the implementation decides
to put it there.  There is no requirement to honor the hint.

I can not write portable code which depends upon insert(pos, value)
placing the item before (or after) pos.  This is a matter of program
correctness not efficiency.

When things like this happen, the standard usually says that it is
unspecified.  Maybe the semantics of insert(pos, value) should read

   Places value in an unspecified position consistent with the
   compare function.  If that position is immediately before pos,
   the operation will be amortized constant time otherwise it will
   be log(size()).

That is, of course, not what I want, but it at least says that it
was intentional not an oversight.  I think the intent was for it
to be the same as for sequences with the added condition that if the
hint is not consistent with compare, it will be ignored and treated
as insert(value).

Anyway, there is an issue up again.  Since the previous NAD, at least
one implementation has changed to what I think users want.  The
committee has many things to consider and this one may not be of high
enough priority to make the upcoming TC.  Time will tell.

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:

[...]

> The standard is totally useless for equal containers since it has no
> requirement to honor the hint.  Here are some results of another
> test program for multiset.  The insert(value) is just there to show
> what Nlog(size()) looks like.  The first line gives the number of
> compares after each insert and the second is the final container
> contents.

> Gcc 2.95.2 shipped libstdc++(SGI).
> insert(value)
> 0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(end, value)
> 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(previous_insert, value)
> 0 3 5 8 10 13 15 18 20 23 25 28 30 33 35 38 40 43 45 48
> 0 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
> insert(begin, value)
> 0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

> Bc++5.02 shipped RW
> insert(value)
> 0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(end, value)
> 0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(previous_insert, value)
> 0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
> insert(begin, value)
> 0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
> 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

STLPort 4.0b8 results, with my modifications to _tree.c:
insert(value)
0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(end, value)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(previous_insert, value)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
insert(begin, value)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0


Obviously, the comparison numbers look a -lot- better than the other
two implementations, and for the second pair of tests, the resulting
sequence is reversed.  Are the results as they should be?

> For end, there is no way to insert after and both implementations
> conform.  For previous_insert, SGI did not insert after (except a
> minor bug at begin which may still be in your STL-port) and conforms
> with fairly nice values which are not required.  The test was of
> course designed to show that the broken RW implementation which did
> insert after does not conform.  For begin, they both do the "wrong"
> thing and conform.

> Note that the results expected were 19...0, but the only non-conformance
> was in taking too long to place the values in the "wrong" place.  Fixing
> the STL-port will not help, the standard is broken.  The only question
> is whether it is intentional or a defect.

I'm aware of the concern about the standard requirement that insert
immediately after hint occur in constant time (or amortized constant
time, don't recall which and don't have the standard to look it up)
is broken and that the requirement should be before.  Is there
another issue that your test is showing here?  i.e., is the reverse
order either (required by the standard but not desired by the user)
or (contradicted by the standard, it should be in forward order
instead)?

--
Craig Powers
cpowers@lynx.neu.edu
enigma@hal-pc.org

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

On Tue, 11 Jul 2000 08:59:12 CST, Craig Powers <enigma@hal-pc.org>
wrote:

> Stephen Howe wrote:
> >
> > Craig Powers <enigma@hal-pc.org> wrote in message
> > news:395414DE.4366D75E@hal-pc.org...
> >
> > > STLPort plus MSVC++ 5.0 produces the same results, which seems right
> > > because STLPort is based on SGI.  After knocking the source around
> > > a bit, I was able to obtain numbers that match Howard's.
> >
> > I would suggest sharing your code modifcations with Boris Fomitchev at
> > www.stlport.org if you have not already.
>
> I'm in the process of doing so...
>
> Pursuant to that, a question -- does the standard impose the same
> requirements on multiset/multimap with regard to complexity of
> insert as it does on set/map?  i.e., should the results for the test
> here be the same for those containers?  (aside from the fact that
> dup compare will insert, not return an iterator pointing at that
> element)  If so, I'll propogate my changes to insert_equal with hint.

Well, yes, but so what?  Your code and Howard's both effectively do
what users want and, as a consolation prize, conform.  With no
requirement in the standard to do what users want, it could conform
with

if (pos != end() && *pos < value && (++ pos == end() || value < *pos))
   put_it_there;
else
   insert(value);

The standard is totally useless for equal containers since it has no
requirement to honor the hint.  Here are some results of another
test program for multiset.  The insert(value) is just there to show
what Nlog(size()) looks like.  The first line gives the number of
compares after each insert and the second is the final container
contents.

Gcc 2.95.2 shipped libstdc++(SGI).
insert(value)
0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(end, value)
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(previous_insert, value)
0 3 5 8 10 13 15 18 20 23 25 28 30 33 35 38 40 43 45 48
0 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
insert(begin, value)
0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Bc++5.02 shipped RW
insert(value)
0 2 5 8 12 16 21 26 31 36 42 48 54 60 67 74 81 88 95 102
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(end, value)
0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(previous_insert, value)
0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
insert(begin, value)
0 3 7 11 16 21 27 33 39 45 52 59 66 73 81 89 97 105 113 121
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

For end, there is no way to insert after and both implementations
conform.  For previous_insert, SGI did not insert after (except a
minor bug at begin which may still be in your STL-port) and conforms
with fairly nice values which are not required.  The test was of
course designed to show that the broken RW implementation which did
insert after does not conform.  For begin, they both do the "wrong"
thing and conform.

Note that the results expected were 19...0, but the only non-conformance
was in taking too long to place the values in the "wrong" place.  Fixing
the STL-port will not help, the standard is broken.  The only question
is whether it is intentional or a defect.

John

#include <iostream>
#include <set>
#include <functional>
#include <algorithm>
#include <iterator>

using namespace std;

struct MeteredCompare : std::binary_function<int, int, bool> {
   static int count;
   bool operator()(int lhs, int rhs) const { ++ count; return false; }
   };
int MeteredCompare::count;
void test_complexity () {
   multiset<int, MeteredCompare> s;
   multiset<int, MeteredCompare>::iterator si;
   int x;
   MeteredCompare::count = 0;
   cout << "insert(value)\n";
   for (x = 0; x < 20; ++ x) {
   s.insert(x);
      cout << MeteredCompare::count << ' ';
      }
   cout << endl;
   copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
   cout << endl;
   s.erase(s.begin(), s.end());
   MeteredCompare::count = 0;
   cout << "insert(end, value)\n";
   for (x = 0; x < 20; ++ x) {
      s.insert(s.end(), x);
      cout << MeteredCompare::count << ' ';
      }
   cout << endl;
   copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
   cout << endl;
   s.erase(s.begin(), s.end());
   MeteredCompare::count = 0;
   cout << "insert(previous_insert, value)\n";
   for (si = s.end(), x = 0; x < 20; ++ x) {
      si = s.insert(si, x);
      cout << MeteredCompare::count << ' ';
      }
   cout << endl;
   copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
   cout << endl;
   s.erase(s.begin(), s.end());
   MeteredCompare::count = 0;
   cout << "insert(begin, value)\n";
   for (x = 0; x < 20; ++ x) {
      s.insert(s.begin(), x);
      cout << MeteredCompare::count << ' ';
      }
   cout << endl;
   copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
   cout << endl;
   s.erase(s.begin(), s.end());
   }
int main () {
   test_complexity();
   cin.get();
   }

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

Stephen Howe wrote:
>
> Craig Powers <enigma@hal-pc.org> wrote in message
> news:395414DE.4366D75E@hal-pc.org...
>
> > STLPort plus MSVC++ 5.0 produces the same results, which seems right
> > because STLPort is based on SGI.  After knocking the source around
> > a bit, I was able to obtain numbers that match Howard's.
>
> I would suggest sharing your code modifcations with Boris Fomitchev at
> www.stlport.org if you have not already.

I'm in the process of doing so...

Pursuant to that, a question -- does the standard impose the same
requirements on multiset/multimap with regard to complexity of
insert as it does on set/map?  i.e., should the results for the test
here be the same for those containers?  (aside from the fact that
dup compare will insert, not return an iterator pointing at that
element)  If so, I'll propogate my changes to insert_equal with hint.

TIA

--
Craig Powers
cpowers@lynx.neu.edu
enigma@hal-pc.org

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

Craig Powers <enigma@hal-pc.org> writes:

[snip]
> Pursuant to that, a question -- does the standard impose the same
> requirements on multiset/multimap with regard to complexity of
> insert as it does on set/map?  i.e., should the results for the test
> here be the same for those containers?  (aside from the fact that
> dup compare will insert, not return an iterator pointing at that
> element)  If so, I'll propogate my changes to insert_equal with hint.
>
[snip]

Yes.

I believe the requirement to perform a.insert(p,t) in amortized
  constant time when t is inserted right after p applies to all
  associative containers, including multiset and multimap.

I am looking at 23.1.2, table 69.

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

[...]

> Note that the first line assures that the test will fail causing an
> insert(value) call giving Lg n time.  This was copied from the RW
> library tree file shipped with Borland 5.02, but I'm sure that it
> has survived in others.  The whole approach taken makes it very
> difficult to handle multiset.  The SGI library moved from a single
> insert function to a pair insert_equal and insert_unique to solve
> the problem.  However, there are still some heldover inefficiencies.

[...]

Assuming that your example should have exercised both facets of the
library, it's broken.  I profiled STLPort (which gives the same results
as SGI) using your program, and both insert_equal do not get hit
(or even instantiated, for that matter); all of the action is in
insert_unique.

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

> sgi::set shipped with gcc-2.95.2 libstdc++
>
> Odd compares = 98
> Even before compares = 123
> Even after compares = 489
> Even dup compares = 491
> Odd compares = 198
> Even before compares = 248
> Even after compares = 1098
> Even dup compares = 1088
>
> Slightly larger success numbers due to some possibly redundant tests
> left over from the HP implementation.  It is also non-conformant, but
> agrees with my opinion that after is nonsense.  If enough people want
> the good dup results, I'm sure that SGI would listen.

STLPort plus MSVC++ 5.0 produces the same results, which seems right
because STLPort is based on SGI.  After knocking the source around
a bit, I was able to obtain numbers that match Howard's.

I'm a decent coder, but I don't know how efficient the code I added is
and I don't know for sure that it doesn't kill something besides Set
that uses the STLPort RBTree.  That said, if anyone wants to know how
to modify the stl_tree.c to obtain the same results, I'd be happy to
oblige.

Conclusions:
- Extra odd compares: addition of an insert_after function or
modification of the insert function in its RBtree will fix this.
(When hint is end(), after checking to make sure v is after the last
element in insert_unequal, it also performs a comparison in the insert
to see if v is before the specified insertion point in insert, which
can't be the case because it was already verified as after.

- Extra even-before compares: On half of these (where the right node
off of the node before the hint is zero), it does an extra comparison
for roughly the same reason as for odd compares -- it does the inverse
of a comparison that already evaluated to true.  The fix for extra
odd comparisons applies here.

- Extra after-compares: Addition of a check for immediately after
(which, as noted, is required by the standard but in low demand)
fixes this.

- Extra dup-compares: Since it's already checking immediately before
and immediately after, the duplicate check comes for free.

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

Craig Powers <enigma@hal-pc.org> spake thusly:

: John Potter wrote:

: > Note that the first line assures that the test will fail causing an
: > insert(value) call giving Lg n time.  This was copied from the RW
: > library tree file shipped with Borland 5.02, but I'm sure that it
: > has survived in others.  The whole approach taken makes it very
: > difficult to handle multiset.  The SGI library moved from a single
: > insert function to a pair insert_equal and insert_unique to solve
: > the problem.  However, there are still some heldover inefficiencies.
:
: [...]
:
: Assuming that your example should have exercised both facets of the
: library, it's broken.  I profiled STLPort (which gives the same results
: as SGI) using your program, and both insert_equal do not get hit
: (or even instantiated, for that matter); all of the action is in
: insert_unique.

Umm, never mind.  I figured out what was meant about five minutes
later... sorry to have bothered y'all...


--
 Craig Powers                   NU ChE class of '98
 cpowers@lynx.dac.neu.edu       http://lynx.neu.edu/home/httpd/c/cpowers
 enigma@hal-pc.org              http://www.hal-pc.org/~enigma

"Good..bad....I'm the guy with the gun." -- "Ash" in *Army of Darkness*

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

Craig Powers <enigma@hal-pc.org> wrote in message
news:395414DE.4366D75E@hal-pc.org...

> STLPort plus MSVC++ 5.0 produces the same results, which seems right
> because STLPort is based on SGI.  After knocking the source around
> a bit, I was able to obtain numbers that match Howard's.

I would suggest sharing your code modifcations with Boris Fomitchev at
www.stlport.org if you have not already.

Stephen Howe



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 10 Jun 2000 22:59:10 CST, John Potter wrote:
> that it will for equal containers.  Having found two libraries which
> make no attempt to test for this, I don't see a change coming.  The
> fact that they also fail to insert in unique containers in amortized
> constant time with a valid hint will likely continue without complaint.

In the interest of drawing shame where shame should be drawn, please identify
the libraries.

Thanks,

Scott

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

On Tue, 20 Jun 2000 22:19:40 CST, smeyers@aristeia.com (Scott Meyers)
wrote:

> On Sat, 10 Jun 2000 22:59:10 CST, John Potter wrote:
> > that it will for equal containers.  Having found two libraries which
> > make no attempt to test for this, I don't see a change coming.  The
> > fact that they also fail to insert in unique containers in amortized
> > constant time with a valid hint will likely continue without complaint.
>
> In the interest of drawing shame where shame should be drawn, please
> identify the libraries.

In the interest of being honest, it is a shame that Lee did not get a
chance to produce good code for the original HP release.  I speculate
that under time pressure the following code was generated to patch a
failing algorithm.

        iterator before = --position;
        if (key_compare(key(before.node), KeyOfValue()(v))
            && key_compare(KeyOfValue()(v), key(position.node)))

Note that the first line assures that the test will fail causing an
insert(value) call giving Lg n time.  This was copied from the RW
library tree file shipped with Borland 5.02, but I'm sure that it
has survived in others.  The whole approach taken makes it very
difficult to handle multiset.  The SGI library moved from a single
insert function to a pair insert_equal and insert_unique to solve
the problem.  However, there are still some heldover inefficiencies.

If there is any shame due, it belongs to the users who do not know
that their library is broken and have not complained.  The algorithm
works and slowly inserts the item in the correct place.  There is
also some shame due to the committee for assuring that an item
inserted after the hint will be fast when nobody wants to insert
after the hint.

Here are some results of a simple test program (included below) to
test your libraries.  It does insert(end,odd) followed by
insert(validhint,even).  It uses both before and after tests and a
qoi test for duplicate hint.  The tests are repeated for 100 and
200 items to see the groth rate.

boost::vector_set

Odd compares = 49
Even before compares = 99
Even after compares = 457
Even dup compares = 99
Odd compares = 99
Even before compares = 199
Even after compares = 1025
Even dup compares = 199

It was a design choice to ignore the standard and take a hint of
insert before.  Note that doubling the size doubles the compares
when the hint is accepted.  Note also the more than doubling when
the hint is not taken.  This is non-conformant, but I wrote it
that way on purpose.  The low value for dup is a qoi issue only.

sgi::set shipped with gcc-2.95.2 libstdc++

Odd compares = 98
Even before compares = 123
Even after compares = 489
Even dup compares = 491
Odd compares = 198
Even before compares = 248
Even after compares = 1098
Even dup compares = 1088

Slightly larger success numbers due to some possibly redundant tests
left over from the HP implementation.  It is also non-conformant, but
agrees with my opinion that after is nonsense.  If enough people want
the good dup results, I'm sure that SGI would listen.

bc5.02-rw::set

Odd compares = 98
Even before compares = 491
Even after compares = 489
Even dup compares = 491
Odd compares = 198
Even before compares = 1100
Even after compares = 1098
Even dup compares = 1088

Not only non-conformant, but broken as noted above.  Interesting that
insert(end, value) is the only thing which works, but couldn't possibly
work with insert after.

I have not run this test with vc++/dw, but partial results of this
and other tests lead me to believe that the shipped library is also
broken.

If you care about this little piece of the standard library, run the
tests and bug your vendor to fix their code and the committee to fix
the standard; otherwise, remain silent.  You might even post the
results here.

I expect that Howard will post the excelent results that I think
CW will produce.  No undefined behavior this time. :)

John

#include <iostream>
#include <set>
#include <functional>

using namespace std;

struct MeteredCompare : binary_function<int, int, bool> {
    static int count;
    bool operator()(int lhs, int rhs) const { ++ count; return lhs <
rhs; }
    };
int MeteredCompare::count;
void test_complexity () {
    for (int size = 100; size <= 200; size += 100) {
        set<int, MeteredCompare> s;
        set<int, MeteredCompare>::iterator si;
        int x;
        MeteredCompare::count = 0;
        for (x = 1; x < size; x += 2)
            s.insert(s.end(), x);
        cout << "Odd compares = " << MeteredCompare::count
                << endl;
        MeteredCompare::count = 0;
        for (x = 0, si = s.begin(); x < size; x += 2, ++ si, ++ si)
            si = s.insert(si, x);
        cout << "Even before compares = " << MeteredCompare::count
                << endl;
        s.clear();
        for (x = 1; x < size; x += 2)
            s.insert(s.end(), x);
        MeteredCompare::count = 0;
        for (x = 2, si = s.begin(); x < size; x += 2, ++ si)
            si = s.insert(si, x);
        cout << "Even after compares = " << MeteredCompare::count
                << endl;
        MeteredCompare::count = 0;
        for (x = 0, si = s.begin(); x < size; x += 2, ++ si, ++ si)
            si = s.insert(si, x);
        cout << "Even dup compares = " << MeteredCompare::count
                << endl;
        }
    }
int main () {
    test_complexity();
    }


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

In article <39518fe0.19485159@news.csrlink.net>,
jpotter@falcon.lhup.edu says...

[ ... ]

> sgi::set shipped with gcc-2.95.2 libstdc++
>
> Odd compares = 98
> Even before compares = 123
> Even after compares = 489
> Even dup compares = 491
> Odd compares = 198
> Even before compares = 248
> Even after compares = 1098
> Even dup compares = 1088

[ ... ]

FWIW, VC++ 6.0 SP3 gives results identical to those above.

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

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

I ran the same test on the latest commercially available version of
the Dinkumware libraries for Visual C++.  I am happy to report that
they have improved to the following:

Odd compares = 49
Even before compares = 99
Even after compares = 440
Even dup compares = 491
Odd compares = 99
Even before compares = 199
Even after compares = 999
Even dup compares = 1088


"Jerry Coffin" <jcoffin@taeus.com> wrote in message
news:MPG.13bbe9172a3f957198998c@news.mindspring.com...
> In article <39518fe0.19485159@news.csrlink.net>,
> jpotter@falcon.lhup.edu says...
>
> [ ... ]
>
> > sgi::set shipped with gcc-2.95.2 libstdc++
> >
> > Odd compares = 98
> > Even before compares = 123
> > Even after compares = 489
> > Even dup compares = 491
> > Odd compares = 198
> > Even before compares = 248
> > Even after compares = 1098
> > Even dup compares = 1088
>
> [ ... ]
>
> FWIW, VC++ 6.0 SP3 gives results identical to those above.
>
> --
>     Later,
>     Jerry.
>
> The universe is a figment of its own imagination.
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting
with ]
> [ your news-reader.  If that fails, use
lto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before
             ]
> [ FAQ:
y.sgi.com/austern_mti/std-c++/faq.html              ]
>
>

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

In article <39518fe0.19485159@news.csrlink.net>, jpotter@falcon.lhup.edu
(John Potter) wrote:

| I expect that Howard will post the excelent results that I think
| CW will produce.  No undefined behavior this time. :)

Metrowerks CodeWarrior 6.0 beta (might be the same for 5.3, haven't
checked yet):

Odd compares = 49
Even before compares = 99
Even after compares = 147
Even dup compares = 99
Odd compares = 99
Even before compares = 199
Even after compares = 297
Even dup compares = 199

I haven't yet looked at the code to see why the "Even after compares"
differs from the boost::vector_set results.

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter <jpotter@falcon.lhup.edu> writes:

[ ... ]

: bc5.02-rw::set

: Odd compares = 98
: Even before compares = 491
: Even after compares = 489
: Even dup compares = 491
: Odd compares = 198
: Even before compares = 1100
: Even after compares = 1098
: Even dup compares = 1088

[ ... ]


HP aC++ B3910B A.01.23
HP aC++ B3910B A.01.19.02 Language Support Library
(the most recent for HP-UX 10.2) produces results
identical to those above.

Brian

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

On Fri, 23 Jun 2000 21:34:23 CST, hinnant@anti-spam_metrowerks.com
(Howard Hinnant) wrote:

> In article <39518fe0.19485159@news.csrlink.net>, jpotter@falcon.lhup.edu
> (John Potter) wrote:
>
> | I expect that Howard will post the excelent results that I think
> | CW will produce.  No undefined behavior this time. :)
>
> Metrowerks CodeWarrior 6.0 beta (might be the same for 5.3, haven't
> checked yet):
>
> Odd compares = 49
> Even before compares = 99
> Even after compares = 147
> Even dup compares = 99
> Odd compares = 99
> Even before compares = 199
> Even after compares = 297
> Even dup compares = 199
>
> I haven't yet looked at the code to see why the "Even after compares"
> differs from the boost::vector_set results.

Because I made no attempt to cover it.  I knew that you would look
better since you said that you did cover it.  That makes yours the
only conformant implementation unless the standard gets changed to
before.  3N is linear.

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              ]

In article <hinnant-2206002251430001@ith3-19f.twcny.rr.com>,
hinnant@anti-spam_metrowerks.com (Howard Hinnant) wrote:

| Metrowerks CodeWarrior 6.0 beta (might be the same for 5.3, haven't
| checked yet):
|
| Odd compares = 49
| Even before compares = 99
| Even after compares = 147
| Even dup compares = 99
| Odd compares = 99
| Even before compares = 199
| Even after compares = 297
| Even dup compares = 199

In the current release (5.3) I had missed an opportunity for optimization
when inserting duplicates:

Odd compares = 49
Even before compares = 99
Even after compares = 147
Even dup compares = 491
Odd compares = 99
Even before compares = 199
Even after compares = 297
Even dup compares = 1088

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

See
  From: Christopher Eltschka <celtschk@physik.tu-muenchen.de>
  Newsgroups: comp.lang.c++.moderated
  Subject: Understanding iterators

If we accept his view that iterators should be understood to point
between elements of a container, the before/after becomes meaningless.

Consider a sequence 1 3 5 7 with an iterator, i, pointing between the
3 and 5.  Dereferencing the iterator gives the element to the right
of the iterator.
   j = seq.insert(i, 4)
The sequence is now 1 3 4 5 7 and j points between 3 and 4.  Where
is i?  Depends.

Alternatively
   insert_iterator<Seq> k(seq, i);
Now k points between 3 and 5.
   *k++ = 4;
Now k points between 4 and 5.  Clearly, the insertion took place after
the old k and the new k is after the inserted item, but still before
the same item as the old k.  Magic. ;)

Returning to the where is i question.  If seq is a vector or deque,
i is invalid and there is no way to determine whether the insertion
came before or after i.  If seq is a list (or an associative being
treated as a sequence for insertion location) i is between 4 and 5.
Was the insertion before i or was it after i and i was magically
moved past it?  Since iterators are implementation defined, there is
no way to know.

The important part is that if the 4 is inserted immediately before
i or immediately after i, it is still between 3 and 5.  If it is
generally understood that the 4 will be inserted between the 3 and
5, it matters not whether the standard says before or after.  The
inserted item will be after *(i-1) and before *i, with these being
vacuously true for i respectively begin and end.

I would like to think that with the new issue, it would also be
considered that the item must be inserted where indicated if that
would not invalidate the associative container.  For unique
containers, that will happen; however, there is nothing to indicate
that it will for equal containers.  Having found two libraries which
make no attempt to test for this, I don't see a change coming.  The
fact that they also fail to insert in unique containers in amortized
constant time with a valid hint will likely continue without complaint.

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              ]