On 08 Mar 98 00:31:11 GMT, sorry@but.spammed.out (Howard Hinnant)
wrote:

> In article <6dol3k$agu$1@excalibur.flash.net>, "Christopher M. Gurnee"
> <gurnec@nospam.yahoo.com> wrote:
> There is a published tree structure that makes incrementing the iterator
> trivial and constant time (as cheap as vector).

Nope, succ of root is still log(N).

> Check out "threaded trees" in "The Art of Computer Programming", Vol 1,
> 3rd ed., Knuth.

> It also only requires two pointers per node.

And two bits to tell threads from branches.  To keep alignment, this
often takes the same space as a pointer.

> It's very cool!  I haven't
> implemented this, so if there are known problems with this structure, I
> would like to hear about it.

No problems with the structure; however, I don't think you can get
amortized constant time for void map::erase(iterator) as required.

I'm open to e-mail discussion but that's enough in csc++.

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              ]

Srinivas Vobilisetti wrote:

> Though, the interface iterator erase(iterator) work for both vectors and
> maps, returning an iterator to the next element for vectors is an O(1)
> complexity while returning an iterator to the next element for maps is
> O(log(n)) complexity where n is the size of the map.

This is simply wrong. Iterator increment is O(1) by definition.

Were you in London when we talked about that ?

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ 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              ]

Valentin Bonnard wrote in message <34FF4BFA.3B61@pratique.fr>...
>Srinivas Vobilisetti wrote:
>
>> Though, the interface iterator erase(iterator) work for both vectors and
>> maps, returning an iterator to the next element for vectors is an O(1)
>> complexity while returning an iterator to the next element for maps is
>> O(log(n)) complexity where n is the size of the map.
>
>This is simply wrong. Iterator increment is O(1) by definition.

All defined iterator operations do take amortized constant time,
however, the worst case time is unspecified.  In most implementations,
the worst case for a map increment is O(lg(n)).  Granted, this is
irrellevant if one iterates through the entire map.  At any rate,
incrementing a vector iterator is trivial (in most implementations),
incrementing a map iterator could take a bit longer (even from a
constant time point of view).

Looking through the containers, it appears as though member functions
only return iterators if
  1) It is the point of the function's existance (e.g. find)
  2) It is trivial to find the appropriate return value.
By that last one, I mean that either the return value is already being
computed as a result of the algorithm (most likely) being used, or the
return value can (most likely) be trivially computed (e.g. a pointer
increment).  Making these assessments does require making assumptions
on what algorithms are actually used.  Although the standard rarely
states that a certain algorithm must be used to preform some
operation, it often describes time complexity requirements that imply
a certain algorithm is used.  For example, vectors will probably be
reallocating arrays in most implementations, and maps will probably be
balanced binary trees in most implementations.  After making these
assumptions, it is easy to see which operations are "trivial" and
which ones are not (a map iterator increment would not be trivial).
Of course, nothing prevents an implementation from using something
completely different, as long as it conforms to the standard.

-Chris
---
[ 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 <6dol3k$agu$1@excalibur.flash.net>, "Christopher M. Gurnee"
<gurnec@nospam.yahoo.com> wrote:

> In most implementations,
> the worst case for a map increment is O(lg(n)).  Granted, this is
> irrellevant if one iterates through the entire map.  At any rate,
> incrementing a vector iterator is trivial (in most implementations),
> incrementing a map iterator could take a bit longer (even from a
> constant time point of view).
>
> ... For example, vectors will probably be
> reallocating arrays in most implementations, and maps will probably be
> balanced binary trees in most implementations.  After making these
> assumptions, it is easy to see which operations are "trivial" and
> which ones are not (a map iterator increment would not be trivial).
> Of course, nothing prevents an implementation from using something
> completely different, as long as it conforms to the standard.

There is a published tree structure that makes incrementing the iterator
trivial and constant time (as cheap as vector).

Check out "threaded trees" in "The Art of Computer Programming", Vol 1,
3rd ed., Knuth.

It also only requires two pointers per node.  It's very cool!  I haven't
implemented this, so if there are known problems with this structure, I
would like to hear about it.

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

In article <6dctdm$o28$1@excalibur.flash.net>,
  "Christopher M. Gurnee" <gurnec@nospam.yahoo.com> wrote:
>
> Howard Hinnant wrote in message ...
> >Hi,
> >
> >I've noticed that the non-associative containers have members like:
> >
> >iterator vector::erase(iterator p);
> >
> >The returned iterator points to the next element (before erasure).
> >
> >However for associative containers the signiture is:
> >
> >void map::erase(iterator p);
> >
> >Why?  I can think of no reason for this behavior.  This makes it
> >significantly harder to process a map, and erase as you go.  Can
> anyone
> >shed some insight for the reasoning behind this?  Or am I looking at
> a bug
> >in the standard?
>
> As far as I know, it's not a bug (as of CD-2).  However, there is no
> loss in functionality.  Consider:
>
> std::vector<int> ivec;
> std::vector<int>::iterator ivecit;
> std::set<int> iset;
> std::set<int>::iterator isetit;
> ...
> ivecit = ivec.erase(ivecit);
> iset.erase(isetit++);

There is a serious loss of functionality.  Consider:

    template< class Container , class Predicate >
    void
    removeIf( Container& c , Predicate p )
    {
        for ( Container::iterator i = c.begin() ; i != c.end() ; )
        {
            if ( p( *i ) )
                i = c.erase( i ) ;
            else
                ++ i ;
        }
    }

Basically, because there are two different idioms, you can't use the
functionality in a template.

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading

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

Howard Hinnant wrote:
<snip>
>
> This is no great flaw.  A minor nit pick.  (Certainly not worth another
> round of changes!!!)  I was curious if there were some reason that all
> containers didn't use the same signiture for erase (iterator
> erase(iterator) ).  This signiture could easily work for both vectors and
> maps.

Though, the interface iterator erase(iterator) work for both vectors and
maps, returning an iterator to the next element for vectors is an O(1)
complexity while returning an iterator to the next element for maps is
O(log(n)) complexity where n is the size of the map. IMO, efficiency
might be the reason for the difference in the erase() interface. Also,
in case of vector, all the iterators for the elements next to the
element being erased are invalidated but not in case of map.

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

Hi,

I've noticed that the non-associative containers have members like:

iterator vector::erase(iterator p);

The returned iterator points to the next element (before erasure).

However for associative containers the signiture is:

void map::erase(iterator p);

Why?  I can think of no reason for this behavior.  This makes it
significantly harder to process a map, and erase as you go.  Can anyone
shed some insight for the reasoning behind this?  Or am I looking at a bug
in the standard?

Thanks,
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              ]

Howard Hinnant wrote in message ...
>Hi,
>
>I've noticed that the non-associative containers have members like:
>
>iterator vector::erase(iterator p);
>
>The returned iterator points to the next element (before erasure).
>
>However for associative containers the signiture is:
>
>void map::erase(iterator p);
>
>Why?  I can think of no reason for this behavior.  This makes it
>significantly harder to process a map, and erase as you go.  Can
anyone
>shed some insight for the reasoning behind this?  Or am I looking at
a bug
>in the standard?

As far as I know, it's not a bug (as of CD-2).  However, there is no
loss in functionality.  Consider:

std::vector<int> ivec;
std::vector<int>::iterator ivecit;
std::set<int> iset;
std::set<int>::iterator isetit;
...
ivecit = ivec.erase(ivecit);
iset.erase(isetit++);

Both of the above delete the element pointed to by the iterator, and
leave the iterator pointing to the element following the deleted
element (or end() if no such element exists).  The next question might
be why bother returning something from vector<>::erase() if you can
just use:
  ivec.erase(ivecit++);
instead?  Unfortunately, this statement leaves ivecit with an
undefined value.  Here's what it does:
  1) increment the value stored in ivecit (no problems here)
  2) call ivec.erase() with the value of ivecit before it was
incremented
Given an iterator "it", during a call to ivec.erase(it), all iterators
in the range [it, ivec.end()] become invalidated.  Since ivecit points
to the element after the one being deleted during the call
ivec.erase(ivecit++), ivecit becomes invalidated.

If vector<>erase() didn't return an iterator the way it does,
something ugly like:
  ivec.erase(--ivecit + 1);  // erase element pointed to by ivecit
  ++ivecit;  // now ivecit points to the element following the deleted
one
would be required.  Associative containers don't have this "problem"
since the only iterators invalidated by the call iset.erase(it) are
those pointing to the erased element.
  iset.erase(isetit++);
is well defined, leaving the value of isetit well defined too.

-Chris
---
[ 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 <6dctdm$o28$1@excalibur.flash.net>, "Christopher M. Gurnee"
<gurnec@nospam.yahoo.com> wrote:

> As far as I know, it's not a bug (as of CD-2).  However, there is no
> loss in functionality.  Consider:
<snip>

Hi Chris, thanks for your response.  I completely agree with you that
there is no loss in functionality.  The "bug" that I see (perhaps bug is
too harsh a word) is that you have to change code to change containers.

One of the beautiful aspects of STL is that code that looks like:

for (container::iterator i = container.begin(); i != container.end(); ++i)
{
   do stuff with container and i
}

works for all containers!  This is really cool.  I can switch the type of
container without breaking my code.

But, if I want to traverse a container, erasing elements as I go, I need
to decide apriori whether I want to use associative containers or
non-associative containers.

for (container::iterator i = container.begin(); i != container.end();)
{
   do stuff with container and i;

   i = container.erase(i);  // works for non-associative container
   // or
   container.erase(i++);  // works for associative container
}

This is no great flaw.  A minor nit pick.  (Certainly not worth another
round of changes!!!)  I was curious if there were some reason that all
containers didn't use the same signiture for erase (iterator
erase(iterator) ).  This signiture could easily work for both vectors and
maps.

I suspect that this is just a minor oversite.  Although I may be missing a
good technical reason that associative containers don't have the same
signiture.  If there is a good reason, I would sure like to know it.  I
hate it when I sound ignorant!  ;-)

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

Christopher M. Gurnee wrote:
> > As far as I know, it's not a bug (as of CD-2).  However, there is no
> loss in functionality.  Consider:
>
> std::vector<int> ivec;
> std::vector<int>::iterator ivecit;
> std::set<int> iset;
> std::set<int>::iterator isetit;
> ...
> ivecit = ivec.erase(ivecit);
> iset.erase(isetit++);
>
> Both of the above delete the element pointed to by the iterator, and
> leave the iterator pointing to the element following the deleted
> element (or end() if no such element exists).  The next question might
> be why bother returning something from vector<>::erase() if you can
> just use:
>   ivec.erase(ivecit++);
> instead?  Unfortunately, this statement leaves ivecit with an
> undefined value.  Here's what it does:
>   1) increment the value stored in ivecit (no problems here)
>   2) call ivec.erase() with the value of ivecit before it was
> incremented
> Given an iterator "it", during a call to ivec.erase(it), all iterators
> in the range [it, ivec.end()] become invalidated.  Since ivecit points
> to the element after the one being deleted during the call
> ivec.erase(ivecit++), ivecit becomes invalidated.
>
> If vector<>erase() didn't return an iterator the way it does,
> something ugly like:
>   ivec.erase(--ivecit + 1);  // erase element pointed to by ivecit
>   ++ivecit;  // now ivecit points to the element following the deleted
> one
> would be required.  Associative containers don't have this "problem"
> since the only iterators invalidated by the call iset.erase(it) are
> those pointing to the erased element.
>   iset.erase(isetit++);
> is well defined, leaving the value of isetit well defined too.

But this doesn't answer the question of why they are different in the
draft.  I understand the reasoning for needing the erase() member to
return a new iterator for the vector case, but for the set case, there
is no reason it shouldn't do that.  Now every programmer has to remember
two different programming idioms, which makes using STL more prone to
mistakes.

--
Jon Biggar
Floorboard Software
jon@floorboard.com
jon@biggar.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              ]