Add a few missing things from the iterator library

[gafu...@gmail.com]

Hi,

I propose to add to <iterator>:

1) std::mbegin(container)/std::mend

Semantics: Return moveable iterators, exactly the same as std::make_move_iterator(std::begin(container))

Why: We already have std::begin and std::cbegin and I believe this is a odd one out for consistency

2) std::make_const_iterator(iterator)

Semantics: return iterator static_cast-ed to const_iterator

Why: We have std::make_move_iterator so again I believe this is missing. Container requirements (23.2) specify that iterators must be convertible to const_iterator so I believe this is just a static_cast.

3) std::container_of_t<decltype(iterator)>

Semantics: determine the container type of the iterator

Why: Helpful to implement 2 above, also helpful in a variety of situations where there's a need to check requirements on the container of an iterator.

Thanks,

-- Giovanni

[Daniel Krügler]

2017-07-10 19:47 GMT+02:00 <gafu...@gmail.com>:
> Hi,
>
> I propose to add to <iterator>:

[..]

> 2) std::make_const_iterator(iterator)
> Semantics: return iterator static_cast-ed to const_iterator
> Why: We have std::make_move_iterator so again I believe this is missing.
> Container requirements (23.2) specify that iterators must be convertible to
> const_iterator so I believe this is just a static_cast.
>
> 3) std::container_of_t<decltype(iterator)>
> Semantics: determine the container type of the iterator
> Why: Helpful to implement 2 above, also helpful in a variety of situations
> where there's a need to check requirements on the container of an iterator.

These two proposals make assumptions that are neither met by current
implementations nor implied by the standard: There is no 1:1 relation
between container type and iterator type, which makes both (2) and (3)
impossible. It would also break non-Standard-Library implementations
of containers such as from Boost or other third-party libraries.

- Daniel

[Ray Hamel]

On Monday, July 10, 2017 at 1:47:29 PM UTC-4, gafu...@gmail.com wrote:

3) std::container_of_t<decltype(iterator)>

Semantics: determine the container type of the iterator

Why: Helpful to implement 2 above, also helpful in a variety of situations where there's a need to check requirements on the container of an iterator.

Someone with more knowledge of template metaprogramming and the type system than I do needs to weigh in on this, but I'm not sure if this is currently possible in ISO C++.

An alternative might be something like

std::container_from_value_type<ValueType, Container=std::vector<ValueType>>
std::container_from_iterator<Iterator,Container=std::vector<std::remove_pointer_t<Iterator>>

-Ray

[Ray Hamel]

On a second look that suggestion of mine doesn't make any sense, but you could have vector_from_(value_type|iterator), list_from_(value_type|iterator) and so on for the standard containers.

[Brian Bi]

I think 2 is possible though it may not necessarily have desirable properties. It can have a generic implementation that returns a std::const_iterator<Iterator> (where std::const_iterator is an adaptor template similar to std::move_iterator). It can be partially specialized on T* to return const T* and then container libraries can add custom overloads for their own iterator types that will be found via ADL, but only if the iterator type isn't T* or something like that.

 

--

Brian Bi

[Giovanni Funchal]

On Mon, Jul 10, 2017 at 7:49 PM, Brian Bi <bbi...@gmail.com> wrote:

On Mon, Jul 10, 2017 at 11:21 AM, Daniel Krügler <daniel....@gmail.com> wrote:

2017-07-10 19:47 GMT+02:00  <gafu...@gmail.com>:
> Hi,
>
> I propose to add to <iterator>:

[..]

> 2) std::make_const_iterator(iterator)
> Semantics: return iterator static_cast-ed to const_iterator
> Why: We have std::make_move_iterator so again I believe this is missing.
> Container requirements (23.2) specify that iterators must be convertible to
> const_iterator so I believe this is just a static_cast.
>
> 3) std::container_of_t<decltype(iterator)>
> Semantics: determine the container type of the iterator
> Why: Helpful to implement 2 above, also helpful in a variety of situations
> where there's a need to check requirements on the container of an iterator.

These two proposals make assumptions that are neither met by current
implementations nor implied by the standard: There is no 1:1 relation
between container type and iterator type, which makes both (2) and (3)
impossible. It would also break non-Standard-Library implementations
of containers such as from Boost or other third-party libraries.

I agree with Daniel's point that the 1:1 relation between container and iterator types is not currently mandated. However:

- I believe it only affects (3).

- Due to std::iterator_traits<iterator>, iterators know something about their container (iterator_category) so there is already limited scope for an iterator to be used in multiple containers. BTW, perhaps std::iterator_traits<iterator>::iterator_container would be a better place for (3).

- I'm not sure I understand your claim that existing code would break. I envision it as a template specialized to std container's iterators and other container libraries could add their own specializations similarly to what is already done for example in std::hash.

 

I think 2 is possible though it may not necessarily have desirable properties. It can have a generic implementation that returns a std::const_iterator<Iterator> (where std::const_iterator is an adaptor template similar to std::move_iterator). It can be partially specialized on T* to return const T* and then container libraries can add custom overloads for their own iterator types that will be found via ADL, but only if the iterator type isn't T* or something like that.

I like Brian's idea of std::const_iterator as an adaptor template.

Thanks,

-- Giovanni

[Thiago Macieira]

On segunda-feira, 10 de julho de 2017 22:21:10 PDT Giovanni Funchal wrote:
> I agree with Daniel's point that the 1:1 relation between container and
> iterator types is not currently mandated. However:
> - I believe it only affects (3).

Strictly speaking, yes. But (2) is also difficult to achieve. You're asking for
a way to transform an iterator to const_iterator, but those types are often
unrelated. For example, for libstdc++'s std::unordered_map, the two iterator
classes are just aliases to std::__detail::_Node_const_iterator and
std::__detail::_Node_iterator.

A const iterator is not the same as a const_iterator.

> - Due to std::iterator_traits<iterator>, iterators know something about
> their container (iterator_category) so there is already limited scope for
> an iterator to be used in multiple containers. BTW, perhaps
> std::iterator_traits<iterator>::iterator_container would be a better place
> for (3).

First, the category is the category of the iterator, not of the container.
Second, you cannot have a link back to the container, period. (3) is simply
unachievable. Just think of this, what should this be

std::iterator_traits<char *>::container

choose:
std::vector<char>
std::string
std::basic_string<char, any trait, any allocator> really...
std::array<char, N>
QVector<char>
QByteArray

> - I'm not sure I understand your claim that existing code would break. I
> envision it as a template specialized to std container's iterators and
> other container libraries could add their own specializations similarly to
> what is already done for example in std::hash.

Right, if you're adding a new set of functions and new members in the
template, existing generic code that isn't using those functions or those
members cannot break.

The problem is when people start using them, but their generic code works with
only a few containers that have been updated. When someone else tries to use
it with some non-updated container, it breaks.

There needs to be a good reason to do what you're asking.

> > I think 2 is possible though it may not necessarily have desirable
> > properties. It can have a generic implementation that returns a
> > std::const_iterator<Iterator> (where std::const_iterator is an adaptor
> > template similar to std::move_iterator). It can be partially specialized
> > on
> > T* to return const T* and then container libraries can add custom
> > overloads
> > for their own iterator types that will be found via ADL, but only if the
> > iterator type isn't T* or something like that.
>
> I like Brian's idea of std::const_iterator as an adaptor template.

std::const_itererator<iterator> is not std::const_iterator. That means that if
you tried to use this in generic code that actually used the container's
const_iterator, it would fail.

Just try:

void f(std::unordered_map<int, int>::const_iterator);
void g(std::unordered_map<int, int>::iterator it)
{
f(std::make_const_iterator(it));
}

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Nicol Bolas]

Even better, what about iterators that do not have containers? Things like iterator wrappers and mutators.

No algorithm has any right to query anything about the iterator's container. That's the whole point of iterators: to be the intermediary between the container of the data and the algorithm that acts on the data. If there is something lacking in our iterator interfaces which algorithms genuinely need, then that is what needs to be fixed.

[Giovanni Funchal]

Hi,

Thanks Thiago, Nicol, those are some very good points and I now think like you that (3) was a bad idea, but I still think proposals (1) and (2) might make sense to propose as additions.

> Just try:

This works:

void f(std::unordered_map<int, int>::const_iterator) {}

void g(std::unordered_map<int, int>::iterator it)

{

    f(static_cast<std::unordered_map<int, int>::const_iterator>(it));

}

(this conversion is a container requirement)

Granted it is not trivial to implement std::make_const_iterator so that it deduces the type to cast to, but I think disregarding implementation for one second that this just points out how useful this feature would be if g() needed a const_iterator for whatever reason, exactly because a const_iterator is not a const iterator.

Furthermore, one way I like to reason about this is making the table below which illustrates the asymmetry in available functionality:

(1) Iterator type -> access function templates

iterator (std::begin/std::end)

reverse_iterator (std::rbegin/std::rend)

const_iterator (std::cbegin/std::cend)

move_iterator (Missing std::mbegin/std::mend)

(2) Iterator type -> conversion function template

reverse_iterator (std::make_reverse_iterator)

const_iterator (Missing std::make_const_iterator)

move_iterator (std::make_move_iterator)

Thanks,

-- Giovanni

--
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/KQII_ogpfxo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/6e2d133b-1c0a-49a9-ae2b-98d82d3a40d3%40isocpp.org.

[Thiago Macieira]

On terça-feira, 11 de julho de 2017 13:09:09 PDT Giovanni Funchal wrote:
> Thanks Thiago, Nicol, those are some very good points and I now think like
> you that (3) was a bad idea, but I still think proposals (1) and (2) might
> make sense to propose as additions.

Why? What value does it give?

> > Just try:
> This works:
>
> void f(std::unordered_map<int, int>::const_iterator) {}
> void g(std::unordered_map<int, int>::iterator it)
> {
> f(static_cast<std::unordered_map<int, int>::const_iterator>(it));
> }

Sorry, that is not what I meant.

Let me rewrite:

void f(std::unordered_map<int, int>::const_iterator) {}

template <typename ForwardIterator>
void g(ForwardIterator it)
{
f(std::make_const(it));
}

void h()
{
std::unordered_map<int, int> m;
g(m.begin());
}

Please write std::make_const such that the code above works.

> Granted it is not trivial to implement std::make_const_iterator so that it
> deduces the type to cast to, but I think disregarding implementation for
> one second that this just points out how useful this feature would be if
> g() needed a const_iterator for whatever reason, exactly because a
> const_iterator is not a const iterator.

Please give us a couple of those "whatever reasons". Let's say at least 5
distinct use-cases.

[Matthew Woehlke]

On 2017-07-12 02:27, Thiago Macieira wrote:
> void f(std::unordered_map<int, int>::const_iterator) {}
>
> template <typename ForwardIterator>
> void g(ForwardIterator it)
> {
> f(std::make_const(it));
> }
>
> void h()
> {
> std::unordered_map<int, int> m;
> g(m.begin());
> }
>
> Please write std::make_const such that the code above works.

template <typename Key, typename Value>
auto make_const(
std::__detail::_Node_iterator<std::pair<const Key, Value>,
false, false> iter)
-> std::__detail::_Node_const_iterator<std::pair<const Key, Value>,
false, false>
{
return iter;
}

...?

Yeah, you need ugly partial specializations / overloads that depend on
implementation details... so what? At worst, there needs to be a type
trait to derive the const_iterator type given the iterator type, or
something along those lines. That doesn't seem fatal...

--
Matthew