John Potter <jpotter@falcon.lhup.edu> wrote in message
news:1cZb3.3328$hk.141179@newscene.newscene.com...
> : As defined in 23.1.2,7 (table 69), a.insert(p,t) suffers from several
> : problems:
>
> I read this as a.insert(p, t) is treated as a request to insert t
> before p.  The insertion will take place at that point if it is
> consistent for the container; otherwise, it will be treated as
> a.insert(t).  Improved complexity is given when the request is
> consistent.  This is also what the implementations that I have
> seen provide.

This is a good general description of the intent of the container, which was
not fullfilled by its definition.  This would be useful precursor to the
list of problems, since it would set the stage for them.

> : 1. For a container with unique keys, only logarithmic complexity is
> : guaranteed if no element is inserted, even though constant complexity is
> : always possible if p points to an element equivalent to t.
>
> This is possible, but it seems inconsistent with the goals of the
> function.  Attempting to insert a known duplicate in a container with
> unique keys is as invalid as trying to put it in the wrong place.  I
> see no reason to provide improved complexity for what could be
> considered a user error.  It would break the implementations that I
> have seen.

Inserting a duplicate when p pointing to the duplicate isn't exactly the
same thing as inserting a "known duplicate".  In the vast majority of the
cases it would be, but let me present a contrived example showing otherwise.

void insert10and11(set<int>& s)
{
    set<int>::iterator i = s.insert(10).first;
    ++i;
    s.insert(i, 11);
}

This routine would ensure that 10 and 11 exist in the set.  If 11 already
exists, the iterator would already be pointing to it, even though it's not
known at compile time whether i is pointing at 11 or just after 11.

Despite the above technicality, I agree with your general point.  In trying
to come up with an example, I found that it is more natural to solve the
problem more like this:

void insert10and11(set<int>& s)
{
    s.insert(s.insert(11).first, 10);
}

This would provide amortized constant complexity for inserting 10, whether
it is already there or not, if the compexity requirement for
a_uniq.insert(p,t) is changed to:

- complexity: logarithmic in general, but amortized constant if upon return
there is an element with key equivalent to the key of t right before p.

This stays consistent with the other complexity guarantees of insertions in
equivelent containers and insertions that succeed in unique containers.  I
would suspect that this complexity guarantee would not break any
implementations.  However, I have not dug through various implementations'
code, so I'd appreciate feedback on this.

I'd like to maintain a way to get constant complexity when trying to insert
a member that already exists.  Even though such insertion is rarely done, I
believe the it can be implemented in constant time without deteriorating the
efficiency of any other use of the container.  Even something that is rarely
used is often worth having if it is 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              ]

"Ed Brey" <brey@afd.mke.etn.com> wrote:

: - complexity: logarithmic in general, but amortized constant if upon return
: there is an element with key equivalent to the key of t right before p.

: This stays consistent with the other complexity guarantees of insertions in
: equivelent containers and insertions that succeed in unique containers.  I
: would suspect that this complexity guarantee would not break any
: implementations.  However, I have not dug through various implementations'
: code, so I'd appreciate feedback on this.

The basic algorithm used is

if (p == end || t < *p)
   q = p
   if (q == begin || *--q < t)
      put t before p
   else
      use insert(t)
else
   use insert(t)

The two added cases of equality would give

if (p == end || t < *p)
   q = p
   if (q == begin || *--q < t)
      put t before p
   else if (t < *q)
      use insert(t)
   else
      handle duplicate (return q)
else if (*p < t)
   use insert(t)
else
   handle duplicate (return p)

A common use of this function is filling the container from sorted
data.  All inserts use p == end and it gives very nice linear time
rather than NlgN time for simple insert.  In this case there would
be no added testing in the modified algorithm.

I leave it to others to decide whether the gain from the additional
complexity of the algorithm is worth mandating.

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              ]

Nicely done.  I have pitched my draft.  Splitting the row makes the
wording much clearer.

"Ed Brey" <brey@afd.mke.etn.com> wrote:

: As defined in 23.1.2,7 (table 69), a.insert(p,t) suffers from several
: problems:

I read this as a.insert(p, t) is treated as a request to insert t
before p.  The insertion will take place at that point if it is
consistent for the container; otherwise, it will be treated as
a.insert(t).  Improved complexity is given when the request is
consistent.  This is also what the implementations that I have
seen provide.

: 1. For a container with unique keys, only logarithmic complexity is
: guaranteed if no element is inserted, even though constant complexity is
: always possible if p points to an element equivalent to t.

This is possible, but it seems inconsistent with the goals of the
function.  Attempting to insert a known duplicate in a container with
unique keys is as invalid as trying to put it in the wrong place.  I
see no reason to provide improved complexity for what could be
considered a user error.  It would break the implementations that I
have seen.

: 3. By guaranteeing amortized constant complexity only when t is inserted
: after p, it is impossible to guarantee constant complexity if t is inserted
: at the beginning of the container.  Such a problem would not exist if
: amortized constant complexity was guaranteed if t is inserted before p,
: since there is always some p immediately before which an insert can take
: place.

Yes, the "after" seems to be a typo.  See also the 1995 HP
documentation.  No implementation meets the "after" requirement
but they do meet the "before" requirement.

I think your changes, less item 1, express what was intended and agree
with existing practice.

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              ]

Nicely done.  I have pitched my draft.  Splitting the row makes the
wording much clearer.

"Ed Brey" <brey@afd.mke.etn.com> wrote:

: As defined in 23.1.2,7 (table 69), a.insert(p,t) suffers from several
: problems:

I read this as a.insert(p, t) is treated as a request to insert t
before p.  The insertion will take place at that point if it is
consistent for the container; otherwise, it will be treated as
a.insert(t).  Improved complexity is given when the request is
consistent.  This is also what the implementations that I have
seen provide.

: 1. For a container with unique keys, only logarithmic complexity is
: guaranteed if no element is inserted, even though constant complexity is
: always possible if p points to an element equivalent to t.

This is possible, but it seems inconsistent with the goals of the
function.  Attempting to insert a known duplicate in a container with
unique keys is as invalid as trying to put it in the wrong place.  I
see no reason to provide improved complexity for what could be
considered a user error.  It would break all implementations that I
have seen.

: 3. By guaranteeing amortized constant complexity only when t is inserted
: after p, it is impossible to guarantee constant complexity if t is inserted
: at the beginning of the container.  Such a problem would not exist if
: amortized constant complexity was guaranteed if t is inserted before p,
: since there is always some p immediately before which an insert can take
: place.

Yes, the "after" seems to be a typo.  See also the 1995 HP
documentation.  No implementation meets the "after" requirement
but they do meet the "before" requirement.

I think your changes, less item 1, express what was intended and agree
with existing practice.

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              ]

As defined in 23.1.2,7 (table 69), a.insert(p,t) suffers from several
problems:

1. For a container with unique keys, only logarithmic complexity is
guaranteed if no element is inserted, even though constant complexity is
always possible if p points to an element equivalent to t.

2. For a container with equivalent keys, the amortized constant complexity
guarantee is only useful if no key equivalent to t exists in the container.
Otherwise, the insertion could occur in one of multiple locations, at least
one of which would not be right after p.

3. By guaranteeing amortized constant complexity only when t is inserted
after p, it is impossible to guarantee constant complexity if t is inserted
at the beginning of the container.  Such a problem would not exist if
amortized constant complexity was guaranteed if t is inserted before p,
since there is always some p immediately before which an insert can take
place.

4. For a container with equivalent keys, p does not allow specification of
where to insert the element, but rather only acts as a hint for improving
performance.  This negates the added functionality that p would provide if
it specified where within a sequence of equivalent keys the insertion should
occur.  Specifying the insert location provides more control to the user,
while providing no disadvantage to the container implementation.


Proposed solution:

Replace the row in table 69 for a.insert(p,t) with the following rows:

- expression: a_uniq.insert(p,t)
- return type: iterator
- pre/post-condition: inserts t if and only if there is no element with key
equivalent to the key of t.  returns the iterator pointing to the element
with key equivalent to the key of t.
- complexity: logarithmic in general, but amortized constant if t is
inserted right before p or p points to an element with key equivalent to t.

- expression: a_eq.insert(p,t)
- return type: iterator
- pre/post-condition: inserts t and returns the iterator pointing to the
newly inserted element.  t is inserted right before p if doing so preserves
the container ordering.
- complexity: logarithmic in general, but amortized constant if t is
inserted right before p.
---
[ 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              ]