libstdc++/5583: std::set::iterator is readonly

[Mathias Hasselmann]

On Tue, 5 Feb 2002, Carlo Wood wrote:

> On Tue, Feb 05, 2002 at 02:56:09PM -0000, rodrigc@gcc.gnu.org wrote:
> > Synopsis: std::set::iterator is readonly
> > 
> > State-Changed-From-To: open->feedback
> > State-Changed-By: rodrigc
> > State-Changed-When: Tue Feb  5 06:56:09 2002
> > State-Changed-Why:
> >     Your testcase in the "How-to-Repeat" section is
> >     incorrect and doesn't even compile.
> >     Can you submit a full testcase (including #include statements)
> >     which illustrates your problem?
> > 
> > http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=5583
> 
> I didn't look at the PR, but from the Subject I bet that
> he means that (*iter) returns a constant object, even
> for set<Non-Const-Type>::iterator.
> 
> If so, then this is not a bug: the elements of set<> have to be
> constant, you are not allowed to change them because that would
> change the ordering in the set<>.


Agreed: There are situations in which changing attributes of an element
would change the ordering in the set. Looks like my acknowledgement of
this situation was not clear enough in the report.

BUT: Condisider the situation where I want to use std::set to store a set
of edges of an directed weighted graph. Edges of a directed graph are
triples of the kind (u,v,w) where u and v refer to vertices of the graph
and w describes the weight of the edge. Obviously edges of a directed
weighted exclusively are distinguished by their vertices. Obviously it
would be nonsense to allow edgessets like {(1,2,3),(1,2,3)} or
{(1,2,3),(1,2,inf)}. I hope you agree so far.

Now since we have our nice set of edges:


	struct edge_t 
	{ 
		vertex_t * u, * v;
		double weight;

		void set_weight(double new_weight) 
		{
			weight = new_weight;
		}
	};

	typedef std::set<edge_t> set_of_edges_t;


we want to use this ADT to implement for instance Dijkstra's Shortest Path
Algorithm. At the very beginning of Dijkstra's Algorithm (in the form I
know it) we have to initialize all edges of the graph to have an infinite 
weight. In my opinion a good way to achieve this would be to write:


	set_of_edges_t edges;
	std::for_each(edges.begin(), edges.end(),
	std::bind2nd(std::mem_fun_ref(&edge_t::set_weight, INFINITY));


Unfortunatly this simple piece of code fails to compile when
std::set::iterator is a read-only iterator.

Well, it would be possible to hack arround the problem by changing the
definition of edge_t:


                struct edge_t
                {
                        vertex_t * u, * v;
                        mutable double weight; // <- made it mutable
  
                        void set_weight(double new_weight) const // <- const now
                        {
                                weight = new_weight;
                        }
                };

But somehow I don't feel well when doing it that way: It's set_weight's
purpose to modify edges contra caricatures the entire idea of the "const"
keyword... In this situation both "const" qualifiers (the one of the
iterator and the one of set_weight) are used in an absurd manner.


Ciao,
Mathias
-- 
WWW:           http://www.informatik.hu-berlin.de/~hasselma/
PGP/GnuPG:     1024-Bit DSA: ID 55E572F3, 1024-Bit RSA: ID EAAF7CF1