[Dev] Pruning elements from sorted associative sequence containers (set, multiset, map, multimap)

[Tanner Lovelace]

--=-CTI6Vz7+VF9ITpt9lr5+
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

On Tue, 2002-02-12 at 06:21, M. Mueller (bhu5nji) wrote:

> What I learned is that a container size must remain constant when an iter=
ator=20
> is being used in a loop guard condition.  If this rule cannot be followed=
,=20
> then the loop must be forcefully aborted.  This is a practical rule only.

Hmm... the Josuttis book says this about erase:

"For vectors and deques, this operation might invalidate iterators and=20
reference to other elements." =20

Which seems to suggest that iterators of other containers shouldn't
be invalidated.  I wonder if the spec changed this at the last minute?

Hmm... actually looking at the implementation gives some insight,
though.  Apparently, associative containers are implemented using
red-black trees.  RB trees, being balanced, will tend to shift
quite a bit whenever something is inserted or deleted.  That's the
most likely reason why erase invalidates the iterators.

=20
> The Musser 2nd Ed. book has no example AFAIK showing the potential flaw a=
nd a=20
> work around.  The only hint is in Section 21.1.5 Sorted Associative Conta=
iner=20
> Requirements on page 326 where it states,
>=20
> "Finally, an *iterator* of a sorted associative container is bidirectiona=
l.=20
> The *insert* operations do not affect the validity of the iterators and=20
> references to the container, and *erase* operations invalidate only itera=
tors=20
> and references to the erased elements."
>=20
> It appears that the reason that *erase* invalidates iterators is left as =
an=20
> exercise for the reader.  This reader could use a little help, however.
>=20

See above.  For a non-associative container, however, it's a little
bit different.  Lists should have no problem.  iterators should still
work (try it out, if you're curious).  For vectors, however, because
the memory allocation is dynamic, if an insert or erase triggers
an allocation/deallocation in memory, the container could be moved
to a different location, and therefore have all it's iterators
invalidated.

Tanner
--=20
Tanner Lovelace | lovelace@wayfarer.org | http://wtl.wayfarer.org/
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
GPG Fingerprint =3D A66C 8660 924F 5F8C 71DA  BDD0 CE09 4F8E DE76 39D4
GPG Key can be found at http://wtl.wayfarer.org/lovelace.gpg.asc
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
 Those who are willing to sacrifice essential liberties for a little=20
 order, will lose both and deserve neither.  --  Benjamin Franklin=20

 History teaches that grave threats to liberty often come in times
 of urgency, when constitutional rights seem too extravagant to=20
 endure.  --  Justice Thurgood Marshall, 1989=20

--=-CTI6Vz7+VF9ITpt9lr5+
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQA8aYTMzglPjt52OdQRAjphAKDBSJ/9t01MfTcA6lh4nT2a6i+8WwCfbESO
NVlzAQRdiZw37HpbplZ8KQQ=
=mhDh
-----END PGP SIGNATURE-----

--=-CTI6Vz7+VF9ITpt9lr5+--