[I originally posted this six days ago, but it hasn't yet shown up at Deja
or my local newsfeed.  I apologize if you see this twice.]

My head hurts.  I'm trying to figure out the situation regarding element
assignability in associative containers, but, well, my head hurts.

I'll start with something simple: assignment to a map element is illegal,
because for a map<K, V>, the type of the elements is pair<const K, V>.
Fine, crystal clear.  The container requirements say that elements must be
assignable, but for map, they're not, and LWG issue 140 makes clear that
it's going to stay that way.  Again, fine.

But the container requirements also state that bulk assignment of
containers is allowed (this is in Table 65), so this is supposed to be
okay:

  map<K, V> map1;
  map<K, V> map2;

  map1 = map2;

Is that true, i.e., is it true that you're not allowed to make an
assignment to an element of a map but you *are* allowed to perform a bulk
assignment from one map to another?  If so, what are the semantics?  Table
65 conveniently gives none, though Josuttis makes it sound like you destroy
all the elements of map1 and then copy over all the elements in map2.  In
other words, performing a bulk assignment of a map (or any container, for
that matter) involves no underlying element assignments.  Rather, it
involves underlying calls to element destructors and copy constructors.
That actually makes sense to me.  Table 65 says that the complexity of
container assignment is linear, but it doesn't say what functions are
called.  Have I overlooked something in the standard that says that in this
code,

  Container<T> container1, container2;
  ...
  container1 = container2;

we get container1.size() invocations of T's destructor and
container2.size() invocations of T's copy constructor?

(Once I get this figured out, I have to try to figure out how to make sense
of the set::iterator mess.  I've just found out that of the four STL
implementations I have, two make set::iterator mutable and two make it
immutable.  Sigh.)

Thanks,

Scott

--
"Effective STL" Seminar     June 7-9     Portland, Oregon
Details at http://www.trekservices.com/estl/

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

Scott Meyers <smeyers@aristeia.com> a    crit dans le message :
MPG.13342bd1814ec2d09896d4@news.supernews.com...
> [I originally posted this six days ago, but it hasn't yet shown up at Deja
> or my local newsfeed.  I apologize if you see this twice.]
>
> My head hurts.  I'm trying to figure out the situation regarding element
> assignability in associative containers, but, well, my head hurts.
>
> I'll start with something simple: assignment to a map element is illegal,
> because for a map<K, V>, the type of the elements is pair<const K, V>.

Ummm, this only means the KEY cannot be changed.  This is necessary because
changing the key means changing the ordering of the elements stored in the
map.  However the value associated with the key can be changed - it is not
const as you can see.

> Fine, crystal clear.  The container requirements say that elements must be
> assignable, but for map, they're not, and LWG issue 140 makes clear that
> it's going to stay that way.  Again, fine.
>
> But the container requirements also state that bulk assignment of
> containers is allowed (this is in Table 65), so this is supposed to be
> okay:
>
>   map<K, V> map1;
>   map<K, V> map2;
>
>   map1 = map2;
>
> Is that true, i.e., is it true that you're not allowed to make an
> assignment to an element of a map but you *are* allowed to perform a bulk
> assignment from one map to another?  If so, what are the semantics?  Table

Assignment makes a copy of all the elements by using the copy constructors
for the key & value to copy each element.

> 65 conveniently gives none, though Josuttis makes it sound like you
destroy
> all the elements of map1 and then copy over all the elements in map2.  In
> other words, performing a bulk assignment of a map (or any container, for
> that matter) involves no underlying element assignments.  Rather, it
> involves underlying calls to element destructors and copy constructors.
> That actually makes sense to me.  Table 65 says that the complexity of
> container assignment is linear, but it doesn't say what functions are
> called.  Have I overlooked something in the standard that says that in
this
> code,
>
>   Container<T> container1, container2;
>   ...
>   container1 = container2;
>
> we get container1.size() invocations of T's destructor and
> container2.size() invocations of T's copy constructor?

Yup I believe so.

>
> (Once I get this figured out, I have to try to figure out how to make
sense
> of the set::iterator mess.  I've just found out that of the four STL
> implementations I have, two make set::iterator mutable and two make it
> immutable.  Sigh.)

Yeah there are implementation hacks because set is often based on a generic
red-black tree class but elements of a set cannot be changed because that
could change the ordering of the elements stored within it!  Therefore set's
iterator and const_iterator are the same - they do not let you modify the
elements to which they point.

If you take a look at the immutable implementations you'll probably see
horrible casts which get around constness problems (see the insert()
functions).  The mutable implemenations avoid the casts but I think its
dangerous to make data members mutable because then ANY function can modify
them.

Hope this helps...


Gawain
--
----------------------------------------------------------------------------
-------------
Gawain Bolton
gp.bolton@computer.org
Paris, France
----------------------------------------------------------------------------
-------------



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

> Yeah there are implementation hacks because set is often based on a
generic
> red-black tree class but elements of a set cannot be changed because
that
> could change the ordering of the elements stored within it! Therefore
set's
> iterator and const_iterator are the same - they do not let you modify
the
> elements to which they point.

Actually, it turned out that the standard is not clear regarding this.
Currently it is under discussion whether elements of a set should be
const or it should be up to the user not to violate the sorting
criterion.
Note, in addition that some implementations declare set elements
not as being const from an iterators point of view (e.g. VC++6.0)!

See http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
for the actual library issue.
However, I am not sure whether I will support the current solution.
This is because it is not clear to me that implementations
that declare set elements as being const are still standard
conforming. And they should be IMO.

Nico


Sent via Deja.com http://www.deja.com/
Before you buy.

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

Gawain Bolton wrote:

[...]

> Yeah there are implementation hacks because set is often based on a generic
> red-black tree class but elements of a set cannot be changed because that
> could change the ordering of the elements stored within it!  Therefore set's
> iterator and const_iterator are the same - they do not let you modify the
> elements to which they point.
>
> If you take a look at the immutable implementations you'll probably see
> horrible casts which get around constness problems (see the insert()
> functions).

Is this guessed, or did you actually look at one?

I don't see why constness problems have to arise:

template<class T, class Compare = less<T>, ...> class set
{
  class __set_iterator
  {
    friend class map;
  public:
    Key const& operator*()
    {
      return internal->value;
    } // no mutable access for the general public
    ...
  private:
    type_of_map_internal_data* internal;
  };

public:
  typedef __set_iterator iterator;
  typedef __set_iterator const_iterator;

  ...

  iterator insert(iterator pos, value_type const& v)
  {
    Compare less;
    if (*pos == v)
      return pos;

    // we are friends, so use that fact
    if (less(*pos, v) && less(v, *(pos+1)))
      return _insert_after(pos.internal, v); // pos.internal is mutable!
    else
      return insert(v);
  }

  ...
};

Indeed, I cannot imagine that you can implement insert
efficiently without having access to the iterator internals.
Therefore I'd be surprised if _any_ vendor did a const_cast.

> The mutable implemenations avoid the casts but I think its
> dangerous to make data members mutable because then ANY function can modify
> them.
>
> Hope this helps...

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

Scott Meyers wrote:

> I'll start with something simple: assignment to a map element is illegal,
> because for a map<K, V>, the type of the elements is pair<const K, V>.

Correct

> But the container requirements also state that bulk assignment of
> containers is allowed (this is in Table 65), so this is supposed to be
> okay:
>
>   map<K, V> map1;
>   map<K, V> map2;
>
>   map1 = map2;
>
> Is that true, i.e., is it true that you're not allowed to make an
> assignment to an element of a map but you *are* allowed to perform a bulk
> assignment from one map to another?

Where is the problem ?

> If so, what are the semantics?

The obvious semantic. The semantic of assignement: after a = b, a has
the
same value as b (a == b).

Of course the tables describing concepts are broken (Container
requirements,
in 23.1/5, has some funny lines), and this may not be said explicitly.
But the
whole generic requirements of the standard need to be rewritten anyway.

--

Valentin Bonnard

---
[ 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 Eltschka <celtschk@physik.tu-muenchen.de> a    crit dans le
message : 38CE6A26.74FAA75C@physik.tu-muenchen.de...
> Gawain Bolton wrote:
>
> [...]
>
> > Yeah there are implementation hacks because set is often based on a
generic
> > red-black tree class but elements of a set cannot be changed because
that
> > could change the ordering of the elements stored within it!  Therefore
set's
> > iterator and const_iterator are the same - they do not let you modify
the
> > elements to which they point.
> >
> > If you take a look at the immutable implementations you'll probably see
> > horrible casts which get around constness problems (see the insert()
> > functions).
>
> Is this guessed, or did you actually look at one?
>
Take a look at SGI's implementation of the set container class:
http://www.sgi.com/Technology/STL/stl_set.h

In particular the following function:

iterator insert(iterator __position, const value_type& __x)

You will see a horrible cast because the set iterator is in fact a
const_iterator but the underlying red-black tree's insert() function called
takes an iterator which is not const.

> I don't see why constness problems have to arise:
>
I did not say constness problems HAD to arise.  They CAN do though depending
on the implementation.


Gawain

--
----------------------------------------------------------------------------
-------------
Gawain Bolton
gp.bolton@computer.org
Paris, France
----------------------------------------------------------------------------
-------------


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