[C++-sig] Re: indexing_v2 status update

[David Abrahams]

Raoul Gough <RaoulGough at yahoo.co.uk> writes:

> David Abrahams <dave at boost-consulting.com> writes:
>
>> Raoul Gough <RaoulGough at yahoo.co.uk> writes:
>>
>>> David Abrahams <dave at boost-consulting.com> writes:
>>>
>>> [snip]
>>>> I don't understand is_reorderable.  How is that different from
>>>>
>>>>   is_convertible<
>>>>       iterator_traits<C::iterator>::iterator_category
>>>>     , forward_iterator_tag
>>>>   >::value
>>>>   && is_non_const_lvalue_iterator<C::iterator>::value
>>>>   && is_assignable<C::value_type>::value
>>>>
>>>> ??
>>>>
>>>> I realize we don't have is_assignable, but shouldn't you phrase this
>>>> in terms of something fundamental like value_type assignability?  We
>>>> can ask all the other questions (see
>>>> boost/iterator/is_lvalue_iterator.hpp).
>>>
>>> It looks like assignability is the really important test for
>>> determining whether a container can be reordered (i.e. sorted or
>>> reversed). However, I can't think of any way to implement an
>>> is_assignable template. 
>>
>> Neither can anyone else, other than specializing for known types and
>> asking the user to specialize for his own.
>
> Well, there is already a ValueTraits concept, so I could easily add an
> "is_assignable" feature to this, and specialize it for the std::pair
> instances that std::map utilizes. That would probably tie up quite
> well with the existing equality_comparable and less_than_comparable.
>
> On the other hand, perhaps this does belong purely in the
> ContainerTraits concept. I wonder whether assignability is always a
> quality of a container (and all instances of it) or just the
> particular type of value stored in a particular instance. In the case
> of the STL containers, I think all template arguments are required to
> be Assignable types

Yes, but...

> and some of the containers (set and map) add
> const qualification somewhere in their value_type.

...that fact tends to make the value_type not Assignable.

> I've just been taking a look at the unordered_set proposal at
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1518.pdf and
> it looks like the unordered_set::value_type is not const qualified,
> which would confuse any assignability determination based on the
> container's value_type directly. 

I'm not sure if that's intentional.  I've asked.

> On the other had, the container only
> provides const iterators, so I guess this means that
> unordered_set<X>::iterator::value_type is "X const", 
> and using the iterator's value type would still work.

No, an iterator's value_type is never const.  You can look at the
mutability of its ``reference`` type, but:

  a. the standard seems to place no requirements on the reference
     type of forward iterators

  b. It barely places requirements on the reference type of
     bidirectional iterators (you have to look for implications in
     the reverse_iterator requirements).

  c. Even having a reference type which is a reference-to-non-const
     doesn't make the value_type assignable.

>>> For instance, std::pair<const int, int> is not
>>> assignable, yet it doesn't have top-level const qualification, and it
>>> *does* have an operator= (which will produce a compile-time error if
>>> used) so I don't think any has_member_function test will help. 
>>
>> Right.  But you can provide partial specializations for
>> std::pair<const T, const U>, 
>> std::pair<T, const U>, 
>> std::pair<const T, U>.
>
> I guess the only potential problem is weirdo cases where the value
> type appears to be assignable but the container still isn't
> reorderable, in which case the client code would have to provide a
> custom-written ContainerTraits anyway. 

There are a number of wierdo cases, but it all comes down to
properties of the value type.

> I'm thinking about some kind of
> a dirty std::set wrapper that pretends its value_type is mutable and
> uses const_cast internally. For motivation, see e.g.
>
> http://groups.google.com/groups?selm=3c939210.56671713%40news.earthlink.net
>
> or http://home.clara.net/raoulgough/map3/index.html

I can't imagine how you plan to use this technique in this case.

>>> If anyone can suggest a workable is_assignable, I'll use it to
>>> deduce is_reorderable, but otherwise I think I'll just stick with
>>> is_mutable_ref and explicit overrides for some containers
>>> (i.e. std::map)
>>
>> I *think* I still think that's an inferior solution.
>
> It's really a question of how the client code helps the library out
> when it would get the wrong answer by itself. 

Yep.

> Possible options include specializing an is_assignable template,
> specializing a value_traits template or providing an alternative
> ContainerTraits class (the current method).

I am not so convinced any more that the current method is worse than
the others.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com