------=_Part_5285_27809195.1369796101339
Content-Type: text/plain; charset=ISO-8859-1

Ref.:
- N3662: Dynamic arrays
- N3686: Traversable arguments for container constructors and methods,
wording revision 3

While reading the later proposal, it was not clear to me if it is proposing
to add a constructor taking a traversable to the dynarray class (my guess
is that both proposals evolved in parallel without much knowledge of each
other). In fact, the proposal adds requirements to all sequence containers,
and dynarray *is *a sequence container.

A dynarray requires a known size to be constructed. There is a reason why
dynarray does not provide a constructor taking a pair of iterators: it is
because the constructor would need to call std::distance to know the size
and it could result in *linear time* (depending on the container). Such an
implicit behavior should not be provided. Fair enough.

So I guess the same could be said about a constructor taking a range; there
should not be a constructor taking a range because such a constructor would
just delegate to the constructor taking an iterator pair.

Since dynarray is going to be widely used (I personally know a lot of code
which will be able to benefit from using it instead of other containers
such as std::vector), it would be very unfortunate not to provide a
constructor for it that would take a range.

Maybe we could be less restrictive and provide such a constructor  (as well
as a constructor taking an iterator pair). But we could still at least
restrict it to iterators for which std::distance could be evaluated in *constant
time*. Of course, there would need to be something in iterator_traits to
determine if std::distance could be evaluated in constant time (unless
there is already a way to evaluate it that I am not thinking about).

list<int> my_vec;
vector<int> my_list;
dynarray<int> from_list{my_list}; // error: distance cannot be evaluated in
constant time for list<int>::iterator
dynarray<int> from_vec{my_vec}; // OK

Your thoughts?

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



------=_Part_5285_27809195.1369796101339
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<span style=3D"font-family: arial; font-size: small;">Ref.:</span><div styl=
e=3D"font-family: arial; font-size: small;">- N3662: Dynamic arrays<br></di=
v><div style=3D"font-family: arial; font-size: small;">- N3686: Traversable=
 arguments for container constructors and methods, wording revision 3</div>=
<div style=3D"font-family: arial; font-size: small;"><br></div><div style=
=3D"font-family: arial; font-size: small;">While reading the later proposal=
, it was not clear to me if it is proposing to add a constructor taking a t=
raversable to the dynarray class (my guess is that both proposals evolved i=
n parallel without much knowledge of each other). In fact, the proposal add=
s requirements to all sequence containers, and dynarray <i>is </i>a sequenc=
e container.</div><div style=3D"font-family: arial; font-size: small;"><br>=
</div><div style=3D"font-family: arial; font-size: small;">A dynarray requi=
res a known size to be constructed. There is a reason why dynarray does not=
 provide a constructor taking a pair of iterators: it is because the constr=
uctor would need to call std::distance to know the size and it could result=
 in <i>linear time</i> (depending on the container). Such an implicit behav=
ior should not be provided. Fair enough.</div><div style=3D"font-family: ar=
ial; font-size: small;"><br></div><div style=3D"font-family: arial; font-si=
ze: small;">So I guess the same could be said about a constructor taking a =
range; there should not be a constructor taking a range because such a cons=
tructor would just delegate to the constructor taking an iterator pair.</di=
v><div style=3D"font-family: arial; font-size: small;"><br></div><div style=
=3D"font-family: arial; font-size: small;">Since dynarray is going to be wi=
dely used (I personally know a lot of code which will be able to benefit fr=
om using it instead of other containers such as std::vector), it would be v=
ery unfortunate not to provide a constructor for it that would take a range=
..</div><div style=3D"font-family: arial; font-size: small;"><br></div><div =
style=3D"font-family: arial; font-size: small;">Maybe we could be less rest=
rictive and provide such a constructor &nbsp;(as well as a constructor taki=
ng an iterator pair). But we could still at least restrict it to iterators =
for which std::distance could be evaluated in <i>constant time</i>. Of cour=
se, there would need to be something in iterator_traits to determine if std=
::distance could be evaluated in constant time (unless there is already a w=
ay to evaluate it that I am not thinking about).</div><div style=3D"font-fa=
mily: arial; font-size: small;"><br></div><div class=3D"prettyprint" style=
=3D"background-color: rgb(250, 250, 250); border: 1px solid rgb(187, 187, 1=
87); word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"subp=
rettyprint"><span style=3D"color: #000;" class=3D"styled-by-prettify">list<=
/span><span style=3D"color: #080;" class=3D"styled-by-prettify">&lt;int&gt;=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> my_vec</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"><br>vector</span><span=
 style=3D"color: #080;" class=3D"styled-by-prettify">&lt;int&gt;</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> my_list</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br>dynarray</span><span style=
=3D"color: #080;" class=3D"styled-by-prettify">&lt;int&gt;</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> from_list</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify">my_list</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">};</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> </span><span style=3D"color: #800;" class=3D"s=
tyled-by-prettify">// error: distance cannot be evaluated in constant time =
for list&lt;int&gt;::iterator</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br>dynarray</span><span style=3D"color: #080;" class=3D=
"styled-by-prettify">&lt;int&gt;</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> from_vec</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">my_vec</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">};</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> </span><span style=3D"color: #800;" class=3D"styled-by-prettify">// OK<=
/span></div></code></div><div style=3D"font-family: arial; font-size: small=
;"><br></div><div style=3D"font-family: arial; font-size: small;">Your thou=
ghts?</div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

------=_Part_5285_27809195.1369796101339--

.

On 5/28/13, Alex B <devalexb@gmail.com> wrote:
> Ref.:
> - N3662: Dynamic arrays
> - N3686: Traversable arguments for container constructors and
> methods, wording revision 3
>
> While reading the later proposal, it was not clear to me if
> it is proposing to add a constructor taking a traversable to
> the dynarray class (my guess is that both proposals evolved
> in parallel without much knowledge of each other). In fact,
> the proposal adds requirements to all sequence containers, and
> dynarray *is *a sequence container.

It is true that I was not aware of N3686.

> A dynarray requires a known size to be constructed. There is a
> reason why dynarray does not provide a constructor taking a pair
> of iterators: it is because the constructor would need to call
> std::distance to know the size and it could result in *linear time*
> (depending on the container). Such an implicit behavior should
> not be provided. Fair enough.
>
> So I guess the same could be said about a constructor taking a
> range; there should not be a constructor taking a range because
> such a constructor would just delegate to the constructor taking
> an iterator pair.
>
> Since dynarray is going to be widely used (I personally know a
> lot of code which will be able to benefit from using it instead of
> other containers such as std::vector), it would be very unfortunate
> not to provide a constructor for it that would take a range.
>
> Maybe we could be less restrictive and provide such a constructor
> (as well as a constructor taking an iterator pair). But we could
> still at least restrict it to iterators for which std::distance
> could be evaluated in *constant time*. Of course, there would need
> to be something in iterator_traits to determine if std::distance
> could be evaluated in constant time (unless there is already a
> way to evaluate it that I am not thinking about).
>
> list<int> my_vec;
> vector<int> my_list;
> dynarray<int> from_list{my_list}; // error: distance cannot be
> // evaluated in constant time for list<int>::iterator
> dynarray<int> from_vec{my_vec}; // OK
>
> Your thoughts?

That looks like a good plan to me.  The error message might be a
bit obscure due to sfinae.

--
Lawrence Crowl

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

2013/5/29 Alex B <devalexb@gmail.com>:
> Ref.:
> - N3662: Dynamic arrays
> - N3686: Traversable arguments for container constructors and methods,
> wording revision 3
>
> While reading the later proposal, it was not clear to me if it is proposing
> to add a constructor taking a traversable to the dynarray class (my guess is
> that both proposals evolved in parallel without much knowledge of each
> other). In fact, the proposal adds requirements to all sequence containers,
> and dynarray is a sequence container.
>
> A dynarray requires a known size to be constructed. There is a reason why
> dynarray does not provide a constructor taking a pair of iterators: it is
> because the constructor would need to call std::distance to know the size
> and it could result in linear time (depending on the container). Such an
> implicit behavior should not be provided. Fair enough.

Yes, you make a good point.

> So I guess the same could be said about a constructor taking a range; there
> should not be a constructor taking a range because such a constructor would
> just delegate to the constructor taking an iterator pair.
>
> Since dynarray is going to be widely used (I personally know a lot of code
> which will be able to benefit from using it instead of other containers such
> as std::vector), it would be very unfortunate not to provide a constructor
> for it that would take a range.
>
> Maybe we could be less restrictive and provide such a constructor  (as well
> as a constructor taking an iterator pair). But we could still at least
> restrict it to iterators for which std::distance could be evaluated in
> constant time. Of course, there would need to be something in
> iterator_traits to determine if std::distance could be evaluated in constant
> time (unless there is already a way to evaluate it that I am not thinking
> about).

I think we could sfinae-constrain on category
std::random_access_iterator_tag (we could make the wording a bit more
friendly and allow for convertibility to
std::random_access_iterator_tag).

I also think that we should follow the sfinae-friendly approach of
result_of/allocator_traits and should ensure that iterator_traits
become a sfinae-friendly primary template definition.

- Daniel

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

--089e01494176eac32104dde15d0c
Content-Type: text/plain; charset=ISO-8859-1

> I also think that we should follow the sfinae-friendly approach of
> result_of/allocator_traits and should ensure that iterator_traits
> become a sfinae-friendly primary template definition.
>

Could you elaborate a bit more about what you consider sfinae-friendly? Do
you mean to add member types to iterator_traits, such as
iterator_traits<T>::is_random_access_iterator ?

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



--089e01494176eac32104dde15d0c
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><div class=3D"gmail_quote">=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
I also think that we should follow the sfinae-friendly approach of<br>
result_of/allocator_traits and should ensure that iterator_traits<br>
become a sfinae-friendly primary template definition.<br></blockquote><div>=
<br></div><div style>Could you elaborate a bit more about what you consider=
 sfinae-friendly? Do you mean to add member types to iterator_traits, such =
as iterator_traits&lt;T&gt;::is_random_access_iterator ?</div>
</div></div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

--089e01494176eac32104dde15d0c--

.

2013/5/29 Alex B <devalexb@gmail.com>:
>
>> I also think that we should follow the sfinae-friendly approach of
>> result_of/allocator_traits and should ensure that iterator_traits
>> become a sfinae-friendly primary template definition.
>
> Could you elaborate a bit more about what you consider sfinae-friendly? Do
> you mean to add member types to iterator_traits, such as
> iterator_traits<T>::is_random_access_iterator ?

No, I mean that the instantiation of the primary template - currently
specified as

template<class Iterator>
struct iterator_traits {
  typedef typename Iterator::difference_type difference_type;
  typedef typename Iterator::value_type value_type;
  typedef typename Iterator::pointer pointer;
  typedef typename Iterator::reference reference;
  typedef typename Iterator::iterator_category iterator_category;
};

will give a sfinae-friendly behaviour when instantiated for types that
don't have these typedefs. Remember that there exists some
compiler-freedom to instantiate declarations of an overload set to
find the best one. This could trigger ill-formed code during the
attempt to instantiate a sfinae-protected member such as

template <class InputIterator>
dynarray(InputIterator first, InputIterator last);

based on some iterator_traits-characteristics.

The solution would be that the primary template does not attempt to
define any member typedef where the corresponding definition would not
exist. For e.g. std::iterator_traits<int> the definition would be
completely empty.

- Daniel

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

> A dynarray requires a known size to be constructed. There is a
> reason why dynarray does not provide a constructor taking a
> pair of iterators: it is because the constructor would need to
> call std::distance to know the size and it could result in
> linear time (depending on the container).

I guess I'm missing something, but a constructor taking a range has to
be linear in the length of the range (be it a random access range), so
the comlexity won't change even if std::distance takes linear time.
So, in my understanding, two passes instead of one on the range
(for dynarray constructor) only forbids the use of input iterators.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

2013/5/30 Rafael Fourquet <fourquet.d@gmail.com>:
>> A dynarray requires a known size to be constructed. There is a
>> reason why dynarray does not provide a constructor taking a
>> pair of iterators: it is because the constructor would need to
>> call std::distance to know the size and it could result in
>> linear time (depending on the container).
>
> I guess I'm missing something, but a constructor taking a range has to
> be linear in the length of the range (be it a random access range), so
> the comlexity won't change even if std::distance takes linear time.
> So, in my understanding, two passes instead of one on the range
> (for dynarray constructor) only forbids the use of input iterators.

That is correct.

- Daniel

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

--001a11c36dae38329904ddfa1cc3
Content-Type: text/plain; charset=ISO-8859-1

I guess if we strictly look at what is possible to implement, indeed the
requirement should be ForwardIterator, which is less restrictive than
BidirectionalIterator. I suppose that the intent of the writers of the
proposal was mainly to avoid two passes because a lot of users won't expect
it (unless I'm wrong, it would be the first container doing it).

Indeed, if we strictly look at the complexity level, doing two passes
doesn't change anything; 2 times linear remains linear. However, concretely
it could result in twice the time taken to execute this constructor (in the
worst case scenario). For some people, it will mater (even if the overall
complexity level is the same) because it will be far from obvious to the
average user.

But I admit that I am not among those caring much about this 'performance
penalty' of doing 2 passes. My goal was to find a compromise that wouldn't
harm anybody because I thought there was a consensus about avoiding it. I
would personally find it better to have the most unrestricted requirements
so that we could have the following uniform behavior (expected from most
users): a standard container (including dynarray) can always be constructed
from *any* other standard container (either with a pair of iterators or
with a range as suggested by the other proposal). And to achieve it, I
would not mind doing two passes for iterators other than random access
iterators. I personally think the benefits of using a dynarray in such a
situation where you need to copy the content of another container/range far
outweighs the penalty of doing two passes (assuming the dynarray will most
probably use memory from the stack instead of the heap).

All that being said, maybe the authors of the dynarray paper could share
what was their own reasoning about not providing the said constructor?

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



--001a11c36dae38329904ddfa1cc3
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I guess if we strictly look at what is possible to impleme=
nt, indeed the requirement should be ForwardIterator, which is less restric=
tive than BidirectionalIterator. I suppose that the intent of the writers o=
f the proposal was mainly to avoid two passes because a lot of users won&#3=
9;t expect it (unless I&#39;m wrong, it would be the first container doing =
it).

<div><br></div><div>Indeed, if we strictly look at the complexity level, do=
ing two passes doesn&#39;t change anything; 2 times linear remains linear. =
However, concretely it could result in twice the time taken to execute this=
 constructor (in the worst case scenario). For some people, it will mater (=
even if the overall complexity level is the same) because it will be far fr=
om obvious to the average user.</div>



<div><br></div><div>But I admit that I am not among those caring much about=
 this &#39;performance penalty&#39; of doing 2 passes. My goal was to find =
a compromise that wouldn&#39;t harm anybody because I thought there was a c=
onsensus about avoiding it. I would personally find it better to have the m=
ost unrestricted requirements so that we could have the following uniform b=
ehavior (expected from most users): a standard container (including dynarra=
y) can always be constructed from <i>any</i>=A0other standard container (ei=
ther with a pair of iterators or with a range as suggested by the other pro=
posal). And to achieve it, I would not mind doing two passes for iterators =
other than random access iterators. I personally think the benefits of usin=
g a dynarray in such a situation where you need to copy the content of anot=
her container/range far outweighs the penalty of doing two passes (assuming=
 the dynarray will most probably use memory from the stack instead of the h=
eap).</div>
<div><br></div><div style>All that being said, maybe the authors of the dyn=
array paper could share what was their own reasoning about not providing th=
e said constructor?</div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

--001a11c36dae38329904ddfa1cc3--

.

2013/5/31 Alex B <devalexb@gmail.com>:
> I guess if we strictly look at what is possible to implement, indeed the
> requirement should be ForwardIterator, which is less restrictive than
> BidirectionalIterator. I suppose that the intent of the writers of the
> proposal was mainly to avoid two passes because a lot of users won't expect
> it (unless I'm wrong, it would be the first container doing it).

I agree that ForwardIterator should be feasible.

> Indeed, if we strictly look at the complexity level, doing two passes
> doesn't change anything; 2 times linear remains linear. However, concretely
> it could result in twice the time taken to execute this constructor (in the
> worst case scenario). For some people, it will mater (even if the overall
> complexity level is the same) because it will be far from obvious to the
> average user.
>
> But I admit that I am not among those caring much about this 'performance
> penalty' of doing 2 passes. My goal was to find a compromise that wouldn't
> harm anybody because I thought there was a consensus about avoiding it. I
> would personally find it better to have the most unrestricted requirements
> so that we could have the following uniform behavior (expected from most
> users): a standard container (including dynarray) can always be constructed
> from any other standard container (either with a pair of iterators or with a
> range as suggested by the other proposal). And to achieve it, I would not
> mind doing two passes for iterators other than random access iterators.

Neither would I.

> I
> personally think the benefits of using a dynarray in such a situation where
> you need to copy the content of another container/range far outweighs the
> penalty of doing two passes (assuming the dynarray will most probably use
> memory from the stack instead of the heap).

Agreed.

- Daniel

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

------=_Part_211_23845995.1370003217761
Content-Type: text/plain; charset=ISO-8859-1

I think there's no reason why InputIterator should not be acceptable. It
would just basically require always allocating on the heap as a result. The
question is whether that's a justifiable tradeoff.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



------=_Part_211_23845995.1370003217761
Content-Type: text/html; charset=ISO-8859-1

I think there's no reason why InputIterator should not be acceptable. It would just basically require always allocating on the heap as a result. The question is whether that's a justifiable tradeoff.

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en">http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en</a>.<br />
&nbsp;<br />
&nbsp;<br />

------=_Part_211_23845995.1370003217761--

.

------=_Part_641_24069824.1370005162451
Content-Type: text/plain; charset=ISO-8859-1

On Friday, May 31, 2013 5:26:57 AM UTC-7, DeadMG wrote:
>
> I think there's no reason why InputIterator should not be acceptable. It
> would just basically require always allocating on the heap as a result. The
> question is whether that's a justifiable tradeoff.


Agreed. Especially since `dynarray` provides absolutely no guarantees for
when it's going to heap allocate vs. stack allocate.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



------=_Part_641_24069824.1370005162451
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Friday, May 31, 2013 5:26:57 AM UTC-7, DeadMG wrote:<blockquote class=3D=
"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc s=
olid;padding-left: 1ex;">I think there's no reason why InputIterator should=
 not be acceptable. It would just basically require always allocating on th=
e heap as a result. The question is whether that's a justifiable tradeoff.<=
/blockquote><div><br>Agreed. Especially since `dynarray` provides absolutel=
y no guarantees for when it's going to heap allocate vs. stack allocate.<br=
></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

------=_Part_641_24069824.1370005162451--

.

--089e0158c3020a4db304de03663a
Content-Type: text/plain; charset=ISO-8859-1

Good point. Well, you are guaranteed that the allocation will be on the
heap in some situations (where it would not be possible at all to allocate
on the stack). That would just be one more of those situations (and only
for strict InputIterators which are not ForwardIterators). So I tend to
agree as well.


On Fri, May 31, 2013 at 8:59 AM, Nicol Bolas <jmckesson@gmail.com> wrote:

> On Friday, May 31, 2013 5:26:57 AM UTC-7, DeadMG wrote:
>>
>> I think there's no reason why InputIterator should not be acceptable. It
>> would just basically require always allocating on the heap as a result. The
>> question is whether that's a justifiable tradeoff.
>
>
> Agreed. Especially since `dynarray` provides absolutely no guarantees for
> when it's going to heap allocate vs. stack allocate.
>
> --
>
> ---
> 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/zh9HX07F1hk/unsubscribe?hl=en
> .
> 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-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
>
>
>

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



--089e0158c3020a4db304de03663a
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Good point. Well, you are guaranteed that the allocation w=
ill be on the heap in some situations (where it would not be possible at al=
l to allocate on the stack). That would just be one more of those situation=
s (and only for strict InputIterators which are not ForwardIterators). So I=
 tend to agree as well.</div>
<div class=3D"gmail_extra"><br><br><div class=3D"gmail_quote">On Fri, May 3=
1, 2013 at 8:59 AM, Nicol Bolas <span dir=3D"ltr">&lt;<a href=3D"mailto:jmc=
kesson@gmail.com" target=3D"_blank">jmckesson@gmail.com</a>&gt;</span> wrot=
e:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im">On Friday, May 31, 2013 5:=
26:57 AM UTC-7, DeadMG wrote:<blockquote class=3D"gmail_quote" style=3D"mar=
gin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex">
I think there&#39;s no reason why InputIterator should not be acceptable. I=
t would just basically require always allocating on the heap as a result. T=
he question is whether that&#39;s a justifiable tradeoff.</blockquote></div=
>
<div><br>Agreed. Especially since `dynarray` provides absolutely no guarant=
ees for when it&#39;s going to heap allocate vs. stack allocate.<br></div><=
div class=3D"HOEnZb"><div class=3D"h5">

<p></p>

-- <br>
=A0<br>
--- <br>
You received this message because you are subscribed to a topic in the Goog=
le Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this topic, visit <a href=3D"https://groups.google.com/=
a/isocpp.org/d/topic/std-proposals/zh9HX07F1hk/unsubscribe?hl=3Den" target=
=3D"_blank">https://groups.google.com/a/isocpp.org/d/topic/std-proposals/zh=
9HX07F1hk/unsubscribe?hl=3Den</a>.<br>

To unsubscribe from this group and all its topics, send an email to <a href=
=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D"_blank">std-pr=
oposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den" target=3D"_blank">http://groups.google.com/a/isocpp=
..org/group/std-proposals/?hl=3Den</a>.<br>
=A0<br>
=A0<br>
</div></div></blockquote></div><br></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

--089e0158c3020a4db304de03663a--

.

> But I admit that I am not among those caring much about this 'performance
> penalty' of doing 2 passes. My goal was to find a compromise that wouldn't
> harm anybody because I thought there was a consensus about avoiding it. I
> would personally find it better to have the most unrestricted requirements
> so that we could have the following uniform behavior (expected from most
> users): a standard container (including dynarray) can always be constructed
> from any other standard container (either with a pair of iterators or with a
> range as suggested by the other proposal). And to achieve it, I would not
> mind doing two passes for iterators other than random access iterators.

Yes... but wouldn't it be better if the constructor was overloaded to
also accept an optional length? For example to avoid the first pass
over a list of which I can know the length in O(1).
It would be useful if (future) std ranges could be optionally equipped
with a length member function (as is the case for the D language) or
equivalent.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

------=_Part_73_30998429.1370013124296
Content-Type: text/plain; charset=ISO-8859-1


>
> Yes... but wouldn't it be better if the constructor was overloaded to
> also accept an optional length? For example to avoid the first pass
> over a list of which I can know the length in O(1).
>

So you mean a constructor that would take one (instead of two)
InputIterator and a size? Personally I am not against the idea; it gives
more flexibility and more optimization opportunities. But it would have to
be added to all standard containers for uniformity. Other containers could
also benefit from having this overload; for example a vector could call
reserve in its constructor if it knows the size.

But because it concerns all containers, it would deserve its own proposal.


> It would be useful if (future) std ranges could be optionally equipped
> with a length member function (as is the case for the D language) or
> equivalent.


Indeed. For standard containers, I could easily imagine the following set
of constructors (I allowed myself to use constraints but it could be done
with sfinae):

template <class T, ...>
class container
{
   ...
public:
   ...

   // This is what we currently have
   template <InputIterator Iter>
   container(Iter first, Iter, last);

   // Overload for performance (we can do two passes on ForwardIterators)
   template <ForwardIterator Iter>
   container(Iter first, Iter, last);

   // If we already have the size, this one is even better
   template <InputIterator Iter>
   container(Iter first, iterator_traits<Iter>::difference_type count);

   // Constructor taking traversable would just delegate to constructor
taking iterators
   template <Traversable Trav>
   container(Trav&& trav) : container{trav.begin(), trav.end()} {}

   // Even better if the traversable has knowledge of its size
   template <TraversableWithSize Trav>
   container(Trav&& trav) : container{trav.begin(), trav.size()} {}

   ...
};




--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



------=_Part_73_30998429.1370013124296
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; borde=
r-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style=
: solid; padding-left: 1ex;"><div class=3D"im" style=3D"color: rgb(80, 0, 8=
0);"><span style=3D"color: rgb(34, 34, 34);">Yes... but wouldn't it be bett=
er if the constructor was overloaded to</span><br></div>also accept an opti=
onal length? For example to avoid the first pass<br>over a list of which I =
can know the length in O(1).<br></blockquote><div><br></div><div>So you mea=
n a constructor that would take one (instead of two) InputIterator and a si=
ze? Personally I am not against the idea; it gives more flexibility and mor=
e optimization opportunities. But it would have to be added to all standard=
 containers for uniformity. Other containers could also benefit from having=
 this overload; for example a vector could call reserve in its constructor =
if it knows the size.</div><div><br></div><div>But because it concerns all =
containers, it would deserve its own proposal.</div><div>&nbsp;</div><block=
quote class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; border-left=
-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: soli=
d; padding-left: 1ex;"><span style=3D"font-family: arial; font-size: small;=
">It would be useful if (future) std ranges could be optionally equipped</s=
pan><br style=3D"font-family: arial; font-size: small;"><span style=3D"font=
-family: arial; font-size: small;">with a length member function (as is the=
 case for the D language) or</span><br style=3D"font-family: arial; font-si=
ze: small;"><span style=3D"font-family: arial; font-size: small;">equivalen=
t.</span></blockquote><div><br></div><div>Indeed. For standard containers, =
I could easily imagine the following set of constructors (I allowed myself =
to use constraints but it could be done with sfinae):</div><div><br></div><=
div><div class=3D"prettyprint" style=3D"background-color: rgb(250, 250, 250=
); border: 1px solid rgb(187, 187, 187); word-wrap: break-word;"><code clas=
s=3D"prettyprint"><div class=3D"subprettyprint"><font color=3D"#660066"><sp=
an style=3D"color: #008;" class=3D"styled-by-prettify">template</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color=
: #008;" class=3D"styled-by-prettify">class</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">...&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify">cl=
ass</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> contai=
ner<br></span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &=
nbsp;</span><span style=3D"color: #660;" class=3D"styled-by-prettify">...</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><=
span style=3D"color: #008;" class=3D"styled-by-prettify">public</span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">:</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">...</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"><br><br>&nbsp; &nbsp;</span></f=
ont><span style=3D"color: rgb(136, 0, 0);"><span style=3D"color: #800;" cla=
ss=3D"styled-by-prettify">// This is what we currently have</span></span><f=
ont color=3D"#660066"><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"><br>&nbsp; &nbsp;</span><span style=3D"color: #008;" class=3D"styled-b=
y-prettify">template</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>&lt;</span><span style=3D"color: #606;" class=3D"styled-by-prettify">Input=
Iterator</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #606;" class=3D"styled-by-prettify">Iter</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;contai=
ner</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span=
><span style=3D"color: #606;" class=3D"styled-by-prettify">Iter</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> first</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;=
" class=3D"styled-by-prettify">Iter</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pre=
ttify">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>);</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br><br=
>&nbsp; &nbsp;</span></font><span style=3D"color: rgb(136, 0, 0);"><span st=
yle=3D"color: #800;" class=3D"styled-by-prettify">// Overload for performan=
ce (we can do two passes on ForwardIterators)</span></span><font color=3D"#=
660066"><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp=
; &nbsp;</span><span style=3D"color: #008;" class=3D"styled-by-prettify">te=
mplate</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><s=
pan style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span =
style=3D"color: #606;" class=3D"styled-by-prettify">Iter</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;container</span><=
/font><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><sp=
an style=3D"color: #606;" class=3D"styled-by-prettify">Iter</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> first</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;" =
class=3D"styled-by-prettify">Iter</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pret=
tify">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
);</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></sp=
an><font color=3D"#660066"><span style=3D"color: #000;" class=3D"styled-by-=
prettify"><br>&nbsp; &nbsp;</span><span style=3D"color: #800;" class=3D"sty=
led-by-prettify">// If we already have the size, this one is even better</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span></=
font><span style=3D"color: #000;" class=3D"styled-by-prettify">&nbsp; &nbsp=
;</span><span style=3D"color: #008;" class=3D"styled-by-prettify">template<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span sty=
le=3D"color: #606;" class=3D"styled-by-prettify">InputIterator</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"=
color: #606;" class=3D"styled-by-prettify">Iter</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;container</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color=
: #606;" class=3D"styled-by-prettify">Iter</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> first</span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> iterator_traits</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">&lt;</span><font color=3D"#660066"><span style=3D"=
color: #606;" class=3D"styled-by-prettify">Iter</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">&gt;::</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify">difference_type count</span></font><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br><br>&nbsp; &nbsp;</span><spa=
n style=3D"color: #800;" class=3D"styled-by-prettify">// Constructor taking=
 traversable would just delegate to constructor taking iterators</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;</sp=
an><font color=3D"#660066"><span style=3D"color: #008;" class=3D"styled-by-=
prettify">template</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">&=
lt;</span><span style=3D"color: #606;" class=3D"styled-by-prettify">Travers=
able</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </spa=
n><span style=3D"color: #606;" class=3D"styled-by-prettify">Trav</span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"><br></span></font><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">&nbsp; &nbsp;container</sp=
an><font color=3D"#666600"><span style=3D"color: #660;" class=3D"styled-by-=
prettify">(</span><span style=3D"color: #606;" class=3D"styled-by-prettify"=
>Trav</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&amp;=
&amp;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> trav=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">:</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> container</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">trav</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">.</span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">begin</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">(),</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> trav</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.<=
/span><span style=3D"color: #008;" class=3D"styled-by-prettify">end</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">()}</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">{}</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"><br></span></font><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;</span><span style=3D"co=
lor: #800;" class=3D"styled-by-prettify">// Even better if the traversable =
has knowledge of its size</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>&nbsp; &nbsp;</span><span style=3D"color: #008;" class=
=3D"styled-by-prettify">template</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">&lt;</span><span style=3D"color: #606;" class=3D"styled-by-p=
rettify">TraversableWithSize</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-p=
rettify">Trav</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>&nbsp; &nbsp;container</span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">(</span><span style=3D"color: #606;" class=3D"styled-by-pretti=
fy">Trav</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&a=
mp;&amp;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> t=
rav</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">:</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> container</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify">trav</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">.</span><span style=3D"color: #008;" class=3D"sty=
led-by-prettify">begin</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">(),</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> trav</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
..</span><span style=3D"color: #000;" class=3D"styled-by-prettify">size</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">()}</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">{}</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"><br><br>&nbsp; &nbsp;</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">...</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br></span><font color=3D"#660066">=
<span style=3D"color: #660;" class=3D"styled-by-prettify">};</span></font><=
/div></code></div><br><br></div><div>&nbsp;</div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

------=_Part_73_30998429.1370013124296--

.

On 5/30/13, Alex B <devalexb@gmail.com> wrote:
> I guess if we strictly look at what is possible to implement,
> indeed the requirement should be ForwardIterator, which is
> less restrictive than BidirectionalIterator. I suppose that the
> intent of the writers of the proposal was mainly to avoid two
> passes because a lot of users won't expect it (unless I'm wrong,
> it would be the first container doing it).
>
> Indeed, if we strictly look at the complexity level, doing
> two passes doesn't change anything; 2 times linear remains
> linear. However, concretely it could result in twice the time taken
> to execute this constructor (in the worst case scenario). For some
> people, it will mater (even if the overall complexity level is
> the same) because it will be far from obvious to the average user.
>
> But I admit that I am not among those caring much about this
> 'performance penalty' of doing 2 passes. My goal was to find a
> compromise that wouldn't harm anybody because I thought there was a
> consensus about avoiding it. I would personally find it better to
> have the most unrestricted requirements so that we could have the
> following uniform behavior (expected from most users): a standard
> container (including dynarray) can always be constructed from *any*
> other standard container (either with a pair of iterators or with
> a range as suggested by the other proposal). And to achieve it,
> I would not mind doing two passes for iterators other than random
> access iterators. I personally think the benefits of using a
> dynarray in such a situation where you need to copy the content
> of another container/range far outweighs the penalty of doing two
> passes (assuming the dynarray will most probably use memory from
> the stack instead of the heap).
>
> All that being said, maybe the authors of the dynarray paper
> could share what was their own reasoning about not providing the
> said constructor?

As an author, my intent was to not put in anything that I wasn't
sure was necessary.  The paper entering the Bristol meeting had
the approval of EWG, so I was not going to add anything that was
not necessary.  The omission was in no way a rejection of that
constructor, but instead an incremental approach.  It is much easer
to expand an interface than it is to reduce it.

An O(n) size computation seems reasonable to me.

--
Lawrence Crowl

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

On 5/31/13, Alex B <devalexb@gmail.com> wrote:
> On May 31, 2013 Nicol Bolas <jmckesson@gmail.com> wrote:
> > On Friday, May 31, 2013 5:26:57 AM UTC-7, DeadMG wrote:
> > > I think there's no reason why InputIterator should not be
> > > acceptable. It would just basically require always allocating
> > > on the heap as a result.  The question is whether that's a
> > > justifiable tradeoff.
> >
> > Agreed. Especially since `dynarray` provides absolutely no
> > guarantees for when it's going to heap allocate vs. stack
> > allocate.
>
> Good point. Well, you are guaranteed that the allocation will be
> on the heap in some situations (where it would not be possible
> at all to allocate on the stack). That would just be one more of
> those situations (and only for strict InputIterators which are
> not ForwardIterators). So I tend to agree as well.

I don't think an input iterator works because you need to know the
size before you can allocate the space, even when allocating on
the heap.  Input iterators do not have that property.

--
Lawrence Crowl

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

On 5/31/13, Alex B <devalexb@gmail.com> wrote:
> > Yes... but wouldn't it be better if the constructor was
> > overloaded to also accept an optional length? For example to
> > avoid the first pass over a list of which I can know the length
> > in O(1).
>
> So you mean a constructor that would take one (instead of two)
> InputIterator and a size? Personally I am not against the idea; it
> gives more flexibility and more optimization opportunities. But
> it would have to be added to all standard containers for
> uniformity. Other containers could also benefit from having
> this overload; for example a vector could call reserve in its
> constructor if it knows the size.

Note that if you have both a length argument and a pair of iterators
(aka range), then you have a redundant specification.  What happens
if the two specifications are inconsistent?

> But because it concerns all containers, it would deserve its
> own proposal.

Agreed, if for no other reason than the above point.

> > It would be useful if (future) std ranges could be optionally equipped
> > with a length member function (as is the case for the D language) or
> > equivalent.
>
> Indeed. For standard containers, I could easily imagine the
> following set of constructors (I allowed myself to use constraints
> but it could be done with sfinae):
>
> template <class T, ...>
> class container
> {
>    ...
> public:
>    ...
>
>    // This is what we currently have
>    template <InputIterator Iter>
>    container(Iter first, Iter, last);
>
>    // Overload for performance (we can do two passes on ForwardIterators)
>    template <ForwardIterator Iter>
>    container(Iter first, Iter, last);
>
>    // If we already have the size, this one is even better
>    template <InputIterator Iter>
>    container(Iter first, iterator_traits<Iter>::difference_type count);
>
>    // Constructor taking traversable would just delegate to constructor taking iterators
>    template <Traversable Trav>
>    container(Trav&& trav) : container{trav.begin(), trav.end()} {}
>
>    // Even better if the traversable has knowledge of its size
>    template <TraversableWithSize Trav>
>    container(Trav&& trav) : container{trav.begin(), trav.size()} {}
>
>    ...
> };

--
Lawrence Crowl

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

2013/6/1 Lawrence Crowl <crowl@googlers.com>:
> On 5/31/13, Alex B <devalexb@gmail.com> wrote:
>> On May 31, 2013 Nicol Bolas <jmckesson@gmail.com> wrote:
>> > On Friday, May 31, 2013 5:26:57 AM UTC-7, DeadMG wrote:
>> > > I think there's no reason why InputIterator should not be
>> > > acceptable. It would just basically require always allocating
>> > > on the heap as a result.  The question is whether that's a
>> > > justifiable tradeoff.
>> >
>> > Agreed. Especially since `dynarray` provides absolutely no
>> > guarantees for when it's going to heap allocate vs. stack
>> > allocate.
>>
>> Good point. Well, you are guaranteed that the allocation will be
>> on the heap in some situations (where it would not be possible
>> at all to allocate on the stack). That would just be one more of
>> those situations (and only for strict InputIterators which are
>> not ForwardIterators). So I tend to agree as well.
>
> I don't think an input iterator works because you need to know the
> size before you can allocate the space, even when allocating on
> the heap.  Input iterators do not have that property.

My understanding of the proposal to allow for input iterators here is
similar to the requirement that dynarray objects of non-automatic
storage duration are required to be supported. In both cases the
implementation (ideally) has to follow two different allocation
strategies internally.

I don't think that we should add support for input iterators from
begin with, it would be a sufficiently good start to restrict support
to forward iterators (or even random access iterators) and to consider
relaxation of the constraints in the future.

- Daniel

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.

------=_Part_535_4670838.1370285297681
Content-Type: text/plain; charset=ISO-8859-1

Op vrijdag 31 mei 2013 15:47:18 UTC+2 schreef Rafael Fourquet het volgende:

> > But I admit that I am not among those caring much about this
> 'performance
> > penalty' of doing 2 passes. My goal was to find a compromise that
> wouldn't
> > harm anybody because I thought there was a consensus about avoiding it.
> I
> > would personally find it better to have the most unrestricted
> requirements
> > so that we could have the following uniform behavior (expected from most
> > users): a standard container (including dynarray) can always be
> constructed
> > from any other standard container (either with a pair of iterators or
> with a
> > range as suggested by the other proposal). And to achieve it, I would
> not
> > mind doing two passes for iterators other than random access iterators.
>
> Yes... but wouldn't it be better if the constructor was overloaded to
> also accept an optional length? For example to avoid the first pass
> over a list of which I can know the length in O(1).
> It would be useful if (future) std ranges could be optionally equipped
> with a length member function (as is the case for the D language) or
> equivalent.
>

Wouldn't the dynarray constructor be able to take advantage of such a
size() property directly, without manually having to call and pass it as an
extra argument?

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



------=_Part_535_4670838.1370285297681
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Op vrijdag 31 mei 2013 15:47:18 UTC+2 schreef Rafael Fourquet het volgende:=
<br><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex=
;border-left: 1px #ccc solid;padding-left: 1ex;">&gt; But I admit that I am=
 not among those caring much about this 'performance
<br>&gt; penalty' of doing 2 passes. My goal was to find a compromise that =
wouldn't
<br>&gt; harm anybody because I thought there was a consensus about avoidin=
g it. I
<br>&gt; would personally find it better to have the most unrestricted requ=
irements
<br>&gt; so that we could have the following uniform behavior (expected fro=
m most
<br>&gt; users): a standard container (including dynarray) can always be co=
nstructed
<br>&gt; from any other standard container (either with a pair of iterators=
 or with a
<br>&gt; range as suggested by the other proposal). And to achieve it, I wo=
uld not
<br>&gt; mind doing two passes for iterators other than random access itera=
tors.
<br>
<br>Yes... but wouldn't it be better if the constructor was overloaded to
<br>also accept an optional length? For example to avoid the first pass
<br>over a list of which I can know the length in O(1).
<br>It would be useful if (future) std ranges could be optionally equipped
<br>with a length member function (as is the case for the D language) or
<br>equivalent.
<br></blockquote><div><br></div><div>Wouldn't the dynarray constructor be a=
ble to take advantage of such a size() property directly, without manually =
having to call and pass it as an extra argument?&nbsp;</div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

------=_Part_535_4670838.1370285297681--

.

--e89a8f83a659510b8504de45354e
Content-Type: text/plain; charset=ISO-8859-1

I think Rafael meant to first have a constructor taking an *iterator* and a
size (not a range and a size).

Later on, when adding ranges, you could have a constructor taking a range
(and only a range) that could be implemented by simply forwarding
range.begin() and range.size() to the first constructor.

Of course, we are assuming here that ranges will have a size() method, but
it will not be true for all ranges.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



--e89a8f83a659510b8504de45354e
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I think Rafael meant to first have a constructor taki=
ng an <i style=3D"font-weight:bold">iterator</i>=A0and a size (not a range =
and a size).<br></div><div><br></div><div style>Later on, when adding range=
s, you could have a constructor taking a range (and only a range) that coul=
d be implemented by simply forwarding range.begin() and range.size() to the=
 first constructor.</div>
<div style><br></div><div style>Of course, we are assuming here that ranges=
 will have a size() method, but it will not be true for all ranges.</div></=
div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
&nbsp;<br />
&nbsp;<br />

--e89a8f83a659510b8504de45354e--

.

> I think Rafael meant to first have a constructor taking an iterator and a
> size (not a range and a size).
>
> Later on, when adding ranges, you could have a constructor taking a range
> (and only a range) that could be implemented by simply forwarding
> range.begin() and range.size() to the first constructor.

Thanks Alex, that's what I meant!

> Of course, we are assuming here that ranges will have a size() method, but
> it will not be true for all ranges.

Yes, having .size() would be like a trait for ranges (as there are
traits for iterators), and algorithms could take advantage of it when
present.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.



.