------=_Part_476_1064165724.1489864402529
Content-Type: multipart/alternative;
 boundary="----=_Part_477_337917633.1489864402530"

------=_Part_477_337917633.1489864402530
Content-Type: text/plain; charset=UTF-8

The array is the most fundamental and important data structure in computer
science. If a problem can be efficiently solved with arrays
there is not likely to be a more optimal solution on modern hardware.

The C++ standard library provides only 2 array types. A static and fixed
size std::array<T,N> and a dynamic and growable std::vector<T,N>.

These are a good foundation, but there are a lot of different array
variations.
In performance critical code, I've found all of these to be very useful.

I'd really like to see these in the standard and am considering writing a
paper. Many of them are already being discussed elsewhere or have active
proposals. Here is the rough outline of the idea. A real paper would need a
lot more detail and examples of course.

The different types of arrays you can create are split across a few
dimensions. All of them have trade-offs.

One dimension is the storage policy:

static - The size is determined at compile time. When you can set compile
time upper bounds on storage, you can construct tightly packed
data structures with no pointer indirections. That's about the best you
could hope for in terms of cache efficiency. The limitation of course
is the fixed size. What do you do if the application wants to use more?
Silently truncate? Throw an error?

dynamic - The size is determined at runtime and allocated on the heap
(maybe stack via magic tricks like alloca()). This is of course more
flexible for all the obvious reasons, and can be safety created locally on
the stack without worrying about using too much memory.
Dyanmic arrays can also be moved efficiently O(1) by swapping pointers,
whereas with the static array you're forced to move all of
individual members O(N) in sequence. The downside are the costs of
allocation and deallocation. Also if you have structures with lots
of different vectors, you'll be risking cache misses and as you do random
access memory hops when accessing the different buffers.

sbo - The small buffer optimization where you have some small amount of
static memory and fallback to dynamic allocation when the
capacity exceeds that amount. This is a great compromise, especially if you
have a system where rare outliers in memory use need to
be handled and its acceptable to pay a penality for it. Its also not hard
to add to some instrumentation and tune the static sizes after
the fact so that for the 80 part of the 80 / 20 rule, your application runs
super fast and doesn't allocate memory.

Another is whether the storage is fixed or growable.

Growable Storage - This is std::vector. It is the most convenient and
default option. It always works and the memory is laid out
linearly so normal access is super fast. Growable means in theory your
application can possibly run out of memory and crash. This is not
such a bad thing if the limits are sufficiently high and you are not
concerned about or are otherwise protected from malicious denial of
service attacks. It also leaves room for hardware memory upgrades to
improve the capabilities of the
application. Growable arrays require that you have different concepts of
"size" and "capacity", which means you need to store more
data in the array object to keep track of this information. The automatic
resizing while amortized is still expensive when it happens, and
if you have a real-time application that can't handle random slowdowns like
this then automatically growable arrays may be off the table.

Fixed Storage - Fixed size storage is less flexible but offers some
performance benefits. Mostly in that you don't need to keep track of a
capacity, you can also choose to encode the size at compile time
(std::array). Since the size is fixed, dynamic memory allocation can be
done once and done exactly for the space requested.

Fixed size arrays can also store non-copyable/non-movable elements, whereas
growable arrays require the objects can be relocated or copied.

One big limitation fixed storage has right now is that as soon as you
construct the array itself, all of the elements have to be constructed too.
If your T's are moveable, its easy to just default construct the array, and
then loop through and carefully construct the real data on the side and
then move it in.

If T's default constructor is complex and not inline, this default and then
move approach can be less efficient. Its also impossible if T is not
movable or copyable.

For non-movable types, fixed arrays make it difficult to pass different
constructor arguments, or even call different constructors for each
individual element.
I once rigged up a technique for doing this using lambdas and iterators,
but it wasn't pretty.


Finally, the last dimension is ownership.

Owns the data - Pretty much all array types actually own and manage the
underlying buffer.

Does not own the data - This is array_view, which I'll describe more later.

So given all of these dimensions, how can we combine them to create useful
types. Here are the ones I've used:

Note that template arguments are:
T - the type of the data
N - a compile time size
A - an allocator

*vector<T,A> - Dynamic and Growable*

The standard bread and butter of C++. Any implementation will require 3
data members for the data pointer, size, and capacity. It can be
implemented using a pointer and 2 ints, or 3 pointers. On 64 bit platforms,
std::vector will likely be 24 bytes. If you know you will never need to
store more than 4 billion elements (an extremely reasonable assumption),
you can shave it down to 16 bytes using a T* and 2 uint32_t's.
Unfortunately, std::vector doesn't provide a way for us to switch on this
optimization.

There's also the choice of the growth factor. 2 being the common naive one
and 1.5 providing better underlying memory reuse.

Finally, theres also the discussion of realloc() that keeps popping up, and
whether or not a standard version of realloc() would make the vector resize
operation more efficient.

*static_vector<T,N> - Static capacity, growable*

This data structure has the exact same interface as std::vector. The
difference is that the capacity is set at compile time and not stored
within the object. If you try to insert an element once the capacity is
full the container will throw an exception instead of allocating.

This one is less common. You get the cache benefits of a compile time
capacity, which means you can embed this object directly in other data
structures without pointer indirections. Its essentially a std::array<T,N>,
with an extra counter embedded inside to keep track of how many objects are
"active".

The resulting size of this data structure will be sizeof(T) * N + the size
of a 64 bit or 32 bit size counter, with additional padding as needed.

One alternative to this is using an array<T,N> and having some state of T
represent whether or not the object is active.

A very common example is an array<T*,N> where the index of the first null
pointer indicates the "size". This is actually faster to iterate in a for
loop than static_vector<T,N> since you can do only a single null check. You
don't need to store a counter, but you may need to store a dummy sentinel
at the end to terminate the loop. The downside is that the size() operation
becomes O(N) instead of O(1).

For other cases, you may need to store an additional bool to say whether
its "alive" or not. In terms of memory usage, you trade off the cost of a
single counter vs storing additional "alive" state in your T object.
Because of padding, storing an additional flag can actually be very
expensive in terms of memory use and cache efficiency. For non-pod complex
types, it also requires that all of them are "constructed" all the time,
which may not be ideal.


*small_vector<T,N,A> - Sbo capacity, growable.*

There have been a lot of other threads talking about small_vector and
examples of its use in the wild. Examples include llvm, google, facebook,
game engines, and more.. So I'm not going to go into huge detail here. In
C++11, std::string already uses the sbo storage policy.

small_vector is a probabilistic bet. If most of the time your maximum size
is <= N, you have the potential to gain large performance benefits. In
particular a vector<small_vector<T,N>> will end up being a single linear
buffer. If you end up exceeding N most of the time, that sbo space just
becomes wasted memory and a simple vector would be faster.

Any small_vector implementation must allow for N to be configurable by the
user. Unlike a string, vector has a nearly infinite set of use cases and
performance critical applications will need to tune it carefully.

*array<T,N> - Static and Fixed (also T[N])*

The fixed size statically allocated array. You get all of the benefits of
the memory layout along with the limitations of fixed storage mentioned
before.

The size is of course sizeof(T) * N.

Not much to say here, we've all been using this for decades.


*dyn_array<T,A> - Dynamic and Fixed*

Not to be confused with the earlier attempt at creating a magic array type
with stack allocation.
Of all of the new types mentioned here, after small_vector, this is the
most important one missing from the standard.

Essentially, this is like a std::vector without the insert, push_back,
erase, methods. Not having these capabilities seems like a limitation, but
its also a strength.

* The underlying memory store can be allocated exactly and only once during
construction. vector implementations may speculatively allocate more,
betting that you will call push_back() later. Unless you use reserve(),
inserting a bunch of things into a vector will result in multiple memory
allocations and deallocations. Slowing down your application and
fragmenting your heap.
* Smaller, more cache friendly footprint. You only need a single pointer
and a size, so on 64bit systems, sizeof(dyn_array<T,A>) == 16. On 32 bit
systems, the size is only 8.
* Works with non-movable types, with the construction caveats I mentioned
before.
* You can store const T, and still be able to move the array but not copy
it.
* Application correctness: If the use case demands an array that cannot be
resized, dyn_array provides exactly that. It becomes impossible for users
to break this contract.

Compared to std::array, the advantages are:
* Determine the size at runtime
* O(1) move operations
* No worry about blowing out stack space with large allocations.

Finally, unlike array, dyn_array still has the ability to be resized at
runtime. Its just that unlike vector, it has to be done manually be the
user. In my implementations of this, I've just allowed copy and/or move
operations to change the size. You could also argue that including the
resize() method still makes sense.

auto a = dyn_array<int>(5, 0); //Initialize to {0, 0, 0, 0, 0}
a = dyn_array<int>(2, 1); //Change to {1, 1}

Finally, if you need some flexibility you can also create your data with a
std::vector, and then move it into a dyn_array. If these types are using
the same allocator, we should allow them to be movable to each other

//Do setup
std::vector<T> temp;
temp.emplace_back(stuff..);
temp.emplace_back(more complicated stuff...);

//All done, now do permanent storage.
auto permanent = dyn_array<T>(std::move(temp));


*array_view<T> - Non-owning view*

There have already been several proposals for this. Personally I love
array_view and use it all the time.

The best part is that it can be used with all of the above array types.
This allows you to write generic functions which accept any kind of array.
Like string_view, it allows generic code without the complexity and compile
time overhead of using templates. Bjarne Stroustrup's GSL library has this
and they call it "span<T>".

The standard 1-dimensional array_view requires only a begin and end pointer.

Theres also discussion of how to handle multiple dimensions. I can have a
flat buffer of memory and construct a multi-dimension view over it.
While multi-dimensional views can be great for numeric code, I find that
the single dimensional array_view is an absolutely essential tool. Again 80
/ 20 principle.

For every dimension you add, you need to include additional state to store
it, either in memory at runtime or at compile time. I'm leaving this
subject alone for now as the various array_view proposals are trying to
tackle it.

*static_array_view<T,N> - Non-owning view with static size.*

This one seems a bit odd and obscure. Essentially this object stores only a
single pointer and has a compile time configured size.

Why would you possibly want to use this thing? Personally I invented this
one time because there was some generic code I wanted to optimize for
single element case and multi-element case.

The generic code was written for array_view<T> and looped over it several
times doing all kinds of nasty business logic. This code was absolutely
performance critical. It was extremely common that we would pass in an
array_view with size 1, with some scenarios never using the multi-element
capability at all.

Writing 2 versions of the code was a maintenance nightmare I didn't want to
deal with. Instead of writing all of this code twice, once with loops and
again without them I simply templated it.

The multi-element case templated to array_view<T>. The single-element case
templated to static_array_view<T,1>. In the static case, the compiler was
smart enough to remove all of the loops and compile the code down as if I
had written it in the single element.


All of these array types are not impossible to write on your own but its
tedious and complicated. It takes a lot of time to write all of the access
methods and then you must unit test it hard as its easy to have a bug in
one of them that your application happens to not use often or ever.

Would you use any of these types in your code?

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/642f3c7d-c20f-4dd2-bfd2-b0c9c326f9b5%40isocpp.org.

------=_Part_477_337917633.1489864402530
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">The array is the most fundamental and important data struc=
ture in computer science. If a problem can be efficiently solved with array=
s<br>there is not likely to be a more optimal solution on modern hardware.<=
br><br>The C++ standard library provides only 2 array types. A static and f=
ixed size std::array&lt;T,N&gt; and a dynamic and growable std::vector&lt;T=
,N&gt;.<br><br>These are a good foundation, but there are a lot of differen=
t array variations.<br>In performance critical code, I&#39;ve found all of =
these to be very useful.<br><br>I&#39;d really like to see these in the sta=
ndard and am considering writing a paper. Many of them are already being di=
scussed elsewhere or have active proposals. Here is the rough outline of th=
e idea. A real paper would need a lot more detail and examples of course.<b=
r><br>The different types of arrays you can create are split across a few d=
imensions. All of them have trade-offs.<br><br>One dimension is the storage=
 policy:<br><br>static - The size is determined at compile time. When you c=
an set compile time upper bounds on storage, you can construct tightly pack=
ed<br>data structures with no pointer indirections. That&#39;s about the be=
st you could hope for in terms of cache efficiency. The limitation of cours=
e<br>is the fixed size. What do you do if the application wants to use more=
? Silently truncate? Throw an error?<br><br>dynamic - The size is determine=
d at runtime and allocated on the heap (maybe stack via magic tricks like a=
lloca()). This is of course more<br>flexible for all the obvious reasons, a=
nd can be safety created locally on the stack without worrying about using =
too much memory.<br>Dyanmic arrays can also be moved efficiently O(1) by sw=
apping pointers, whereas with the static array you&#39;re forced to move al=
l of <br>individual members O(N) in sequence. The downside are the costs of=
 allocation and deallocation. Also if you have structures with lots<br>of d=
ifferent vectors, you&#39;ll be risking cache misses and as you do random a=
ccess memory hops when accessing the different buffers.<br><br>sbo - The sm=
all buffer optimization where you have some small amount of static memory a=
nd fallback to dynamic allocation when the<br>capacity exceeds that amount.=
 This is a great compromise, especially if you have a system where rare out=
liers in memory use need to<br>be handled and its acceptable to pay a penal=
ity for it. Its also not hard to add to some instrumentation and tune the s=
tatic sizes after<br>the fact so that for the 80 part of the 80 / 20 rule, =
your application runs super fast and doesn&#39;t allocate memory.<br><br>An=
other is whether the storage is fixed or growable.<br><br>Growable Storage =
- This is std::vector. It is the most convenient and default option. It alw=
ays works and the memory is laid out<br>linearly so normal access is super =
fast. Growable means in theory your application can possibly run out of mem=
ory and crash. This is not<br>such a bad thing if the limits are sufficient=
ly high and you are not concerned about or are otherwise protected from mal=
icious denial of<br>service attacks. It also leaves room for hardware memor=
y upgrades to improve the capabilities of the<br>application. Growable arra=
ys require that you have different concepts of &quot;size&quot; and &quot;c=
apacity&quot;, which means you need to store more<br>data in the array obje=
ct to keep track of this information. The automatic resizing while amortize=
d is still expensive when it happens, and<br>if you have a real-time applic=
ation that can&#39;t handle random slowdowns like this then automatically g=
rowable arrays may be off the table.<br><br>Fixed Storage - Fixed size stor=
age is less flexible but offers some performance benefits. Mostly in that y=
ou don&#39;t need to keep track of a<br>capacity, you can also choose to en=
code the size at compile time (std::array). Since the size is fixed, dynami=
c memory allocation can be<br>done once and done exactly for the space requ=
ested.<br><br>Fixed size arrays can also store non-copyable/non-movable ele=
ments, whereas growable arrays require the objects can be relocated or copi=
ed.<br><br>One big limitation fixed storage has right now is that as soon a=
s you construct the array itself, all of the elements have to be constructe=
d too.<br>If your T&#39;s are moveable, its easy to just default construct =
the array, and then loop through and carefully construct the real data on t=
he side and then move it in.<br><br>If T&#39;s default constructor is compl=
ex and not inline, this default and then move approach can be less efficien=
t. Its also impossible if T is not movable or copyable.<br><br>For non-mova=
ble types, fixed arrays make it difficult to pass different constructor arg=
uments, or even call different constructors for each individual element.<br=
>I once rigged up a technique for doing this using lambdas and iterators, b=
ut it wasn&#39;t pretty.<br><br><br>Finally, the last dimension is ownershi=
p.<br><br>Owns the data - Pretty much all array types actually own and mana=
ge the underlying buffer.<br><br>Does not own the data - This is array_view=
, which I&#39;ll describe more later.<br><br>So given all of these dimensio=
ns, how can we combine them to create useful types. Here are the ones I&#39=
;ve used:<br><br>Note that template arguments are:<br>T - the type of the d=
ata<br>N - a compile time size<br>A - an allocator<br><br><b>vector&lt;T,A&=
gt; - Dynamic and Growable</b><br><br>The standard bread and butter of C++.=
 Any implementation will require 3 data members for the data pointer, size,=
 and capacity. It can be implemented using a pointer and 2 ints, or 3 point=
ers. On 64 bit platforms, std::vector will likely be 24 bytes. If you know =
you will never need to store more than 4 billion elements (an extremely rea=
sonable assumption), you can shave it down to 16 bytes using a T* and 2 uin=
t32_t&#39;s. Unfortunately, std::vector doesn&#39;t provide a way for us to=
 switch on this optimization.<br><br>There&#39;s also the choice of the gro=
wth factor. 2 being the common naive one and 1.5 providing better underlyin=
g memory reuse.<br><br>Finally, theres also the discussion of realloc() tha=
t keeps popping up, and whether or not a standard version of realloc() woul=
d make the vector resize operation more efficient.<br><b><br>static_vector&=
lt;T,N&gt; - Static capacity, growable</b><br><br>This data structure has t=
he exact same interface as std::vector. The difference is that the capacity=
 is set at compile time and not stored within the object. If you try to ins=
ert an element once the capacity is full the container will throw an except=
ion instead of allocating.<br><br>This one is less common. You get the cach=
e benefits of a compile time capacity, which means you can embed this objec=
t directly in other data structures without pointer indirections. Its essen=
tially a std::array&lt;T,N&gt;, with an extra counter embedded inside to ke=
ep track of how many objects are &quot;active&quot;.<br><br>The resulting s=
ize of this data structure will be sizeof(T) * N + the size of a 64 bit or =
32 bit size counter, with additional padding as needed.<br><br>One alternat=
ive to this is using an array&lt;T,N&gt; and having some state of T represe=
nt whether or not the object is active. <br><br>A very common example is an=
 array&lt;T*,N&gt; where the index of the first null pointer indicates the =
&quot;size&quot;. This is actually faster to iterate in a for loop than sta=
tic_vector&lt;T,N&gt; since you can do only a single null check. You don&#3=
9;t need to store a counter, but you may need to store a dummy sentinel at =
the end to terminate the loop. The downside is that the size() operation be=
comes O(N) instead of O(1).<br><br>For other cases, you may need to store a=
n additional bool to say whether its &quot;alive&quot; or not. In terms of =
memory usage, you trade off the cost of a single counter vs=20
storing additional &quot;alive&quot; state in your T object. Because of pad=
ding,=20
storing an additional flag can actually be very expensive in terms of=20
memory use and cache efficiency. For non-pod complex types, it also require=
s=20
that all of them are &quot;constructed&quot; all the time, which may not be=
 ideal.<br><br><b><br>small_vector&lt;T,N,A&gt; - Sbo capacity, growable.</=
b><br><br>There have been a lot of other threads talking about small_vector=
 and examples of its use in the wild. Examples include llvm, google, facebo=
ok, game engines, and more.. So I&#39;m not going to go into huge detail he=
re. In C++11, std::string already uses the sbo storage policy.<br><br>small=
_vector is a probabilistic bet. If most of the time your maximum size is &l=
t;=3D N, you have the potential to gain large performance benefits. In part=
icular a vector&lt;small_vector&lt;T,N&gt;&gt; will end up being a single l=
inear buffer. If you end up exceeding N most of the time, that sbo space ju=
st becomes wasted memory and a simple vector would be faster.<br><br>Any sm=
all_vector implementation must allow for N to be configurable by the user. =
Unlike a string, vector has a nearly infinite set of use cases and performa=
nce critical applications will need to tune it carefully. <br><b><br>array&=
lt;T,N&gt; - Static and Fixed (also T[N])</b><br><br>The fixed size statica=
lly allocated array. You get all of the benefits of the memory layout along=
 with the limitations of fixed storage mentioned before.<br><br>The size is=
 of course sizeof(T) * N.<br><br>Not much to say here, we&#39;ve all been u=
sing this for decades.<br><br><br><b>dyn_array&lt;T,A&gt; - Dynamic and Fix=
ed</b><br><br>Not to be confused with the earlier attempt at creating a mag=
ic array type with stack allocation.<br>Of all of the new types mentioned h=
ere, after small_vector, this is the most important one missing from the st=
andard.<br><br>Essentially, this is like a std::vector without the insert, =
push_back, erase, methods. Not having these capabilities seems like a limit=
ation, but its also a strength.<br><br>* The underlying memory store can be=
 allocated exactly and only once during construction. vector implementation=
s may speculatively allocate more, betting that you will call push_back() l=
ater. Unless you use reserve(), inserting a bunch of things into a vector w=
ill result in multiple memory allocations and deallocations. Slowing down y=
our application and fragmenting your heap.<br>* Smaller, more cache friendl=
y footprint. You only need a single pointer and a size, so on 64bit systems=
, sizeof(dyn_array&lt;T,A&gt;) =3D=3D 16. On 32 bit systems, the size is on=
ly 8.<br>* Works with non-movable types, with the construction caveats I me=
ntioned before.<br>* You can store const T, and still be able to move the a=
rray but not copy it.<br>* Application correctness: If the use case demands=
 an array that cannot be resized, dyn_array provides exactly that. It becom=
es impossible for users to break this contract.<br><br>Compared to std::arr=
ay, the advantages are:<br>* Determine the size at runtime<br>* O(1) move o=
perations<br>* No worry about blowing out stack space with large allocation=
s.<br><br>Finally, unlike array, dyn_array still has the ability to be resi=
zed at runtime. Its just that unlike vector, it has to be done manually be =
the user. In my implementations of this, I&#39;ve just allowed copy and/or =
move operations to change the size. You could also argue that including the=
 resize() method still makes sense.<br><br><div style=3D"background-color: =
rgb(250, 250, 250); border-color: rgb(187, 187, 187); border-style: solid; =
border-width: 1px; overflow-wrap: break-word;" class=3D"prettyprint"><code =
class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #=
008;" class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> a </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> dyn_array</span><span style=3D"color: #080;" class=3D"sty=
led-by-prettify">&lt;int&gt;</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">(</span><span style=3D"color: #066;" class=3D"styled-by-p=
rettify">5</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: #066;" class=3D"styled-by-prettify">0</span><span styl=
e=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: #800;=
" class=3D"styled-by-prettify">//Initialize to {0, 0, 0, 0, 0}</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br>a </span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> dyn_array</span><span style=3D"co=
lor: #080;" class=3D"styled-by-prettify">&lt;int&gt;</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #06=
6;" class=3D"styled-by-prettify">2</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: #066;" class=3D"styled-by-pret=
tify">1</span><span style=3D"color: #660;" class=3D"styled-by-prettify">);<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><sp=
an style=3D"color: #800;" class=3D"styled-by-prettify">//Change to {1, 1}</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><=
/div></code></div><br>Finally, if you need some flexibility you can also cr=
eate your data with a std::vector, and then move it into a dyn_array. If th=
ese types are using the same allocator, we should allow them to be movable =
to each other<br><br><div style=3D"background-color: rgb(250, 250, 250); bo=
rder-color: rgb(187, 187, 187); border-style: solid; border-width: 1px; ove=
rflow-wrap: break-word;" class=3D"prettyprint"><code class=3D"prettyprint">=
<div class=3D"subprettyprint"><span style=3D"color: #800;" class=3D"styled-=
by-prettify">//Do setup</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"><br>std</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
">vector</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&l=
t;</span><span style=3D"color: #000;" class=3D"styled-by-prettify">T</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> temp</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>temp</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">.</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">emplace_back</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">stuff</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">..);</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"><br>temp</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">em=
place_back</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">more comp=
licated stuff</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">...);</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><b=
r><br></span><span style=3D"color: #800;" class=3D"styled-by-prettify">//Al=
l done, now do permanent storage.</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br></span><span style=3D"color: #008;" class=3D"st=
yled-by-prettify">auto</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> permanent </span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> dyn_array</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">&lt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;(</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">std</span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">move</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify">temp</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">));</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br></span></div></code></div><br><br><b>array_view&lt;T=
&gt; - Non-owning view</b><br><br>There have already been several proposals=
 for this. Personally I love array_view and use it all the time. <br><br>Th=
e best part is that it can be used with all of the above array types. This =
allows you to write generic functions which accept any kind of array. Like =
string_view, it allows generic code without the complexity and compile time=
 overhead of using templates. Bjarne Stroustrup&#39;s GSL library has this =
and they call it &quot;span&lt;T&gt;&quot;.<br><br>The standard 1-dimension=
al array_view requires only a begin and end pointer.<br><br>Theres also dis=
cussion of how to handle multiple dimensions. I can have a flat buffer of m=
emory and construct a multi-dimension view over it. <br>While multi-dimensi=
onal views can be great for numeric code, I find that the single dimensiona=
l array_view is an absolutely essential tool. Again 80 / 20 principle.<br><=
br>For every dimension you add, you need to include additional state to sto=
re it, either in memory at runtime or at compile time. I&#39;m leaving this=
 subject alone for now as the various array_view proposals are trying to ta=
ckle it.<br><b><br>static_array_view&lt;T,N&gt; - Non-owning view with stat=
ic size.</b><br><br>This one seems a bit odd and obscure. Essentially this =
object stores only a single pointer and has a compile time configured size.=
<br><br>Why would you possibly want to use this thing? Personally I invente=
d this one time because there was some generic code I wanted to optimize fo=
r single element case and multi-element case.<br><br>The generic code was w=
ritten for array_view&lt;T&gt; and looped over it several times doing all k=
inds of nasty business logic. This code was absolutely performance critical=
.. It was extremely common that we would pass in an array_view with size 1, =
with some scenarios never using the multi-element capability at all.<br><br=
>Writing 2 versions of the code was a maintenance nightmare I didn&#39;t wa=
nt to deal with. Instead of writing all of this code twice, once with loops=
 and again without them I simply templated it.<br><br>The multi-element cas=
e templated to array_view&lt;T&gt;. The single-element case templated to st=
atic_array_view&lt;T,1&gt;. In the static case, the compiler was smart enou=
gh to remove all of the loops and compile the code down as if I had written=
 it in the single element.<br><br><br>All of these array types are not impo=
ssible to write on your own but its tedious and complicated. It takes a lot=
 of time to write all of the access methods and then you must unit test it =
hard as its easy to have a bug in one of them that your application happens=
 to not use often or ever.<br><br>Would you use any of these types in your =
code?<br></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/642f3c7d-c20f-4dd2-bfd2-b0c9c326f9b5%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/642f3c7d-c20f-4dd2-bfd2-b0c9c326f9b5=
%40isocpp.org</a>.<br />

------=_Part_477_337917633.1489864402530--

------=_Part_476_1064165724.1489864402529--

.

------=_Part_664_693334507.1489871274110
Content-Type: multipart/alternative;
 boundary="----=_Part_665_875354401.1489871274110"

------=_Part_665_875354401.1489871274110
Content-Type: text/plain; charset=UTF-8



On Saturday, March 18, 2017 at 8:13:22 PM UTC+1, Matthew Fioravante wrote:
>
> The array is the most fundamental and important data structure in computer
> science. If a problem can be efficiently solved with arrays
> there is not likely to be a more optimal solution on modern hardware.
>
> The C++ standard library provides only 2 array types. A static and fixed
> size std::array<T,N> and a dynamic and growable std::vector<T,N>.
>
> These are a good foundation, but there are a lot of different array
> variations.
> In performance critical code, I've found all of these to be very useful.
>
> I'd really like to see these in the standard and am considering writing a
> paper. Many of them are already being discussed elsewhere or have active
> proposals. Here is the rough outline of the idea. A real paper would need a
> lot more detail and examples of course.
>
> The different types of arrays you can create are split across a few
> dimensions. All of them have trade-offs.
>
>
 Nicol Bolas suggest adding `omi_vector` that will be configurable by type
traits to change behavior as you see fit.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/0c29ca96-7552-414c-9425-f396f44cce23%40isocpp.org.

------=_Part_665_875354401.1489871274110
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Saturday, March 18, 2017 at 8:13:22 PM UTC+1, M=
atthew Fioravante wrote:<blockquote class=3D"gmail_quote" style=3D"margin: =
0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div d=
ir=3D"ltr">The array is the most fundamental and important data structure i=
n computer science. If a problem can be efficiently solved with arrays<br>t=
here is not likely to be a more optimal solution on modern hardware.<br><br=
>The C++ standard library provides only 2 array types. A static and fixed s=
ize std::array&lt;T,N&gt; and a dynamic and growable std::vector&lt;T,N&gt;=
..<br><br>These are a good foundation, but there are a lot of different arra=
y variations.<br>In performance critical code, I&#39;ve found all of these =
to be very useful.<br><br>I&#39;d really like to see these in the standard =
and am considering writing a paper. Many of them are already being discusse=
d elsewhere or have active proposals. Here is the rough outline of the idea=
.. A real paper would need a lot more detail and examples of course.<br><br>=
The different types of arrays you can create are split across a few dimensi=
ons. All of them have trade-offs.<br><br></div></blockquote><div>=C2=A0</di=
v><div>=C2=A0Nicol Bolas suggest adding `omi_vector` that will be configura=
ble by type traits to change behavior as you see fit.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/0c29ca96-7552-414c-9425-f396f44cce23%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/0c29ca96-7552-414c-9425-f396f44cce23=
%40isocpp.org</a>.<br />

------=_Part_665_875354401.1489871274110--

------=_Part_664_693334507.1489871274110--

.

------=_Part_2516_2017482649.1489872032602
Content-Type: multipart/alternative;
 boundary="----=_Part_2517_1540223572.1489872032602"

------=_Part_2517_1540223572.1489872032602
Content-Type: text/plain; charset=UTF-8



On Saturday, March 18, 2017 at 4:07:54 PM UTC-5, Marcin Jaczewski wrote:
>
>  Nicol Bolas suggest adding `omi_vector` that will be configurable by type
> traits to change behavior as you see fit.
>

That's a great idea. Especially if it also lets me adjust the size counters
to be uint32_t.

In that scenario, there are a few more configurations that to consider.

* Instead of storing runtime capacity, make it a function of size. One
example I used once to save space was making the capacity always the next
power of 2 of the size. Checking whether you need to resize requires only a
fast is power of 2 check.
* Sentinel arrays. Like the example I mentioned with std::array<T*,N>, make
the size an O(N) operation function of the elements. For most efficient
iteration, optionally require a permanent sentinel element at the end of
the array that cannot be overwritten.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/04daae5b-439e-46d7-95ee-3043bea0667b%40isocpp.org.

------=_Part_2517_1540223572.1489872032602
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Saturday, March 18, 2017 at 4:07:54 PM UTC-5, M=
arcin Jaczewski wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;=
margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">=C2=A0Nicol Bolas suggest adding `omi_vector` that will be configu=
rable by type traits to change behavior as you see fit.<br></div></blockquo=
te><div><br>That&#39;s a great idea. Especially if it also lets me adjust t=
he size counters to be uint32_t.<br><br>In that scenario, there are a few m=
ore configurations that to consider.<br><br>* Instead of storing runtime ca=
pacity, make it a function of size. One example I used once to save space w=
as making the capacity always the next power of 2 of the size. Checking whe=
ther you need to resize requires only a fast is power of 2 check.<br>* Sent=
inel arrays. Like the example I mentioned with std::array&lt;T*,N&gt;, make=
 the size an O(N) operation function of the elements. For most efficient it=
eration, optionally require a permanent sentinel element at the end of the =
array that cannot be overwritten.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/04daae5b-439e-46d7-95ee-3043bea0667b%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/04daae5b-439e-46d7-95ee-3043bea0667b=
%40isocpp.org</a>.<br />

------=_Part_2517_1540223572.1489872032602--

------=_Part_2516_2017482649.1489872032602--

.

On Sat, Mar 18, 2017 at 12:13:22PM -0700, Matthew Fioravante wrote:
> The array is the most fundamental and important data structure in computer
> science. If a problem can be efficiently solved with arrays
> there is not likely to be a more optimal solution on modern hardware.
>
> The C++ standard library provides only 2 array types. A static and fixed
> size std::array<T,N> and a dynamic and growable std::vector<T,N>.
>
> These are a good foundation, but there are a lot of different array
> variations.
> In performance critical code, I've found all of these to be very useful.
>
> I'd really like to see these in the standard and am considering writing a
> paper. Many of them are already being discussed elsewhere or have active
> proposals. Here is the rough outline of the idea. A real paper would need a
> lot more detail and examples of course.
>
> The different types of arrays you can create are split across a few
> dimensions. All of them have trade-offs.
>
> Another is whether the storage is fixed or growable.
>
> Growable Storage - This is std::vector. It is the most convenient and
> default option. It always works and the memory is laid out
> linearly so normal access is super fast. Growable means in theory your
> application can possibly run out of memory and crash. This is not
> such a bad thing if the limits are sufficiently high and you are not
> concerned about or are otherwise protected from malicious denial of
> service attacks. It also leaves room for hardware memory upgrades to
> improve the capabilities of the
> application. Growable arrays require that you have different concepts of
> "size" and "capacity", which means you need to store more
> data in the array object to keep track of this information. The automatic
> resizing while amortized is still expensive when it happens, and
> if you have a real-time application that can't handle random slowdowns like
> this then automatically growable arrays may be off the table.
>
> Fixed Storage - Fixed size storage is less flexible but offers some
> performance benefits. Mostly in that you don't need to keep track of a
> capacity, you can also choose to encode the size at compile time
> (std::array). Since the size is fixed, dynamic memory allocation can be
> done once and done exactly for the space requested.
>
> Fixed size arrays can also store non-copyable/non-movable elements, whereas
> growable arrays require the objects can be relocated or copied.

This is actuallly false, you can store non-movable objects in a growable
array, you just can't resize it while it is non-empty.

This means you have to use "reserve" prior to putting objects into it, but you
can still use it dynamically.

/MF

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170319190502.GB17057%40noemi.

.

------=_Part_1073_1587456389.1490042112424
Content-Type: multipart/alternative;
 boundary="----=_Part_1074_1391776633.1490042112424"

------=_Part_1074_1391776633.1490042112424
Content-Type: text/plain; charset=UTF-8

You may also like to consider existing proposals and LEWG's response to
them:

   - P0210r0
   <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0210r0.html>,
   a light-weight, compact dynamic array, by yours truly. Reaction: meh, too
   specific, not necessary.
   - P0274r0
   <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0274r0.pdf>,
   clump, a vector-like container with embedded storage, by Nevin. LEWG liked
   this one quite a bit I believe, though we haven't seen it since.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/aae31c67-d992-446a-bd92-fd9ab63cf310%40isocpp.org.

------=_Part_1074_1391776633.1490042112424
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">You may also like to consider existing proposals and LEWG&=
#39;s response to them:<div><ul><li><a href=3D"http://www.open-std.org/jtc1=
/sc22/wg21/docs/papers/2016/p0210r0.html">P0210r0</a>, a light-weight, comp=
act dynamic array, by yours truly. Reaction: meh, too specific, not necessa=
ry.</li><li><a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2=
016/p0274r0.pdf">P0274r0</a>, clump, a vector-like container with embedded =
storage, by Nevin. LEWG liked this one quite a bit I believe, though we hav=
en&#39;t seen it since.</li></ul></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/aae31c67-d992-446a-bd92-fd9ab63cf310%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/aae31c67-d992-446a-bd92-fd9ab63cf310=
%40isocpp.org</a>.<br />

------=_Part_1074_1391776633.1490042112424--

------=_Part_1073_1587456389.1490042112424--

.

------=_Part_883_254915065.1492144462374
Content-Type: text/plain; charset=UTF-8

I've often thought that a capacity constructor to vector would be nice (probably with a capacity_t tag or something). This would take the place of one of your vectors I think. Plus one for the shock vector!

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f01a71c2-02e6-4fe3-8602-c3dfb19077bc%40isocpp.org.

------=_Part_883_254915065.1492144462374--

.

------=_Part_1101_1833205480.1492144551588
Content-Type: text/plain; charset=UTF-8

I mean short or sbo vector not shock vector.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/59238645-c3d5-4282-86d8-b4044731f3cf%40isocpp.org.

------=_Part_1101_1833205480.1492144551588--

.

I don't know what a shock vector is, but I want one.

Sent=C2=A0from=C2=A0my=C2=A0BlackBerry=C2=A0portable=C2=A0Babbage=C2=A0Devi=
ce
=C2=A0 Original Message =C2=A0
From: 3dw4rd@verizon.net
Sent: Friday, April 14, 2017 12:35 AM
To: ISO C++ Standard - Future Proposals
Reply To: std-proposals@isocpp.org
Subject: [std-proposals] Add all useful array types to the standard library

I mean short or sbo vector not shock vector.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/59238645-c3d5-4282-86d8-b4044731f3cf%40isocpp.or=
g.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/20170414111554.5148754.67724.28881%40gmail.com.

.

Em sexta-feira, 14 de abril de 2017, =C3=A0s 04:15:54 PDT, Tony V E escreve=
u:
> I don't know what a shock vector is, but I want one.

A shock vector is what happens to a vector when you reply to mailing lists=
=20
with a phone.

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

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/12437571.3omJd9UHM2%40tjmaciei-mobl1.

.

------=_Part_1067_22435211.1492299223810
Content-Type: multipart/alternative;
 boundary="----=_Part_1068_106523784.1492299223810"

------=_Part_1068_106523784.1492299223810
Content-Type: text/plain; charset=UTF-8



> As a variant it would be possible to use different allocators to achieve
> these different results.


This could be done using these two allocators:

     FixedAllocator<T, N> // Has a fixed block to allocate from, part of
its own size.
     SooAllocator<T, N, A> // Has N elements inside and can also allocate
from the subordinate allocator A which defaults to the default allocator

To get all the variants we then use std::vector with one of these and to
get the dyn_array behaviour we also need a template class which allocates
one block from its allocator at construction time, lets call it DynArray
for now:

DynArray<T, std::allocator>               // Always allocate a heap block
DynArray<T, FixedAllocator<T, N>>  // Consumes N elements worth of memory
and allows up to N as the size constructor parameter.
DynArray<T, SooAllotactor<T, N>>   // Allocates on heap if requirement is
larger than N

This is sort of elegant as it allows composing the resizable behaviour
(DynArray or std::vector) freely with the different allocators, but there
are drawbacks:

- The types are more cumbersome to write out.
- For performance/size reasons DynArray and std.:vector may be better off
specialized for the different allocators. This reduces the terseness of the
code.

These drawbacks together may well cause the addition of type aliases for
"good" combinations which takes us back to the same old hariy naming
issue., and if each of these correspond to a specialized implementation,
what has actually been gained?

So my conclusion is that while it looked nice for a while this may not be a
better idea after all. But now that I wrote it down I can just as well send
it, maybe someone else gets a better idea out of this...

Bengt


--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/4b989332-5ff1-4321-a276-aff41d87a140%40isocpp.org.

------=_Part_1068_106523784.1492299223810
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;">As a variant it would be possible to use different allocators to achi=
eve these different results.</blockquote><div><br></div><div>This could be =
done using these two allocators:</div><div><br></div><div>=C2=A0 =C2=A0 =C2=
=A0FixedAllocator&lt;T, N&gt;<span class=3D"Apple-tab-span" style=3D"white-=
space: pre;">       </span>// Has a fixed block to allocate from, part of i=
ts own size.</div><div>=C2=A0 =C2=A0 =C2=A0SooAllocator&lt;T, N, A&gt;<span=
 class=3D"Apple-tab-span" style=3D"white-space:pre">      </span>// Has N e=
lements inside and can also allocate from the subordinate allocator A which=
 defaults to the default allocator</div><div><br></div><div>To get all the =
variants we then use std::vector with one of these and to get the dyn_array=
 behaviour we also need a template class which allocates one block from its=
 allocator at construction time, lets call it DynArray for now:</div><div><=
br></div><div>DynArray&lt;T, std::allocator&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 // Always allocate a heap block</div><div>DynArray&lt=
;T, FixedAllocator&lt;T, N&gt;&gt; =C2=A0// Consumes N elements worth of me=
mory and allows up to N as the size constructor parameter.</div><div>DynArr=
ay&lt;T, SooAllotactor&lt;T, N&gt;&gt; =C2=A0 // Allocates on heap if requi=
rement is larger than N</div><div><br></div><div>This is sort of elegant as=
 it allows composing the resizable behaviour (DynArray or std::vector) free=
ly with the different allocators, but there are drawbacks:</div><div><br></=
div><div>- The types are more cumbersome to write out.</div><div>- For perf=
ormance/size reasons DynArray and std.:vector may be better off specialized=
 for the different allocators. This reduces the terseness of the code.</div=
><div><br></div><div>These drawbacks together may well cause the addition o=
f type aliases for &quot;good&quot; combinations which takes us back to the=
 same old hariy naming issue., and if each of these correspond to a special=
ized implementation, what has actually been gained?</div><div><br></div><di=
v>So my conclusion is that while it looked nice for a while this may not be=
 a better idea after all. But now that I wrote it down I can just as well s=
end it, maybe someone else gets a better idea out of this...</div><div><br>=
</div><div>Bengt</div><div><br></div><div><br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/4b989332-5ff1-4321-a276-aff41d87a140%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/4b989332-5ff1-4321-a276-aff41d87a140=
%40isocpp.org</a>.<br />

------=_Part_1068_106523784.1492299223810--

------=_Part_1067_22435211.1492299223810--

.

------=_Part_3141_2029203755.1492310012043
Content-Type: multipart/alternative;
 boundary="----=_Part_3142_231726993.1492310012043"

------=_Part_3142_231726993.1492310012043
Content-Type: text/plain; charset=UTF-8

On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote:
>
>
>
>> As a variant it would be possible to use different allocators to achieve
>> these different results.
>
>
> This could be done using these two allocators:
>

No, it could not.

You can get *some* of the effect of it. But without partial specializations
of `vector` that explicitly have the desired properties, it becomes a big
kludge.

`FixedAllocator` cannot get rid of two now worthless pointers inside
`vector`. Neither can `SooAllocator` somehow create a union between the
pointers and the fixed block of elements.

Furthermore, `small_vector` and `static_vector` has fundamental behavioral
differences from `vector` which cannot merely be a matter of allocators.
Moving a `static_vector` into another `static_vector` will *always* invoke
`T`'s move constructor; for `vector`, it never will, no matter the
allocator. `small_vector` has different iterator invalidation behavior.

The current specification of `vector` doesn't allow these things. So if
you're going to force these things, and complicate the specification, it
would be much better to use a true parameterization of `vector`'s behavior,
rather than an allocator-based hack.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/a57fa2f7-6cb1-46ad-9e24-e4fd4fdfac6f%40isocpp.org.

------=_Part_3142_231726993.1492310012043
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gus=
tafsson wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0;margi=
n-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex">As a variant it w=
ould be possible to use different allocators to achieve these different res=
ults.</blockquote><div><br></div><div>This could be done using these two al=
locators:</div></div></blockquote><div><br>No, it could not.<br><br>You can=
 get <i>some</i> of the effect of it. But without partial specializations o=
f `vector` that explicitly have the desired properties, it becomes a big kl=
udge.<br><br>`FixedAllocator` cannot get rid of two now worthless pointers =
inside `vector`. Neither can `SooAllocator` somehow create a union between =
the pointers and the fixed block of elements.<br><br>Furthermore, `small_ve=
ctor` and `static_vector` has fundamental behavioral differences from `vect=
or` which cannot merely be a matter of allocators. Moving a `static_vector`=
 into another `static_vector` will <i>always</i> invoke `T`&#39;s move cons=
tructor; for `vector`, it never will, no matter the allocator. `small_vecto=
r` has different iterator invalidation behavior.<br><br>The current specifi=
cation of `vector` doesn&#39;t allow these things. So if you&#39;re going t=
o force these things, and complicate the specification, it would be much be=
tter to use a true parameterization of `vector`&#39;s behavior, rather than=
 an allocator-based hack.</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/a57fa2f7-6cb1-46ad-9e24-e4fd4fdfac6f%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/a57fa2f7-6cb1-46ad-9e24-e4fd4fdfac6f=
%40isocpp.org</a>.<br />

------=_Part_3142_231726993.1492310012043--

------=_Part_3141_2029203755.1492310012043--

.

------=_Part_423_792675218.1492442337061
Content-Type: multipart/alternative;
 boundary="----=_Part_424_284610512.1492442337061"

------=_Part_424_284610512.1492442337061
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable



Den s=C3=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 skrev Nicol Bolas:
>
> On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote:
>>
>> =20
>>
>>> As a variant it would be possible to use different allocators to achiev=
e=20
>>> these different results.
>>
>>
>> This could be done using these two allocators:
>>
>
> No, it could not.
>
> You can get *some* of the effect of it. But without partial=20
> specializations of `vector` that explicitly have the desired properties, =
it=20
> becomes a big kludge.
>
> `FixedAllocator` cannot get rid of two now worthless pointers inside=20
> `vector`. Neither can `SooAllocator` somehow create a union between the=
=20
> pointers and the fixed block of elements.
>
Well, I did write that the actual implementatation of vector would probably=
=20
be specialized for the different allocators as a QoI excercise.
=20

>
> Furthermore, `small_vector` and `static_vector` has fundamental behaviora=
l=20
> differences from `vector` which cannot merely be a matter of allocators.=
=20
> Moving a `static_vector` into another `static_vector` will *always*=20
> invoke `T`'s move constructor; for `vector`, it never will, no matter the=
=20
> allocator. `small_vector` has different iterator invalidation behavior.
>
Yes, this would be a somewhat valid concern, but is it so much harder to=20
know that a vector with a certain allocator will invalidate its iterators=
=20
at move assignment than that a container with a slighly different name (or=
=20
template parameters of other sorts than allocators) would?

I would be reluctant to rely on iterators outliving the move assignment of=
=20
their vector, but of course there is code out there that does. If such code=
=20
is templated on the container to use both solutions are still having the=20
same risk level. If such code is templated on the allocator but uses a=20
vector of the supplied allocator type then the allocator based solution=20
would maybe fail silently while the new-class solution would not be=20
applicable at all. This is a very small corner.
=20

>
> The current specification of `vector` doesn't allow these things. So if=
=20
> you're going to force these things, and complicate the specification, it=
=20
> would be much better to use a true parameterization of `vector`'s behavio=
r,=20
> rather than an allocator-based hack.
>
But unfortunately we can't get such true parameterisation unless we start=
=20
afresh with a new container name. I was basically just exploring the=20
possibility of avoiding having to have two names for the same basic type of=
=20
container where one is "better" and the other is "simpler".

As for your omi_vector, I guess it is similar to how Eigen handles its=20
configurable matrices. This is powerful but rather hard to set up the 6=20
template parameters so there are quite a few alias templates for common=20
cases. It would be good if you could post the specification of this class,=
=20
as google could not find it for me.=20
=20

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/d3aa4421-d095-4d6a-a323-ea13b3513e2a%40isocpp.or=
g.

------=_Part_424_284610512.1492442337061
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>Den s=C3=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 s=
krev Nicol Bolas:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr">On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote=
:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>=C2=A0</div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;borde=
r-left:1px #ccc solid;padding-left:1ex">As a variant it would be possible t=
o use different allocators to achieve these different results.</blockquote>=
<div><br></div><div>This could be done using these two allocators:</div></d=
iv></blockquote><div><br>No, it could not.<br><br>You can get <i>some</i> o=
f the effect of it. But without partial specializations of `vector` that ex=
plicitly have the desired properties, it becomes a big kludge.<br><br>`Fixe=
dAllocator` cannot get rid of two now worthless pointers inside `vector`. N=
either can `SooAllocator` somehow create a union between the pointers and t=
he fixed block of elements.<br></div></div></blockquote><div>Well, I did wr=
ite that the actual implementatation of vector would probably be specialize=
d for the different allocators as a QoI excercise.</div><div>=C2=A0</div><b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><br>Furthe=
rmore, `small_vector` and `static_vector` has fundamental behavioral differ=
ences from `vector` which cannot merely be a matter of allocators. Moving a=
 `static_vector` into another `static_vector` will <i>always</i> invoke `T`=
&#39;s move constructor; for `vector`, it never will, no matter the allocat=
or. `small_vector` has different iterator invalidation behavior.<br></div><=
/div></blockquote><div>Yes, this would be a somewhat valid concern, but is =
it so much harder to know that a vector with a certain allocator will inval=
idate its iterators at move assignment than that a container with a slighly=
 different name (or template parameters of other sorts than allocators) wou=
ld?</div><div><br></div><div>I would be reluctant to rely on iterators outl=
iving the move assignment of their vector, but of course there is code out =
there that does. If such code is templated on the container to use both sol=
utions are still having the same risk level. If such code is templated on t=
he allocator but uses a vector of the supplied allocator type then the allo=
cator based solution would maybe fail silently while the new-class solution=
 would not be applicable at all. This is a very small corner.</div><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: =
0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div=
><br>The current specification of `vector` doesn&#39;t allow these things. =
So if you&#39;re going to force these things, and complicate the specificat=
ion, it would be much better to use a true parameterization of `vector`&#39=
;s behavior, rather than an allocator-based hack.</div></div></blockquote><=
div>But unfortunately we can&#39;t get such true parameterisation unless we=
 start afresh with a new container name. I was basically just exploring the=
 possibility of avoiding having to have two names for the same basic type o=
f container where one is &quot;better&quot; and the other is &quot;simpler&=
quot;.</div><div><br></div><div>As for your omi_vector, I guess it is simil=
ar to how Eigen handles its configurable matrices. This is powerful but rat=
her hard to set up the 6 template parameters so there are quite a few alias=
 templates for common cases. It would be good if you could post the specifi=
cation of this class, as google could not find it for me.=C2=A0</div><div>=
=C2=A0</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/d3aa4421-d095-4d6a-a323-ea13b3513e2a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/d3aa4421-d095-4d6a-a323-ea13b3513e2a=
%40isocpp.org</a>.<br />

------=_Part_424_284610512.1492442337061--

------=_Part_423_792675218.1492442337061--

.

------=_Part_464_1422146456.1492444717791
Content-Type: multipart/alternative;
 boundary="----=_Part_465_236836064.1492444717792"

------=_Part_465_236836064.1492444717792
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable



On Sunday, March 19, 2017 at 2:05:06 PM UTC-5, Magnus Fromreide wrote:
>
> This is actuallly false, you can store non-movable objects in a growable=
=20
> array, you just can't resize it while it is non-empty.=20
>
> This means you have to use "reserve" prior to putting objects into it, bu=
t=20
> you=20
> can still use it dynamically.=20
>
> /MF=20


That doesn't play well with concepts. If I have a resizable vector, then at=
=20
compile time I might want to check that T is movable when I call push_back.=
=20
This is a compile time check which cannot know whether or not sufficient=20
size has been reserved ahead of time.

If the use case is a vector that is pre-allocated and will never attempt to=
=20
do a move of T, then use a different array type which is designed to do=20
exactly that.

On Saturday, April 15, 2017 at 6:33:43 PM UTC-5, Bengt Gustafsson wrote:
>
> =20
>
>> As a variant it would be possible to use different allocators to achieve=
=20
>> these different results.
>
>
> This could be done using these two allocators:
>
>      FixedAllocator<T, N> // Has a fixed block to allocate from, part of=
=20
> its own size.
>      SooAllocator<T, N, A> // Has N elements inside and can also allocate=
=20
> from the subordinate allocator A which defaults to the default allocator
>

For reasons already mentioned, allocators are a dead end. You need to=20
actually modify the vector itself. What data members it has, what methods=
=20
its exposes to the client, and what concepts its compatible with, what are=
=20
the invariants / contracts, etc...=20

On Monday, April 17, 2017 at 10:18:57 AM UTC-5, Bengt Gustafsson wrote:
>
>
>
> Den s=C3=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 skrev Nicol Bolas:
>>
>> On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote:
>>>
>>> =20
>>>
>>>> As a variant it would be possible to use different allocators to=20
>>>> achieve these different results.
>>>
>>>
>>> This could be done using these two allocators:
>>>
>>
>> No, it could not.
>>
>> You can get *some* of the effect of it. But without partial=20
>> specializations of `vector` that explicitly have the desired properties,=
 it=20
>> becomes a big kludge.
>>
>> `FixedAllocator` cannot get rid of two now worthless pointers inside=20
>> `vector`. Neither can `SooAllocator` somehow create a union between the=
=20
>> pointers and the fixed block of elements.
>>
> Well, I did write that the actual implementatation of vector would=20
> probably be specialized for the different allocators as a QoI excercise.
> =20
>
>>
>> Furthermore, `small_vector` and `static_vector` has fundamental=20
>> behavioral differences from `vector` which cannot merely be a matter of=
=20
>> allocators. Moving a `static_vector` into another `static_vector` will=
=20
>> *always* invoke `T`'s move constructor; for `vector`, it never will, no=
=20
>> matter the allocator. `small_vector` has different iterator invalidation=
=20
>> behavior.
>>
> Yes, this would be a somewhat valid concern, but is it so much harder to=
=20
> know that a vector with a certain allocator will invalidate its iterators=
=20
> at move assignment than that a container with a slighly different name (o=
r=20
> template parameters of other sorts than allocators) would?
>
> I would be reluctant to rely on iterators outliving the move assignment o=
f=20
> their vector, but of course there is code out there that does. If such co=
de=20
> is templated on the container to use both solutions are still having the=
=20
> same risk level. If such code is templated on the allocator but uses a=20
> vector of the supplied allocator type then the allocator based solution=
=20
> would maybe fail silently while the new-class solution would not be=20
> applicable at all. This is a very small corner.
> =20
>
>>
>> The current specification of `vector` doesn't allow these things. So if=
=20
>> you're going to force these things, and complicate the specification, it=
=20
>> would be much better to use a true parameterization of `vector`'s behavi=
or,=20
>> rather than an allocator-based hack.
>>
> But unfortunately we can't get such true parameterisation unless we start=
=20
> afresh with a new container name. I was basically just exploring the=20
> possibility of avoiding having to have two names for the same basic type =
of=20
> container where one is "better" and the other is "simpler".
>
> As for your omi_vector, I guess it is similar to how Eigen handles its=20
> configurable matrices. This is powerful but rather hard to set up the 6=
=20
> template parameters so there are quite a few alias templates for common=
=20
> cases. It would be good if you could post the specification of this class=
,=20
> as google could not find it for me.=20
>
>
I believe Nicol's omni_vec idea is the way to go here. Allocators are a=20
dead end. Yes this also means you could redundantly reconstruct vector and=
=20
array using a variant of omni_vec. That's not a bad thing.

I don't think we want to have 6 or 7 template arguments.

I would make omni_vec only take 2 arguments, T and an omni_vec_traits which=
=20
describes the desired behavior.

It would look something like this:
template <typename T, typename Traits> class omni_vec;

template <typename T, typename Allocator=3Dstd::allocator<T>>
struct ov_vector_traits {
using allocator_t =3D Allocator;
using size_type =3D size_t;
static constexpr storage_policy =3D dynamic; //Could be inferred by the=20
presense of allocator_t typedef.
static constexpr is_growable =3D true; //
};

//Behaves exactly the same way as vector.
template <typename T, typename Allocator=3Dstd::allocator<T>>
using vector2 =3D omni_vec<T, ov_vector_traits<T,Allocator>>;

template <typename T, size_t N.
struct ov_array_traits {
static constexpr storage_policy =3D fixed; //Maybe implied by size =3D N=20
compile time constant.
static constexpr size =3D N;
};

//Same as array
template <typename T, size_t N>
using array2 =3D omni_vec<T,ov_array_traits<T,N>>;


The idea here is that omni_vec is not a template you would normally use=20
directly. Instead its a toolbox you configure with traits to construct the=
=20
kind of vector you want. Once you've setup the traits, you create a typedef=
=20
and use that in your code. Obviously, the standard could provide a set of=
=20
typedefs for common scenarios. STL 2.0 if that happens can just define=20
vector and array to be typedefs of omni_vec. vector<bool> sticks around for=
=20
backwards compatibility, and likewise omni_vec<bool,Traits> does the right=
=20
thing.

The traits approach offers several advantages:
- You don't have to remember what all N ordered template arguments mean.=20
Its like using struct vs tuple.
- You don't need to specify everything. Only specify whats needed for your=
=20
behavior. Easy things like vector, array, dyn_array, etc.. only need a few=
=20
simple tokens specified. Hard things like a vector which stores its=20
capacity and size in the memory buffer and uses uint32_t for size_type need=
=20
more complex configuration.
- Its extensible in the future. We can add many omni_vec configuration=20
knobs in the future and not break ABI. Adding more template arguments is=20
ABI breaking.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/d0cb3b20-e197-44af-92c0-459d96793644%40isocpp.or=
g.

------=_Part_465_236836064.1492444717792
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><br><br>On Sunday, March 19, 2017 at 2:05:06 PM UTC-5=
, Magnus Fromreide wrote:<blockquote class=3D"gmail_quote" style=3D"margin:=
 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left=
: 1ex;">This is actuallly false, you can store non-movable objects in a gro=
wable=C2=A0<br>array, you just can&#39;t resize it while it is non-empty.=
=C2=A0<br><br>This means you have to use &quot;reserve&quot; prior to putti=
ng objects into it, but you=C2=A0<br>can still use it dynamically.=C2=A0<br=
><br>/MF=C2=A0</blockquote></div><div><br></div>That doesn&#39;t play well =
with concepts. If I have a resizable vector, then at compile time I might w=
ant to check that T is movable when I call push_back. This is a compile tim=
e check which cannot know whether or not sufficient size has been reserved =
ahead of time.<div><br></div><div>If the use case is a vector that is pre-a=
llocated and will never attempt to do a move of T, then use a different arr=
ay type which is designed to do exactly that.<br><div><br></div><div>On Sat=
urday, April 15, 2017 at 6:33:43 PM UTC-5, Bengt Gustafsson wrote:<blockquo=
te class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; border-left: 1=
px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir=3D"ltr"><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8=
ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">As a var=
iant it would be possible to use different allocators to achieve these diff=
erent results.</blockquote><div><br></div><div>This could be done using the=
se two allocators:</div><div><br></div><div>=C2=A0 =C2=A0 =C2=A0FixedAlloca=
tor&lt;T, N&gt;<span style=3D"white-space: pre;">       </span>// Has a fix=
ed block to allocate from, part of its own size.</div><div>=C2=A0 =C2=A0 =
=C2=A0SooAllocator&lt;T, N, A&gt;<span style=3D"white-space: pre;">      </=
span>// Has N elements inside and can also allocate from the subordinate al=
locator A which defaults to the default allocator</div></div></blockquote><=
div><br></div><div>For reasons already mentioned, allocators are a dead end=
.. You need to actually modify the vector itself. What data members it has, =
what methods its exposes to the client, and what concepts its compatible wi=
th, what are the invariants / contracts, etc...=C2=A0</div></div><div><br>O=
n Monday, April 17, 2017 at 10:18:57 AM UTC-5, Bengt Gustafsson wrote:<bloc=
kquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-l=
eft: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><br><br>Den s=C3=
=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 skrev Nicol Bolas:<blockquote clas=
s=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc =
solid;padding-left:1ex"><div dir=3D"ltr">On Saturday, April 15, 2017 at 7:3=
3:43 PM UTC-4, Bengt Gustafsson wrote:<blockquote class=3D"gmail_quote" sty=
le=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1e=
x"><div dir=3D"ltr"><div>=C2=A0</div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex=
">As a variant it would be possible to use different allocators to achieve =
these different results.</blockquote><div><br></div><div>This could be done=
 using these two allocators:</div></div></blockquote><div><br>No, it could =
not.<br><br>You can get <i>some</i> of the effect of it. But without partia=
l specializations of `vector` that explicitly have the desired properties, =
it becomes a big kludge.<br><br>`FixedAllocator` cannot get rid of two now =
worthless pointers inside `vector`. Neither can `SooAllocator` somehow crea=
te a union between the pointers and the fixed block of elements.<br></div><=
/div></blockquote><div>Well, I did write that the actual implementatation o=
f vector would probably be specialized for the different allocators as a Qo=
I excercise.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"ltr"><div><br>Furthermore, `small_vector` and `static_vector` =
has fundamental behavioral differences from `vector` which cannot merely be=
 a matter of allocators. Moving a `static_vector` into another `static_vect=
or` will <i>always</i> invoke `T`&#39;s move constructor; for `vector`, it =
never will, no matter the allocator. `small_vector` has different iterator =
invalidation behavior.<br></div></div></blockquote><div>Yes, this would be =
a somewhat valid concern, but is it so much harder to know that a vector wi=
th a certain allocator will invalidate its iterators at move assignment tha=
n that a container with a slighly different name (or template parameters of=
 other sorts than allocators) would?</div><div><br></div><div>I would be re=
luctant to rely on iterators outliving the move assignment of their vector,=
 but of course there is code out there that does. If such code is templated=
 on the container to use both solutions are still having the same risk leve=
l. If such code is templated on the allocator but uses a vector of the supp=
lied allocator type then the allocator based solution would maybe fail sile=
ntly while the new-class solution would not be applicable at all. This is a=
 very small corner.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-lef=
t:1ex"><div dir=3D"ltr"><div><br>The current specification of `vector` does=
n&#39;t allow these things. So if you&#39;re going to force these things, a=
nd complicate the specification, it would be much better to use a true para=
meterization of `vector`&#39;s behavior, rather than an allocator-based hac=
k.</div></div></blockquote><div>But unfortunately we can&#39;t get such tru=
e parameterisation unless we start afresh with a new container name. I was =
basically just exploring the possibility of avoiding having to have two nam=
es for the same basic type of container where one is &quot;better&quot; and=
 the other is &quot;simpler&quot;.</div><div><br></div><div>As for your omi=
_vector, I guess it is similar to how Eigen handles its configurable matric=
es. This is powerful but rather hard to set up the 6 template parameters so=
 there are quite a few alias templates for common cases. It would be good i=
f you could post the specification of this class, as google could not find =
it for me.=C2=A0</div><div><br></div></div></blockquote><div><br></div><div=
>I believe Nicol&#39;s omni_vec idea is the way to go here. Allocators are =
a dead end. Yes this also means you could redundantly reconstruct vector an=
d array using a variant of omni_vec. That&#39;s not a bad thing.</div><div>=
<br></div><div>I don&#39;t think we want to have 6 or 7 template arguments.=
</div><div><br></div><div>I would make omni_vec only take 2 arguments, T an=
d an omni_vec_traits which describes the desired behavior.</div><div><br></=
div><div>It would look something like this:</div><div><div class=3D"prettyp=
rint" style=3D"background-color: rgb(250, 250, 250); border-color: rgb(187,=
 187, 187); border-style: solid; border-width: 1px; word-wrap: break-word;"=
><code class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">template</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">&lt;</span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">typename</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">ty=
pename</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #606;" class=3D"styled-by-prettify">Traits</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"=
color: #008;" class=3D"styled-by-prettify">class</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> omni_vec</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"><br><br></span><span style=3D"color: #008;" cla=
ss=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: #008;" class=3D"styled-by-p=
rettify">typename</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"> T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><s=
pan style=3D"color: #008;" class=3D"styled-by-prettify">typename</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #606;" class=3D"styled-by-prettify">Allocator</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify">std</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify">allocator</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&lt;</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify">T</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">&gt;&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>struct</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> ov=
_vector_traits </span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">using</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> allocator_t </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #606;" class=3D"styled-by-prettify">Allocator</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">using</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"> size_type </span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> size_t</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">static</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">constexpr<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify"> storage_po=
licy </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #008;" class=3D"styled-by-prettify">dynamic</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #80=
0;" class=3D"styled-by-prettify">//Could be inferred by the presense of all=
ocator_t typedef.</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>static</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #008;" class=3D"styled-by-prettify">constexpr</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"> is_growable =
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">true</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #800;" clas=
s=3D"styled-by-prettify">//</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">};</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"><br><br></span><span style=3D"color: #800;" class=3D"styled-by-prettify"=
>//Behaves exactly the same way as vector.</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #008;" cla=
ss=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: #008;" class=3D"styled-by-p=
rettify">typename</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"> T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><s=
pan style=3D"color: #008;" class=3D"styled-by-prettify">typename</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #606;" class=3D"styled-by-prettify">Allocator</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify">std</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify">allocator</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&lt;</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify">T</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">&gt;&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>using</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> vec=
tor2 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> omni_vec</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify">T</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> ov_vector_traits</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify">T</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">,</span><span style=3D"color: #606;" class=
=3D"styled-by-prettify">Allocator</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&gt;&gt;;</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br><br></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: #008;" class=3D"styled-by-p=
rettify">typename</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"> T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> size_t N<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">struct</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> ov_array_traits </span><spa=
n 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"co=
lor: #008;" class=3D"styled-by-prettify">static</span><span style=3D"color:=
 #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" c=
lass=3D"styled-by-prettify">constexpr</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"> storage_policy </span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"sty=
led-by-prettify">fixed</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> </span><span style=3D"color: #800;" class=3D"styled-by-prettify">//Mayb=
e implied by size =3D N compile time constant.</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #008;"=
 class=3D"styled-by-prettify">static</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"sty=
led-by-prettify">constexpr</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> size </span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> N</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: #660;" class=3D"styled-by-prettify">};</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"><br><br></span><span style=
=3D"color: #800;" class=3D"styled-by-prettify">//Same as array</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br></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"styled-by-prettify">&lt;</span><span style=3D"color: #008=
;" class=3D"styled-by-prettify">typename</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"> T</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> size_t N</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify=
">using</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> ar=
ray2 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> omni_vec</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify">T</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">ov_array_traits</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">&lt;</span><font color=3D"#00000=
0"><span style=3D"color: #000;" class=3D"styled-by-prettify">T</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify">N</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">&gt;&gt;;</span></font></div></code></div=
><br><br>The idea here is that omni_vec is not a template you would normall=
y use directly. Instead its a toolbox you configure with traits to construc=
t the kind of vector you want. Once you&#39;ve setup the traits, you create=
 a typedef and use that in your code. Obviously, the standard could provide=
 a set of typedefs for common scenarios. STL 2.0 if that happens can just d=
efine vector and array to be typedefs of omni_vec. vector&lt;bool&gt; stick=
s around for backwards compatibility, and likewise omni_vec&lt;bool,Traits&=
gt; does the right thing.<br><br>The traits approach offers several advanta=
ges:</div><div>- You don&#39;t have to remember what all N ordered template=
 arguments mean. Its like using struct vs tuple.</div><div>- You don&#39;t =
need to specify everything. Only specify whats needed for your behavior. Ea=
sy things like vector, array, dyn_array, etc.. only need a few simple token=
s specified. Hard things like a vector which stores its capacity and size i=
n the memory buffer and uses uint32_t for size_type need more complex confi=
guration.</div><div>- Its extensible in the future. We can add many omni_ve=
c configuration knobs in the future and not break ABI. Adding more template=
 arguments is ABI breaking.<br><br></div></div></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/d0cb3b20-e197-44af-92c0-459d96793644%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/d0cb3b20-e197-44af-92c0-459d96793644=
%40isocpp.org</a>.<br />

------=_Part_465_236836064.1492444717792--

------=_Part_464_1422146456.1492444717791--

.

------=_Part_3556_97221916.1492444838315
Content-Type: multipart/alternative;
 boundary="----=_Part_3557_84361832.1492444838315"

------=_Part_3557_84361832.1492444838315
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Monday, April 17, 2017 at 11:18:57 AM UTC-4, Bengt Gustafsson wrote:
>
> Den s=C3=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 skrev Nicol Bolas:
>>
>> On Saturday, April 15, 2017 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote:
>>>
>>> =20
>>>
>>>> As a variant it would be possible to use different allocators to=20
>>>> achieve these different results.
>>>
>>>
>>> This could be done using these two allocators:
>>>
>>
>> No, it could not.
>>
>> You can get *some* of the effect of it. But without partial=20
>> specializations of `vector` that explicitly have the desired properties,=
 it=20
>> becomes a big kludge.
>>
>> `FixedAllocator` cannot get rid of two now worthless pointers inside=20
>> `vector`. Neither can `SooAllocator` somehow create a union between the=
=20
>> pointers and the fixed block of elements.
>>
> Well, I did write that the actual implementatation of vector would=20
> probably be specialized for the different allocators as a QoI excercise.
>
=20

> Furthermore, `small_vector` and `static_vector` has fundamental behaviora=
l=20
>> differences from `vector` which cannot merely be a matter of allocators.=
=20
>> Moving a `static_vector` into another `static_vector` will *always*=20
>> invoke `T`'s move constructor; for `vector`, it never will, no matter th=
e=20
>> allocator. `small_vector` has different iterator invalidation behavior.
>>
> Yes, this would be a somewhat valid concern, but is it so much harder to=
=20
> know that a vector with a certain allocator will invalidate its iterators=
=20
> at move assignment than that a container with a slighly different name (o=
r=20
> template parameters of other sorts than allocators) would?
>

It's not about one being particularly "much harder to know". It's about=20
being a kludge rather than how it *should* be implemented. Allocators=20
should not control fundamental aspects of the container's behavior like=20
that. And the only advantage you gain by this is not having to create a new=
=20
class name, even though you have to create new template specializations for=
=20
it.

I would be reluctant to rely on iterators outliving the move assignment of=
=20
> their vector, but of course there is code out there that does. If such co=
de=20
> is templated on the container to use both solutions are still having the=
=20
> same risk level. If such code is templated on the allocator but uses a=20
> vector of the supplied allocator type then the allocator based solution=
=20
> would maybe fail silently while the new-class solution would not be=20
> applicable at all. This is a very small corner.
>

I didn't say anything about iterators outliving move assignment. I was=20
talking about the fundamental aspects of `vector`'s move behavior. For=20
example, `vector`'s move constructor and move assignment operator are=20
`noexcept`, regardless of the properties of `T` (its exception property=20
only depends on the allocator's move behavior). That *cannot happen* with a=
=20
static vector or a small-sized vector. The `noexcept` status of these=20
operations must be based on the `noexcept` status of the move constructor=
=20
of `T`.


>> The current specification of `vector` doesn't allow these things. So if=
=20
>> you're going to force these things, and complicate the specification, it=
=20
>> would be much better to use a true parameterization of `vector`'s behavi=
or,=20
>> rather than an allocator-based hack.
>>
> But unfortunately we can't get such true parameterisation unless we start=
=20
> afresh with a new container name. I was basically just exploring the=20
> possibility of avoiding having to have two names for the same basic type =
of=20
> container where one is "better" and the other is "simpler".
>

I don't see the difference between `vector<T,=20
ParameterPretendingToBeAllocator<N, ActualAllocator>>` and=20
`parameter_vector<T, Parameter<N>, ActualAllocator>`. Especially since the=
=20
specification has to define `vector` specializations for these allocators=
=20
anyway. And since implementers will have to use completely different=20
implementations for those specializations.

Shoving this parameter in the wrong place, all for the sake of a name? I=20
just don't see the point. Especially when odds are good that people are=20
going to make aliases like `static_vector` and `small_vector` when using=20
them in actual code.

The point of unifying all of these dimensions within one class is to be=20
able to have a foundation for expansion (adding new behaviors) as well as=
=20
allow users to mix-and-match functionality in useful ways. If you're only=
=20
going to support these two variations, I'd much rather they just be=20
separate classes.
=20

> As for your omi_vector, I guess it is similar to how Eigen handles its=20
> configurable matrices. This is powerful but rather hard to set up the 6=
=20
> template parameters so there are quite a few alias templates for common=
=20
> cases. It would be good if you could post the specification of this class=
,=20
> as google could not find it for me.=20
>

The `omni_vector` was just an idea, not to the level of a specification or=
=20
implementation. I talked about it primarily to get input on what dimensions=
=20
of `vector` behavior people were interested in having.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/5125f9e2-161d-4a3f-9ff4-66a94db0fe73%40isocpp.or=
g.

------=_Part_3557_84361832.1492444838315
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Monday, April 17, 2017 at 11:18:57 AM UTC-4, Bengt Gust=
afsson wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">=
Den s=C3=B6ndag 16 april 2017 kl. 04:33:32 UTC+2 skrev Nicol Bolas:<blockqu=
ote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1=
px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Saturday, April 15, 201=
7 at 7:33:43 PM UTC-4, Bengt Gustafsson wrote:<blockquote class=3D"gmail_qu=
ote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding=
-left:1ex"><div dir=3D"ltr"><div>=C2=A0</div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-=
left:1ex">As a variant it would be possible to use different allocators to =
achieve these different results.</blockquote><div><br></div><div>This could=
 be done using these two allocators:</div></div></blockquote><div><br>No, i=
t could not.<br><br>You can get <i>some</i> of the effect of it. But withou=
t partial specializations of `vector` that explicitly have the desired prop=
erties, it becomes a big kludge.<br><br>`FixedAllocator` cannot get rid of =
two now worthless pointers inside `vector`. Neither can `SooAllocator` some=
how create a union between the pointers and the fixed block of elements.<br=
></div></div></blockquote><div>Well, I did write that the actual implementa=
tation of vector would probably be specialized for the different allocators=
 as a QoI excercise.</div></div></blockquote><div>=C2=A0</div><blockquote c=
lass=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px=
 #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><blockquote class=3D"gmail=
_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padd=
ing-left:1ex"><div dir=3D"ltr"><div>Furthermore, `small_vector` and `static=
_vector` has fundamental behavioral differences from `vector` which cannot =
merely be a matter of allocators. Moving a `static_vector` into another `st=
atic_vector` will <i>always</i> invoke `T`&#39;s move constructor; for `vec=
tor`, it never will, no matter the allocator. `small_vector` has different =
iterator invalidation behavior.<br></div></div></blockquote><div>Yes, this =
would be a somewhat valid concern, but is it so much harder to know that a =
vector with a certain allocator will invalidate its iterators at move assig=
nment than that a container with a slighly different name (or template para=
meters of other sorts than allocators) would?</div></div></blockquote><div>=
<br>It&#39;s not about one being particularly &quot;much harder to know&quo=
t;. It&#39;s about being a kludge rather than how it <i>should</i> be imple=
mented. Allocators should not control fundamental aspects of the container&=
#39;s behavior like that. And the only advantage you gain by this is not ha=
ving to create a new class name, even though you have to create new templat=
e specializations for it.<br><br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;"><div dir=3D"ltr"><div></div><div>I would be reluctant to rely on i=
terators outliving the move assignment of their vector, but of course there=
 is code out there that does. If such code is templated on the container to=
 use both solutions are still having the same risk level. If such code is t=
emplated on the allocator but uses a vector of the supplied allocator type =
then the allocator based solution would maybe fail silently while the new-c=
lass solution would not be applicable at all. This is a very small corner.<=
/div></div></blockquote><div><br>I didn&#39;t say anything about iterators =
outliving move assignment. I was=20
talking about the fundamental aspects of `vector`&#39;s move behavior. For=
=20
example, `vector`&#39;s move constructor and move assignment operator are=
=20
`noexcept`, regardless of the properties of `T` (its exception property=20
only depends on the allocator&#39;s move behavior). That <i>cannot happen</=
i>
 with a static vector or a small-sized vector. The `noexcept` status of=20
these operations must be based on the `noexcept` status of the move=20
constructor of `T`.<br><br></div><blockquote class=3D"gmail_quote" style=3D=
"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex=
;"><div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;mar=
gin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr=
"><div><br>The current specification of `vector` doesn&#39;t allow these th=
ings. So if you&#39;re going to force these things, and complicate the spec=
ification, it would be much better to use a true parameterization of `vecto=
r`&#39;s behavior, rather than an allocator-based hack.</div></div></blockq=
uote><div>But unfortunately we can&#39;t get such true parameterisation unl=
ess we start afresh with a new container name. I was basically just explori=
ng the possibility of avoiding having to have two names for the same basic =
type of container where one is &quot;better&quot; and the other is &quot;si=
mpler&quot;.</div></div></blockquote><div><br>I don&#39;t see the differenc=
e between `vector&lt;T, ParameterPretendingToBeAllocator&lt;N, ActualAlloca=
tor&gt;&gt;` and `parameter_vector&lt;T, Parameter&lt;N&gt;, ActualAllocato=
r&gt;`. Especially since the specification has to define `vector` specializ=
ations for these allocators anyway. And since implementers will have to use=
 completely different implementations for those specializations.<br><br>Sho=
ving this parameter in the wrong place, all for the sake of a name? I just =
don&#39;t see the point. Especially when odds are good that people are goin=
g to make aliases like `static_vector` and `small_vector` when using them i=
n actual code.<br><br>The point of unifying all of these dimensions within =
one class is to be able to have a foundation for expansion (adding new beha=
viors) as well as allow users to mix-and-match functionality in useful ways=
.. If you&#39;re only going to support these two variations, I&#39;d much ra=
ther they just be separate classes.<br>=C2=A0</div><blockquote class=3D"gma=
il_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid=
;padding-left: 1ex;"><div dir=3D"ltr"><div>As for your omi_vector, I guess =
it is similar to how Eigen handles its configurable matrices. This is power=
ful but rather hard to set up the 6 template parameters so there are quite =
a few alias templates for common cases. It would be good if you could post =
the specification of this class, as google could not find it for me.=C2=A0<=
/div></div></blockquote><div><br>The `omni_vector` was just an idea, not to=
 the level of a specification or implementation. I talked about it primaril=
y to get input on what dimensions of `vector` behavior people were interest=
ed in having.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/5125f9e2-161d-4a3f-9ff4-66a94db0fe73%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/5125f9e2-161d-4a3f-9ff4-66a94db0fe73=
%40isocpp.org</a>.<br />

------=_Part_3557_84361832.1492444838315--

------=_Part_3556_97221916.1492444838315--

.

------=_Part_539_223111141.1492447874874
Content-Type: multipart/alternative;
 boundary="----=_Part_540_826203111.1492447874875"

------=_Part_540_826203111.1492447874875
Content-Type: text/plain; charset=UTF-8

As for configuration options, here's all I can think of at the moment:

   - Capacity
      - None (==size, fixed size array types)
      - Static: Compile time constant
      - Dynamic: Stored in container
      - Dynamic: Stored in allocated buffer
      - Dynamic: f(size) - not stored at all, computed from size. example:
      next power of 2 >= than size
         - Should also allow overridable fast computation of size >=
         capacity in push_back(). For example ispow2(size) is faster than size ==
         ceil_pow2(size).
      - Size
      - Static: Compile time constant (requires no capacity)
      - Dynamic: Stored in container
      - Dynamic: Stored in allocated buffer
      - Dynamic: f(T) - not stored at all, unique sentinel element at the
      end of the buffer. (e.g. nan, nullptr, etc..)
         - size() and push_back() become O(N)
         - Debug mode checks to assert that a sentinel element is never
         inadvertently added by the user.
      - Growable Size
      - True: Requires T to be movable. enables push_back(), insert(),
      erase(),  etc...
         - If capacity is dynamic, default construction should be
         guaranteed to do no allocations.
      - False: Requires capacity to be "none"
         - All non-move constructors always do an exact allocation of
         size() T objects.
         - Allows non-movable T, and const T
      - Growable Capacity
      - True: (requires dynamic capacity and dynamic size)
         - Calling push_back() or insert() when full reallocates.
      - False:
         - Calling push_back() or insert() when full throws exception.
      - Growth Factor
      - If present, requires Growable Capacity == true. Can be size_type or
      std::ratio<size_type,size_type>. Default can either be something agreed
      upon or implementation defined. ratio<3,2> can be used for the popular 1.5
      growth factor.
   - size_type
      - Integral, can be signed or unsigned
      - If not specified, defaults to decltype(size) if size a compile time
      constant, or size_t otherwise.
      - UB if you try to create an omni_vec with size() >=
      numeric_limits<size_type>::max()
   - allocator_t
      - Required for dynamic capacity.
      - Where possible, any omni_vec<T,TraitsA>, omni_vec<T,TraitsB> should
      be able to efficiently swap/move underlying buffers with each other if they
      use the same allocator.
         - This would have to be disallowed in the case where capacity() is
         computed as f(size) as we could not guarantee anything about the capacity
         of some other buffer moved into this. An optional cast could be added for
         this narrow use case which does a runtime check on the capacity and throws
         if its not == f(size).
      - omni_vec<T,Traits> should be able to swap/move underlying buffers
      with vector<T,A> if they use the same allocator.
   - Small buffer optimization:
      - Disabled - normal behavior
      - Some size N > 0 - Requires dynamic capacity.
         - move operations of container now require movable T
      - Bit Storage and proxy iterators
      - Some special T which makes the array behave like a bitset /
      vector<bool>. Then we get the underlying storage bitset and dynamic_bitset
      basically for free and they can use all of the omni_vec storage policy
      variants.

array_view and static_array_view are pretty different. It can be argued
that they belong in their own separate array_view / span library.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/6492fd26-fea9-4765-a173-599ec8899647%40isocpp.org.

------=_Part_540_826203111.1492447874875
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">As for configuration options, here&#39;s all I can think o=
f at the moment:<div><ul><li>Capacity</li><ul><li>None (=3D=3Dsize, fixed s=
ize array types)</li><li>Static: Compile time constant</li><li>Dynamic: Sto=
red in container</li><li>Dynamic: Stored in allocated buffer</li><li>Dynami=
c: f(size) - not stored at all, computed from size. example: next power of =
2 &gt;=3D than size</li><ul><li>Should also allow overridable fast computat=
ion of size &gt;=3D capacity in push_back(). For example ispow2(size) is fa=
ster than size =3D=3D ceil_pow2(size).</li></ul></ul><li>Size</li><ul><li>S=
tatic: Compile time constant (requires no capacity)</li><li>Dynamic: Stored=
 in container</li><li>Dynamic: Stored in allocated buffer</li><li>Dynamic: =
f(T) - not stored at all, unique sentinel element at the end of the buffer.=
 (e.g. nan, nullptr, etc..)</li><ul><li>size() and push_back() become O(N)<=
/li><li>Debug mode checks to assert that a sentinel element is never inadve=
rtently added by the user.</li></ul></ul><li>Growable Size</li><ul><li>True=
: Requires T to be movable. enables push_back(), insert(), erase(), =C2=A0e=
tc...</li><ul><li>If capacity is dynamic, default construction should be gu=
aranteed to do no allocations.</li></ul><li>False: Requires capacity to be =
&quot;none&quot;</li><ul><li>All non-move constructors always do an exact a=
llocation of size() T objects.</li><li>Allows non-movable T, and const T</l=
i></ul></ul><li>Growable Capacity</li><ul><li>True: (requires dynamic capac=
ity and dynamic size)</li><ul><li>Calling push_back() or insert() when full=
 reallocates.</li></ul><li>False:</li><ul><li>Calling push_back() or insert=
() when full throws exception.</li></ul></ul><li>Growth Factor</li><ul><li>=
If present, requires Growable Capacity =3D=3D true. Can be size_type or std=
::ratio&lt;size_type,size_type&gt;. Default can either be something agreed =
upon or implementation defined. ratio&lt;3,2&gt; can be used for the popula=
r 1.5 growth factor.</li></ul><li>size_type</li><ul><li>Integral, can be si=
gned or unsigned</li><li>If not specified, defaults to decltype(size) if si=
ze a compile time constant, or size_t otherwise.</li><li>UB if you try to c=
reate an omni_vec with size() &gt;=3D numeric_limits&lt;size_type&gt;::max(=
)</li></ul><li>allocator_t</li><ul><li>Required for dynamic capacity.</li><=
li>Where possible, any omni_vec&lt;T,TraitsA&gt;, omni_vec&lt;T,TraitsB&gt;=
 should be able to efficiently swap/move underlying buffers with each other=
 if they use the same allocator.</li><ul><li>This would have to be disallow=
ed in the case where capacity() is computed as f(size) as we could not guar=
antee anything about the capacity of some other buffer moved into this. An =
optional cast could be added for this narrow use case which does a runtime =
check on the capacity and throws if its not =3D=3D f(size).</li></ul><li>om=
ni_vec&lt;T,Traits&gt; should be able to swap/move underlying buffers with =
vector&lt;T,A&gt; if they use the same allocator.</li></ul><li>Small buffer=
 optimization:</li><ul><li>Disabled - normal behavior</li><li>Some size N &=
gt; 0 - Requires dynamic capacity.</li><ul><li>move operations of container=
 now require movable T</li></ul></ul><li>Bit Storage and proxy iterators</l=
i><ul><li>Some special T which makes the array behave like a bitset / vecto=
r&lt;bool&gt;. Then we get the underlying storage bitset and dynamic_bitset=
 basically for free and they can use all of the omni_vec storage policy var=
iants.=C2=A0</li></ul></ul><div>array_view and static_array_view are pretty=
 different. It can be argued that they belong in their own separate array_v=
iew / span library.</div></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/6492fd26-fea9-4765-a173-599ec8899647%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/6492fd26-fea9-4765-a173-599ec8899647=
%40isocpp.org</a>.<br />

------=_Part_540_826203111.1492447874875--

------=_Part_539_223111141.1492447874874--

.

------=_Part_4517_1083433390.1492451221354
Content-Type: multipart/alternative;
 boundary="----=_Part_4518_2130728925.1492451221354"

------=_Part_4518_2130728925.1492451221354
Content-Type: text/plain; charset=UTF-8

On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote:
>
> As for configuration options, here's all I can think of at the moment:
>

There is a very great deal of overlap in that list. As well as
contradictory dimensions: you can't have a static capacity stored in the
object with dynamic resizing that's allocated. The parameterization system
should be designed to avoid such contradictory options, rather than simply
declaring them illegal.

Also, there are several options of... dubious merit. Control over
`size_type`, for example. And having a sentinel value rather than a genuine
size; that's just begging for someone to break the container. Even
`basic_string`, a type designed specifically for such a use case, doesn't
actually use the NUL character to determine the string's size.

Similarly, no form of `vector` should support "Bit Storage and proxy
iterators". `vector<T>` is supposed to mean "contiguous storage of `T`",
and every form of `vector` ought to provide that.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/401585fc-6648-4dcd-b3ba-25e135833d85%40isocpp.org.

------=_Part_4518_2130728925.1492451221354
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fi=
oravante wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-=
left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr=
">As for configuration options, here&#39;s all I can think of at the moment=
:</div></blockquote><div><br>There is a very great deal of overlap in that =
list. As well as contradictory dimensions: you can&#39;t have a static capa=
city stored in the object with dynamic resizing that&#39;s allocated. The p=
arameterization system should be designed to avoid such contradictory optio=
ns, rather than simply declaring them illegal.<br><br>Also, there are sever=
al options of... dubious merit. Control over `size_type`, for example. And =
having a sentinel value rather than a genuine size; that&#39;s just begging=
 for someone to break the container. Even `basic_string`, a type designed s=
pecifically for such a use case, doesn&#39;t actually use the NUL character=
 to determine the string&#39;s size.<br><br>Similarly, no form of `vector` =
should support &quot;Bit Storage and proxy iterators&quot;. `vector&lt;T&gt=
;` is supposed to mean &quot;contiguous storage of `T`&quot;, and every for=
m of `vector` ought to provide that.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/401585fc-6648-4dcd-b3ba-25e135833d85%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/401585fc-6648-4dcd-b3ba-25e135833d85=
%40isocpp.org</a>.<br />

------=_Part_4518_2130728925.1492451221354--

------=_Part_4517_1083433390.1492451221354--

.

------=_Part_330_1260978237.1492453691418
Content-Type: multipart/alternative;
 boundary="----=_Part_331_1945898688.1492453691418"

------=_Part_331_1945898688.1492453691418
Content-Type: text/plain; charset=UTF-8



On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote:
>
> On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote:
>>
>> As for configuration options, here's all I can think of at the moment:
>>
>
> There is a very great deal of overlap in that list. As well as
> contradictory dimensions: you can't have a static capacity stored in the
> object with dynamic resizing that's allocated.
>

Sure, this is an off the cuff list I produced in 2 minutes. Certainly there
are various illegal combinations, contradictions, and possibly other
options I've left out. But hopefully it gives a starting point for fleshing
out a real interface.

For example, I just realized that growth_factor should actually just be a
function object instead of a size or ratio. Sometimes you really want an
additive linear growth factor.


> The parameterization system should be designed to avoid such contradictory
> options, rather than simply declaring them illegal.
>

At a minimum, I would suggest using static_asserts in omni_vec to detect
and complain about all illegal combinations with helpful diagnostics.
Obviously if the interface is designed well to lead you avoid mistakes all
the better.


>
> Also, there are several options of... dubious merit. Control over
> `size_type`, for example.
>

This is not dubious at all. I can give you 2 solid use cases, both of which
I've done in the past.

On 64 bit platforms, a vector using size_t is 24 bytes, whereas vector
using uint32_t is only 16 bytes. Those 8 bytes can be valuable if you have
several of these packed tightly in a single cache line in hot memory. For a
lot of use cases, we'll never need more than 4 billions elements in a
vector.

Signed size_type also might let me finally start using gcc's -Wconversion
without getting a ton of false positives. I don't use -Wconversion because
all of the required casts around STL containers can easily cause bugs of
their own. Signed size() might also enable optimizations in some cases
because the compiler can assume signed arithmetic sourced from a call to
size() can never overflow.


> And having a sentinel value rather than a genuine size; that's just
> begging for someone to break the container. Even `basic_string`, a type
> designed specifically for such a use case, doesn't actually use the NUL
> character to determine the string's size.
>

I've used the sentinel in production code as well. Again I don't need to
store a size variable anywhere, saving valuable cache space. The most
common use case for this is when you have a list of pointers to callbacks
to be iterated through. All of the pointers except the last one are null.

This makes size() and push_back() slow, but in my use case it was a
situation where I set everything up on startup and then need to iterate the
list over and over again in the hotpath. I don't give a damn about a bit
slower slow setup (not even measurable in real tests), when it buys me the
fastest possible iteration loop.

This optimizes the hell out of iteration. After optimization its
essentially this:
for(T**p = v.data(); *p != nullptr; ++p) {
  doSomething(*p);
}

The vector itself only stores a single pointer and is only 8 bytes in size.

Capacity can either be a function of size (size % N, next power of 2,
etc..) or a static compile time upper bound.

Now I agree that this is easy to use wrong in the general case. But again,
omni_vec is a toolbox that doesn't always have to stand on its own in the
wild. I can create a sentinel based omni_vec inside and then further wrap
it in a safer interface.

I think the decision for string was more about 2 things: (1) allowing for
strings with embedded nulls (mandatory for binary string data) and (2)
making size() O(1). For string data, this is the right trade-off because in
the context of string, those are 2 very important properties to have. For
some other generic situations, they may not be necessary.

One might also want to make a C style null terminated string type which
doesn't store the size, and they could easily start out by using
omni_vec<char,Traits> to define the storage policy and build a semantic
string wrapper on-top.


> Similarly, no form of `vector` should support "Bit Storage and proxy
> iterators". `vector<T>` is supposed to mean "contiguous storage of `T`",
> and every form of `vector` ought to provide that.
>

I think my original idea of using some kind of type T to enable this is
wrong, as its similar to vector<bool>. Certaintly though it could make
sense to add a traits parameter to enable bitset behavior, with a
static_assert() that T is bool.

Iterating over bits is fundamentally different than iterating over T. I
agree that it is a bit uncomfortable how it crosses the turf of vector a
bitset. However, if we added some facility to omni_vec, it means we get all
the storage foundations for all possible bitsets for free.

Bitsets operate exactly like vectors and arrays. The only difference is
that bits need special handling because they can't be represented with a
type T directly.

Another option could be an omni_bitset, which uses the exact same traits as
omni_vec but has bitset semantics.

I guess the idea I'm envisioning here is a completely flexible array-like
storage backend for any possible kind of array like thing you would want.
Simple inheritance/composition can be used to add additional semantic
layers as needed (strings, bitsets, circular buffers, etc..).

Writing your own vector like type is a huge pain. Especially getting all of
the move semantics and exception safety right. Having a flexible omni_vec
tool would provide all of that foundation for us and let us create all
kinds of really interesting and immediately useful data structures.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/31af4b2d-2481-419e-856b-5363635d6a7a%40isocpp.org.

------=_Part_331_1945898688.1492453691418
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Ni=
col Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"lt=
r">On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote=
:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">As for configurat=
ion options, here&#39;s all I can think of at the moment:</div></blockquote=
><div><br>There is a very great deal of overlap in that list. As well as co=
ntradictory dimensions: you can&#39;t have a static capacity stored in the =
object with dynamic resizing that&#39;s allocated.</div></div></blockquote>=
<div><br></div><div>Sure, this is an off the cuff list I produced in 2 minu=
tes. Certainly there are various illegal combinations, contradictions, and =
possibly other options I&#39;ve left out. But hopefully it gives a starting=
 point for fleshing out a real interface.</div><div><br></div><div>For exam=
ple, I just realized that growth_factor should actually just be a function =
object instead of a size or ratio. Sometimes you really want an additive li=
near growth factor.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote"=
 style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-=
left: 1ex;"><div dir=3D"ltr"><div>The parameterization system should be des=
igned to avoid such contradictory options, rather than simply declaring the=
m illegal.<br></div></div></blockquote><div><br></div><div>At a minimum, I =
would suggest using static_asserts in omni_vec to detect and complain about=
 all illegal combinations with helpful diagnostics. Obviously if the interf=
ace is designed well to lead you avoid mistakes all the better.</div><div>=
=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><=
div><br>Also, there are several options of... dubious merit. Control over `=
size_type`, for example. </div></div></blockquote><div><br></div><div>This =
is not dubious at all. I can give you 2 solid use cases, both of which I&#3=
9;ve done in the past.</div><div><br></div><div>On 64 bit platforms, a vect=
or using size_t is 24 bytes, whereas vector using uint32_t is only 16 bytes=
.. Those 8 bytes can be valuable if you have several of these packed tightly=
 in a single cache line in hot memory. For a lot of use cases, we&#39;ll ne=
ver need more than 4 billions elements in a vector.</div><div><br></div><di=
v>Signed size_type also might let me finally start using gcc&#39;s -Wconver=
sion without getting a ton of false positives. I don&#39;t use -Wconversion=
 because all of the required casts around STL containers can easily cause b=
ugs of their own. Signed size() might also enable optimizations in some cas=
es because the compiler can assume signed arithmetic sourced from a call to=
 size() can never overflow.</div><div>=C2=A0</div><blockquote class=3D"gmai=
l_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;=
padding-left: 1ex;"><div dir=3D"ltr"><div>And having a sentinel value rathe=
r than a genuine size; that&#39;s just begging for someone to break the con=
tainer. Even `basic_string`, a type designed specifically for such a use ca=
se, doesn&#39;t actually use the NUL character to determine the string&#39;=
s size.<br></div></div></blockquote><div><br></div><div>I&#39;ve used the s=
entinel in production code as well. Again I don&#39;t need to store a size =
variable anywhere, saving valuable cache space. The most common use case fo=
r this is when you have a list of pointers to callbacks to be iterated thro=
ugh. All of the pointers except the last one are null.</div><div><br></div>=
<div>This makes size() and push_back() slow, but in my use case it was a si=
tuation where I set everything up on startup and then need to iterate the l=
ist over and over again in the hotpath. I don&#39;t give a damn about a bit=
 slower slow setup (not even measurable in real tests), when it buys me the=
 fastest possible iteration loop.</div><div><br></div><div>This optimizes t=
he hell out of iteration. After optimization its essentially this:</div><di=
v><div class=3D"prettyprint" style=3D"background-color: rgb(250, 250, 250);=
 border-color: rgb(187, 187, 187); border-style: solid; border-width: 1px; =
word-wrap: break-word;"><font color=3D"#000000" face=3D"monospace">for(T**p=
 =3D v.data(); *p !=3D nullptr; ++p) {<br>=C2=A0 doSomething(*p);<br>}</fon=
t></div><br>The vector itself only stores a single pointer and is only 8 by=
tes in size.</div><div><br></div><div>Capacity can either be a function of =
size (size % N, next power of 2, etc..) or a static compile time upper boun=
d.</div><div><br></div><div>Now I agree that this is easy to use wrong in t=
he general case. But again, omni_vec is a toolbox that doesn&#39;t always h=
ave to stand on its own in the wild. I can create a sentinel based omni_vec=
 inside and then further wrap it in a safer interface.</div><div><br></div>=
<div>I think the decision for string was more about 2 things: (1) allowing =
for strings with embedded nulls (mandatory for binary string data) and (2) =
making size() O(1). For string data, this is the right trade-off because in=
 the context of string, those are 2 very important properties to have. For =
some other generic situations, they may not be necessary.</div><div><br></d=
iv><div>One might also want to make a C style null terminated string type w=
hich doesn&#39;t store the size, and they could easily start out by using o=
mni_vec&lt;char,Traits&gt; to define the storage policy and build a semanti=
c string wrapper on-top.</div><div>=C2=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;pad=
ding-left: 1ex;"><div dir=3D"ltr"><div>Similarly, no form of `vector` shoul=
d support &quot;Bit Storage and proxy iterators&quot;. `vector&lt;T&gt;` is=
 supposed to mean &quot;contiguous storage of `T`&quot;, and every form of =
`vector` ought to provide that.<br></div></div></blockquote><div><br></div>=
<div>I think my original idea of using some kind of type T to enable this i=
s wrong, as its similar to vector&lt;bool&gt;. Certaintly though it could m=
ake sense to add a traits parameter to enable bitset behavior, with a stati=
c_assert() that T is bool.</div><div><br></div><div>Iterating over bits is =
fundamentally different than iterating over T. I agree that it is a bit unc=
omfortable how it crosses the turf of vector a bitset. However, if we added=
 some facility to omni_vec, it means we get all the storage foundations for=
 all possible bitsets for free.</div><div><br></div><div>Bitsets operate ex=
actly like vectors and arrays. The only difference is that bits need specia=
l handling because they can&#39;t be represented with a type T directly.</d=
iv><div><br></div><div>Another option could be an omni_bitset, which uses t=
he exact same traits as omni_vec but has bitset semantics.</div><div><br></=
div><div>I guess the idea I&#39;m envisioning here is a completely flexible=
 array-like storage backend for any possible kind of array like thing you w=
ould want. Simple inheritance/composition can be used to add additional sem=
antic layers as needed (strings, bitsets, circular buffers, etc..).</div><d=
iv><br>Writing your own vector like type is a huge pain. Especially getting=
 all of the move semantics and exception safety right. Having a flexible om=
ni_vec tool would provide all of that foundation for us and let us create a=
ll kinds of really interesting and immediately useful data structures.</div=
></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/31af4b2d-2481-419e-856b-5363635d6a7a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/31af4b2d-2481-419e-856b-5363635d6a7a=
%40isocpp.org</a>.<br />

------=_Part_331_1945898688.1492453691418--

------=_Part_330_1260978237.1492453691418--

.

------=_Part_5549_1456587966.1492459499890
Content-Type: multipart/alternative;
 boundary="----=_Part_5550_1891250717.1492459499891"

------=_Part_5550_1891250717.1492459499891
Content-Type: text/plain; charset=UTF-8

On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:
>
> On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote:
>>
>> On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote:
>>>
>>> As for configuration options, here's all I can think of at the moment:
>>>
>>
>> There is a very great deal of overlap in that list. As well as
>> contradictory dimensions: you can't have a static capacity stored in the
>> object with dynamic resizing that's allocated.
>>
>
> Sure, this is an off the cuff list I produced in 2 minutes. Certainly
> there are various illegal combinations, contradictions, and possibly other
> options I've left out. But hopefully it gives a starting point for fleshing
> out a real interface.
>
> For example, I just realized that growth_factor should actually just be a
> function object instead of a size or ratio. Sometimes you really want an
> additive linear growth factor.
>
>
>> The parameterization system should be designed to avoid such
>> contradictory options, rather than simply declaring them illegal.
>>
>
> At a minimum, I would suggest using static_asserts in omni_vec to detect
> and complain about all illegal combinations with helpful diagnostics.
> Obviously if the interface is designed well to lead you avoid mistakes all
> the better.
>
>
>>
>> Also, there are several options of... dubious merit. Control over
>> `size_type`, for example.
>>
>
> This is not dubious at all. I can give you 2 solid use cases, both of
> which I've done in the past.
>
> On 64 bit platforms, a vector using size_t is 24 bytes, whereas vector
> using uint32_t is only 16 bytes. Those 8 bytes can be valuable if you have
> several of these packed tightly in a single cache line in hot memory. For a
> lot of use cases, we'll never need more than 4 billions elements in a
> vector.
>

You assume that `size_type` is actually stored in the `vector` to contain
the size. Many `vector` implementations simply contain 3 pointers,
computing `size` and `capacity` as needed.

So controlling `size_type` will not help you on such implementations.

Signed size_type also might let me finally start using gcc's -Wconversion
> without getting a ton of false positives. I don't use -Wconversion because
> all of the required casts around STL containers can easily cause bugs of
> their own. Signed size() might also enable optimizations in some cases
> because the compiler can assume signed arithmetic sourced from a call to
> size() can never overflow.
>

And what exactly would control over `size_type` do for that problem *in
general*? Because it won't change the fact that *every other* container
uses an unsigned `size_type`. Nor will it change the fact that `span<T>`
will use an unsigned `size_type`. Nor will it change the fact that the
unparameterized `vector` will use an unsigned `size_type`. Nor will it
change the fact that someone else can pass you a `vector` that uses an
unsigned `size_type`.

Also, `container::size_type` is *required* by the standard to be an
unsigned integer, big enough to store any non-negative value of
`container::difference_type`. If you have a problem with the way
containers/ranges return their sizes, then that's a problem that needs to
be handled at the specification level, not in a specific container class.

And having a sentinel value rather than a genuine size; that's just begging
>> for someone to break the container. Even `basic_string`, a type designed
>> specifically for such a use case, doesn't actually use the NUL character to
>> determine the string's size.
>>
>
> I've used the sentinel in production code as well.
>

I never said that nobody uses such things in production code. I said that
it's not something the standard library should support. It's just too
fragile of a container for the standard library.

Again I don't need to store a size variable anywhere, saving valuable cache
> space. The most common use case for this is when you have a list of
> pointers to callbacks to be iterated through. All of the pointers except
> the last one are null.
>
> This makes size() and push_back() slow, but in my use case it was a
> situation where I set everything up on startup and then need to iterate the
> list over and over again in the hotpath. I don't give a damn about a bit
> slower slow setup (not even measurable in real tests), when it buys me the
> fastest possible iteration loop.
>
> This optimizes the hell out of iteration. After optimization its
> essentially this:
> for(T**p = v.data(); *p != nullptr; ++p) {
>   doSomething(*p);
> }
>
>
Which you can do right now by manually putting a NULL pointer at the end of
the list. This sounds like something best handled by some kind of
iterator/range adapter, not by changing the container itself. Indeed, by
making it an adapter rather than part of the class, it can now be used for
lots of tasks, the equivalent of doing a loop until you reach the value
that `find_if` would return.

The vector itself only stores a single pointer and is only 8 bytes in size.
>

So you create this incredibly fragile container... just to save 16 bytes.

Capacity can either be a function of size (size % N, next power of 2,
> etc..) or a static compile time upper bound.
>

Um, if the capacity is a function of the size, then the capacity must
change whenever the size does. Which makes the capacity functionally
useless; it will have to reallocate on any insertion or removal.

Now I agree that this is easy to use wrong in the general case. But again,
> omni_vec is a toolbox that doesn't always have to stand on its own in the
> wild. I can create a sentinel based omni_vec inside and then further wrap
> it in a safer interface.
>
> I think the decision for string was more about 2 things: (1) allowing for
> strings with embedded nulls (mandatory for binary string data) and (2)
> making size() O(1). For string data, this is the right trade-off because in
> the context of string, those are 2 very important properties to have. For
> some other generic situations, they may not be necessary.
>
> One might also want to make a C style null terminated string type which
> doesn't store the size, and they could easily start out by using
> omni_vec<char,Traits> to define the storage policy and build a semantic
> string wrapper on-top.
>
>
>> Similarly, no form of `vector` should support "Bit Storage and proxy
>> iterators". `vector<T>` is supposed to mean "contiguous storage of `T`",
>> and every form of `vector` ought to provide that.
>>
>
> I think my original idea of using some kind of type T to enable this is
> wrong, as its similar to vector<bool>. Certaintly though it could make
> sense to add a traits parameter to enable bitset behavior, with a
> static_assert() that T is bool.
>
> Iterating over bits is fundamentally different than iterating over T. I
> agree that it is a bit uncomfortable how it crosses the turf of vector a
> bitset. However, if we added some facility to omni_vec, it means we get all
> the storage foundations for all possible bitsets for free.
>
> Bitsets operate exactly like vectors and arrays.
>

No, they do not. A `vector<T>` is a contiguous container of `T`s, which can
be iterated over and accessed by pointers. A bitset isn't that. So no, they
do not "operate *exactly*" like `vector`.

You can use a `vector` to *create* a bitset, but that's different from a
bitset actually *being* a specialization of `vector`. I could even imagine
a new `bitset` class that takes the same parameters as `omni_vector`,
forwarding them to an internal `vector` implementation.


> The only difference is that bits need special handling because they can't
> be represented with a type T directly.
>
> Another option could be an omni_bitset, which uses the exact same traits
> as omni_vec but has bitset semantics.
>
> I guess the idea I'm envisioning here is a completely flexible array-like
> storage backend for any possible kind of array like thing you would want.
> Simple inheritance/composition can be used to add additional semantic
> layers as needed (strings, bitsets, circular buffers, etc..).
>

You can use `vector` in an implementation of bitset as it currently stands;
you don't need to shove bitset functionality *into* `vector` to do that.
You'll just have to write a bit more code.

And that "bit more code" is not the hard code of implementing `vector`.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/92026194-86f7-4e1d-94e5-d5c0f1cfd602%40isocpp.org.

------=_Part_5550_1891250717.1492459499891
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fio=
ravante wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
>On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote:<blockqu=
ote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1=
px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monday, April 17, 2017 =
at 12:51:15 PM UTC-4, Matthew Fioravante wrote:<blockquote class=3D"gmail_q=
uote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;paddin=
g-left:1ex"><div dir=3D"ltr">As for configuration options, here&#39;s all I=
 can think of at the moment:</div></blockquote><div><br>There is a very gre=
at deal of overlap in that list. As well as contradictory dimensions: you c=
an&#39;t have a static capacity stored in the object with dynamic resizing =
that&#39;s allocated.</div></div></blockquote><div><br></div><div>Sure, thi=
s is an off the cuff list I produced in 2 minutes. Certainly there are vari=
ous illegal combinations, contradictions, and possibly other options I&#39;=
ve left out. But hopefully it gives a starting point for fleshing out a rea=
l interface.</div><div><br></div><div>For example, I just realized that gro=
wth_factor should actually just be a function object instead of a size or r=
atio. Sometimes you really want an additive linear growth factor.</div><div=
>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-lef=
t:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>=
The parameterization system should be designed to avoid such contradictory =
options, rather than simply declaring them illegal.<br></div></div></blockq=
uote><div><br></div><div>At a minimum, I would suggest using static_asserts=
 in omni_vec to detect and complain about all illegal combinations with hel=
pful diagnostics. Obviously if the interface is designed well to lead you a=
void mistakes all the better.</div><div>=C2=A0</div><blockquote class=3D"gm=
ail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;p=
adding-left:1ex"><div dir=3D"ltr"><div><br>Also, there are several options =
of... dubious merit. Control over `size_type`, for example. </div></div></b=
lockquote><div><br></div><div>This is not dubious at all. I can give you 2 =
solid use cases, both of which I&#39;ve done in the past.</div><div><br></d=
iv><div>On 64 bit platforms, a vector using size_t is 24 bytes, whereas vec=
tor using uint32_t is only 16 bytes. Those 8 bytes can be valuable if you h=
ave several of these packed tightly in a single cache line in hot memory. F=
or a lot of use cases, we&#39;ll never need more than 4 billions elements i=
n a vector.</div></div></blockquote><div><br>You assume that `size_type` is=
 actually stored in the `vector` to contain the size. Many `vector` impleme=
ntations simply contain 3 pointers, computing `size` and `capacity` as need=
ed.<br><br>So controlling `size_type` will not help you on such implementat=
ions.<br><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;mar=
gin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D=
"ltr"><div></div><div>Signed size_type also might let me finally start usin=
g gcc&#39;s -Wconversion without getting a ton of false positives. I don&#3=
9;t use -Wconversion because all of the required casts around STL container=
s can easily cause bugs of their own. Signed size() might also enable optim=
izations in some cases because the compiler can assume signed arithmetic so=
urced from a call to size() can never overflow.</div></div></blockquote><di=
v><br>And what exactly would control over `size_type` do for that problem <=
i>in general</i>? Because it won&#39;t change the fact that <i>every other<=
/i> container uses an unsigned `size_type`. Nor will it change the fact tha=
t `span&lt;T&gt;` will use an unsigned `size_type`. Nor will it change the =
fact that the unparameterized `vector` will use an unsigned `size_type`. No=
r will it change the fact that someone else can pass you a `vector` that us=
es an unsigned `size_type`.<br><br>Also, `container::size_type` is <i>requi=
red</i> by the standard to be an unsigned integer, big enough to store any =
non-negative value of `container::difference_type`. If you have a problem w=
ith the way containers/ranges return their sizes,
 then that&#39;s a problem that needs to be handled at the specification le=
vel, not in a specific container class.<br><br></div><blockquote class=3D"g=
mail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc sol=
id;padding-left: 1ex;"><div dir=3D"ltr"><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:=
1ex"><div dir=3D"ltr"><div>And having a sentinel value rather than a genuin=
e size; that&#39;s just begging for someone to break the container. Even `b=
asic_string`, a type designed specifically for such a use case, doesn&#39;t=
 actually use the NUL character to determine the string&#39;s size.<br></di=
v></div></blockquote><div><br></div><div>I&#39;ve used the sentinel in prod=
uction code as well.</div></div></blockquote><div><br>I never said that nob=
ody uses such things in production code. I said that it&#39;s not something=
 the standard library should support. It&#39;s just too fragile of a contai=
ner for the standard library.<br><br></div><blockquote class=3D"gmail_quote=
" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding=
-left: 1ex;"><div dir=3D"ltr"><div>Again I don&#39;t need to store a size v=
ariable anywhere, saving valuable cache space. The most common use case for=
 this is when you have a list of pointers to callbacks to be iterated throu=
gh. All of the pointers except the last one are null.</div><div><br></div><=
div>This makes size() and push_back() slow, but in my use case it was a sit=
uation where I set everything up on startup and then need to iterate the li=
st over and over again in the hotpath. I don&#39;t give a damn about a bit =
slower slow setup (not even measurable in real tests), when it buys me the =
fastest possible iteration loop.</div><div><br></div><div>This optimizes th=
e hell out of iteration. After optimization its essentially this:</div><div=
><div style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,1=
87);border-style:solid;border-width:1px;word-wrap:break-word"><font face=3D=
"monospace" color=3D"#000000">for(T**p =3D v.data(); *p !=3D nullptr; ++p) =
{<br>=C2=A0 doSomething(*p);<br>}</font></div><br></div></div></blockquote>=
<div><br>Which you can do right now by manually putting a NULL pointer at t=
he end of the list. This sounds like something best handled by some kind of=
 iterator/range adapter, not by changing the container itself. Indeed, by m=
aking it an adapter rather than part of the class, it can now be used for l=
ots of tasks, the equivalent of doing a loop until you reach the value that=
 `find_if` would return.<br><br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left=
: 1ex;"><div dir=3D"ltr"><div>The vector itself only stores a single pointe=
r and is only 8 bytes in size.</div></div></blockquote><div><br>So you crea=
te this incredibly fragile container... just to save 16 bytes.<br><br></div=
><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bo=
rder-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div></div><=
div>Capacity can either be a function of size (size % N, next power of 2, e=
tc..) or a static compile time upper bound.</div></div></blockquote><div><b=
r>Um, if the capacity is a function of the size, then the capacity must cha=
nge whenever the size does. Which makes the capacity functionally useless; =
it will have to reallocate on any insertion or removal.<br><br></div><block=
quote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-le=
ft: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div></div><div>Now=
 I agree that this is easy to use wrong in the general case. But again, omn=
i_vec is a toolbox that doesn&#39;t always have to stand on its own in the =
wild. I can create a sentinel based omni_vec inside and then further wrap i=
t in a safer interface.</div><div><br></div><div>I think the decision for s=
tring was more about 2 things: (1) allowing for strings with embedded nulls=
 (mandatory for binary string data) and (2) making size() O(1). For string =
data, this is the right trade-off because in the context of string, those a=
re 2 very important properties to have. For some other generic situations, =
they may not be necessary.</div><div><br></div><div>One might also want to =
make a C style null terminated string type which doesn&#39;t store the size=
, and they could easily start out by using omni_vec&lt;char,Traits&gt; to d=
efine the storage policy and build a semantic string wrapper on-top.</div><=
div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-=
left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><d=
iv>Similarly, no form of `vector` should support &quot;Bit Storage and prox=
y iterators&quot;. `vector&lt;T&gt;` is supposed to mean &quot;contiguous s=
torage of `T`&quot;, and every form of `vector` ought to provide that.<br><=
/div></div></blockquote><div><br></div><div>I think my original idea of usi=
ng some kind of type T to enable this is wrong, as its similar to vector&lt=
;bool&gt;. Certaintly though it could make sense to add a traits parameter =
to enable bitset behavior, with a static_assert() that T is bool.</div><div=
><br></div><div>Iterating over bits is fundamentally different than iterati=
ng over T. I agree that it is a bit uncomfortable how it crosses the turf o=
f vector a bitset. However, if we added some facility to omni_vec, it means=
 we get all the storage foundations for all possible bitsets for free.</div=
><div><br></div><div>Bitsets operate exactly like vectors and arrays.</div>=
</div></blockquote><div><br>No, they do not. A `vector&lt;T&gt;` is a conti=
guous container of `T`s, which can be iterated over and accessed by pointer=
s. A bitset isn&#39;t that. So no, they do not &quot;operate <i>exactly</i>=
&quot; like `vector`.<br><br>You can use a `vector` to <i>create</i> a bits=
et, but that&#39;s different from a bitset actually <i>being</i> a speciali=
zation of `vector`. I could even imagine a new `bitset` class that takes th=
e same parameters as `omni_vector`, forwarding them to an internal `vector`=
 implementation.<br>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"=
margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;=
"><div dir=3D"ltr"><div>The only difference is that bits need special handl=
ing because they can&#39;t be represented with a type T directly.</div><div=
><br></div><div>Another option could be an omni_bitset, which uses the exac=
t same traits as omni_vec but has bitset semantics.</div><div><br></div><di=
v>I guess the idea I&#39;m envisioning here is a completely flexible array-=
like storage backend for any possible kind of array like thing you would wa=
nt. Simple inheritance/composition can be used to add additional semantic l=
ayers as needed (strings, bitsets, circular buffers, etc..).</div></div></b=
lockquote><div><br>You can use `vector` in an implementation of bitset as i=
t currently stands; you don&#39;t need to shove bitset functionality <i>int=
o</i> `vector` to do that. You&#39;ll just have to write a bit more code.<b=
r><br>And that &quot;bit more code&quot; is not the hard code of implementi=
ng `vector`.</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/92026194-86f7-4e1d-94e5-d5c0f1cfd602%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/92026194-86f7-4e1d-94e5-d5c0f1cfd602=
%40isocpp.org</a>.<br />

------=_Part_5550_1891250717.1492459499891--

------=_Part_5549_1456587966.1492459499890--

.

------=_Part_241_288065310.1492463804493
Content-Type: multipart/alternative;
 boundary="----=_Part_242_951793341.1492463804493"

------=_Part_242_951793341.1492463804493
Content-Type: text/plain; charset=UTF-8



On Monday, April 17, 2017 at 3:05:00 PM UTC-5, Nicol Bolas wrote:
>
> You assume that `size_type` is actually stored in the `vector` to contain
> the size. Many `vector` implementations simply contain 3 pointers,
> computing `size` and `capacity` as needed.
>
> So controlling `size_type` will not help you on such implementations.
>

I would suggest that for omni_vec, if sizeof(size_type) <
sizeof(ptrdiff_t), a space saving integer counter implementation must be
used instead of pointers. Otherwise then yes the option is completely
pointless.


>
> Signed size_type also might let me finally start using gcc's -Wconversion
>> without getting a ton of false positives. I don't use -Wconversion because
>> all of the required casts around STL containers can easily cause bugs of
>> their own. Signed size() might also enable optimizations in some cases
>> because the compiler can assume signed arithmetic sourced from a call to
>> size() can never overflow.
>>
>
> And what exactly would control over `size_type` do for that problem *in
> general*? Because it won't change the fact that *every other* container
> uses an unsigned `size_type`. Nor will it change the fact that `span<T>`
> will use an unsigned `size_type`. Nor will it change the fact that the
> unparameterized `vector` will use an unsigned `size_type`. Nor will it
> change the fact that someone else can pass you a `vector` that uses an
> unsigned `size_type`.
>

While it wouldn't fix the problem in the general case (we're already
screwed for that), it would fix the majority of use cases. First at least
for me, I already use vector or something vector-like 90% of the time.
Second, most of the time when I do need to work with the size() of the
container, that container is a vector. Most commonly in an index based for
loop. While size() is sometimes useful for unordered_map and other things,
I find myself querying it far less often in those cases than I do with
arrays and certainly even less often needing to compare it with signed
values.


>
> Also, `container::size_type` is *required* by the standard to be an
> unsigned integer, big enough to store any non-negative value of
> `container::difference_type`. If you have a problem with the way
> containers/ranges return their sizes, then that's a problem that needs to
> be handled at the specification level, not in a specific container class.
>

I remember one of the C++ talks (I think it was a microsoft conference?)
where some of the C++ committee members actually admitted publicly using
unsigned types for container sizes was a mistake. I don't remember which
talk this was.

But you are right the question of signed vs unsigned size() is a bigger
issue than what we're talking about here. Again, the ship has probably
sailed on this unless we do stl 2.0 full rewrite.



>
> And having a sentinel value rather than a genuine size; that's just
>>> begging for someone to break the container. Even `basic_string`, a type
>>> designed specifically for such a use case, doesn't actually use the NUL
>>> character to determine the string's size.
>>>
>>
>> I've used the sentinel in production code as well.
>>
>
> I never said that nobody uses such things in production code. I said that
> it's not something the standard library should support. It's just too
> fragile of a container for the standard library.
>

Why does everything in the standard library need to be an idiot proof
novice friendly all out complete solution? I'd really like to see more
expert level building block style tools we can use to quickly construct our
own types and avoid the boilerplate, drudgery, testing, and bugs coming
from rewriting the basics over and over again.

This is not the only unsafe container with loose semantics I've had to
write before. There's nothing wrong with a slightly dangerous interface
that's almost always intended to be wrapped in a safer more well defined
and application specific interface which use it in slightly different ways
depending on context.

std::mutex and std::atomic are good examples of sharp tools most people
would recommend only experts use and carefully abstract away from the
general application code whenever possible.



>
> Again I don't need to store a size variable anywhere, saving valuable
>> cache space. The most common use case for this is when you have a list of
>> pointers to callbacks to be iterated through. All of the pointers except
>> the last one are null.
>>
>> This makes size() and push_back() slow, but in my use case it was a
>> situation where I set everything up on startup and then need to iterate the
>> list over and over again in the hotpath. I don't give a damn about a bit
>> slower slow setup (not even measurable in real tests), when it buys me the
>> fastest possible iteration loop.
>>
>> This optimizes the hell out of iteration. After optimization its
>> essentially this:
>> for(T**p = v.data(); *p != nullptr; ++p) {
>>   doSomething(*p);
>> }
>>
>>
> Which you can do right now by manually putting a NULL pointer at the end
> of the list. This sounds like something best handled by some kind of
> iterator/range adapter, not by changing the container itself. Indeed, by
> making it an adapter rather than part of the class, it can now be used for
> lots of tasks, the equivalent of doing a loop until you reach the value
> that `find_if` would return.
>

Adding wrappers on-top doesn't let you optimize out data and logic inside
the underlying data structure that your limited interface doesn't need
anymore. The only thing wrappers can do is improve
correctness by constricting the interface. They can't provide optimization.

I'm still wasting memory storing the size and capacity.  Also in my loop I
need to add an additional check for empty(), otherwise dereferencing the
first element will crash.

I could try to remember at runtime to always allocate one sentinel. That's
an invariant now that has to be guaranteed at runtime, instead of at
compile time with sentinel_vector. Also, sentinel_vector can store one copy
of the sentinel object as a static const data member. Then all empty
sentinel_vectors can avoid allocating at all and their sentinel_nodes all
share the same address, improving cache locality and reducing heap
fragmentation if you have a lot of empty sentinel_vectors.


>
> The vector itself only stores a single pointer and is only 8 bytes in size.
>>
>
> So you create this incredibly fragile container... just to save 16 bytes.
>

Yes, and it resulted in a measurable improvement in application runtime. 16
bytes is already 1/4 of a cache line on Intel.


>
> Capacity can either be a function of size (size % N, next power of 2,
>> etc..) or a static compile time upper bound.
>>
>
> Um, if the capacity is a function of the size, then the capacity must
> change whenever the size does. Which makes the capacity functionally
> useless; it will have to reallocate on any insertion or removal.
>

Not exactly. If capacity is ceil_pow2(size()), the capacity stays constant
until your size hits the next power of 2 boundary.  For push_back(), just
check if size is a power of 2, if so you need to reallocate more up to the
next boundary.

The modulus example is like a linear growth factor. For example if N is 5,
you'll reallocate when size is 5, 10, 15, etc..

These options are not appropriate if you want insertion/removal to be fast.
Many times however, we just do setup once and then need to iterate (read)
over and over again in the hot path. Any kind of simulation use case where
you set everything up and then run the simulation has this general
paradigm. Sometimes we only need to push_back() and never do any removal
until we tear down the whole system at shutdown.

Finally, the other example is static_vector<T,N>, where the capacity is a
compile time constant. Essentially now you've got a fixed upper bound on
the number of things you can store, and instead of storing and checking
size, you have a sentinel.

Admittedly for many uses, storing the size counter inside the allocated
memory buffer could be a good alternative to using a sentinel. You still
get the space savings in the container. Empty vectors again could point to
a static 0 size_type somewhere to avoid allocations, and now you avoid all
of that messy fragility of the sentinel.




>
> Now I agree that this is easy to use wrong in the general case. But again,
>> omni_vec is a toolbox that doesn't always have to stand on its own in the
>> wild. I can create a sentinel based omni_vec inside and then further wrap
>> it in a safer interface.
>>
>> I think the decision for string was more about 2 things: (1) allowing for
>> strings with embedded nulls (mandatory for binary string data) and (2)
>> making size() O(1). For string data, this is the right trade-off because in
>> the context of string, those are 2 very important properties to have. For
>> some other generic situations, they may not be necessary.
>>
>> One might also want to make a C style null terminated string type which
>> doesn't store the size, and they could easily start out by using
>> omni_vec<char,Traits> to define the storage policy and build a semantic
>> string wrapper on-top.
>>
>>
>>> Similarly, no form of `vector` should support "Bit Storage and proxy
>>> iterators". `vector<T>` is supposed to mean "contiguous storage of `T`",
>>> and every form of `vector` ought to provide that.
>>>
>>
>> I think my original idea of using some kind of type T to enable this is
>> wrong, as its similar to vector<bool>. Certaintly though it could make
>> sense to add a traits parameter to enable bitset behavior, with a
>> static_assert() that T is bool.
>>
>> Iterating over bits is fundamentally different than iterating over T. I
>> agree that it is a bit uncomfortable how it crosses the turf of vector a
>> bitset. However, if we added some facility to omni_vec, it means we get all
>> the storage foundations for all possible bitsets for free.
>>
>> Bitsets operate exactly like vectors and arrays.
>>
>
> No, they do not. A `vector<T>` is a contiguous container of `T`s, which
> can be iterated over and accessed by pointers. A bitset isn't that. So no,
> they do not "operate *exactly*" like `vector`.
>
> You can use a `vector` to *create* a bitset, but that's different from a
> bitset actually *being* a specialization of `vector`. I could even
> imagine a new `bitset` class that takes the same parameters as
> `omni_vector`, forwarding them to an internal `vector` implementation.
>
>
>> The only difference is that bits need special handling because they can't
>> be represented with a type T directly.
>>
>> Another option could be an omni_bitset, which uses the exact same traits
>> as omni_vec but has bitset semantics.
>>
>> I guess the idea I'm envisioning here is a completely flexible array-like
>> storage backend for any possible kind of array like thing you would want.
>> Simple inheritance/composition can be used to add additional semantic
>> layers as needed (strings, bitsets, circular buffers, etc..).
>>
>
> You can use `vector` in an implementation of bitset as it currently
> stands; you don't need to shove bitset functionality *into* `vector` to
> do that. You'll just have to write a bit more code.
>
> And that "bit more code" is not the hard code of implementing `vector`.
>

Fair enough.

Anyway after thinking about it more, if we wanted to talk about bitset, I
think omni_bitset<Traits> would be the way to go. It can be implemented
ontop of omni_vec as you suggested and all the bitset related proxy hackery
kept cleanly separated.

Some configuration options just make no sense for bitset (example:
sentinels) and should be static_asserted away.

Also, bitset has some other configuration parameters you might want to
tweak with traits.

Specifically controlling the word size and alignment used to construct it.
Right now std::bitset<T,32> on gcc uses 64 bits. This makes it space
inefficient at best and unusable at worse. A good example is a struct which
is supposed to overlay binary protocols such as network packet headers. If
I could control the size and alignment of my bitset, I could overlay it
directly over binary data without making copies. Then I can manipulate my
data using the nice already tested bitset interface instead of hacking my
own logical ops.

I tried to propose something like this for bitset before and it failed to
go through. If we had an omni_bitset, these fine controls would fall in
nicely and it would be better than trying to add them to std::bitset and
breaking ABI compatibility.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/0e40ab99-3066-4579-8f51-0db825d814f7%40isocpp.org.

------=_Part_242_951793341.1492463804493
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, April 17, 2017 at 3:05:00 PM UTC-5, Nic=
ol Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-=
left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr=
"><div>You assume that `size_type` is actually stored in the `vector` to co=
ntain the size. Many `vector` implementations simply contain 3 pointers, co=
mputing `size` and `capacity` as needed.<br><br>So controlling `size_type` =
will not help you on such implementations.<br></div></div></blockquote><div=
><br></div><div>I would suggest that for omni_vec, if sizeof(size_type) &lt=
; sizeof(ptrdiff_t), a space saving integer counter implementation must be =
used instead of pointers. Otherwise then yes the option is completely point=
less.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"marg=
in: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><d=
iv dir=3D"ltr"><div><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div =
dir=3D"ltr"><div></div><div>Signed size_type also might let me finally star=
t using gcc&#39;s -Wconversion without getting a ton of false positives. I =
don&#39;t use -Wconversion because all of the required casts around STL con=
tainers can easily cause bugs of their own. Signed size() might also enable=
 optimizations in some cases because the compiler can assume signed arithme=
tic sourced from a call to size() can never overflow.</div></div></blockquo=
te><div><br>And what exactly would control over `size_type` do for that pro=
blem <i>in general</i>? Because it won&#39;t change the fact that <i>every =
other</i> container uses an unsigned `size_type`. Nor will it change the fa=
ct that `span&lt;T&gt;` will use an unsigned `size_type`. Nor will it chang=
e the fact that the unparameterized `vector` will use an unsigned `size_typ=
e`. Nor will it change the fact that someone else can pass you a `vector` t=
hat uses an unsigned `size_type`.<br></div></div></blockquote><div><br></di=
v><div>While it wouldn&#39;t fix the problem in the general case (we&#39;re=
 already screwed for that), it would fix the majority of use cases. First a=
t least for me, I already use vector or something vector-like 90% of the ti=
me. Second, most of the time when I do need to work with the size() of the =
container, that container is a vector. Most commonly in an index based for =
loop. While size() is sometimes useful for unordered_map and other things, =
I find myself querying it far less often in those cases than I do with arra=
ys and certainly even less often needing to compare it with signed values.<=
/div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;=
margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr"><div><br>Also, `container::size_type` is <i>required</i> by the st=
andard to be an unsigned integer, big enough to store any non-negative valu=
e of `container::difference_type`. If you have a problem with the way conta=
iners/ranges return their sizes,
 then that&#39;s a problem that needs to be handled at the specification le=
vel, not in a specific container class.<br></div></div></blockquote><div><b=
r></div><div>I remember one of the C++ talks (I think it was a microsoft co=
nference?) where some of the C++ committee members actually admitted public=
ly using unsigned types for container sizes was a mistake. I don&#39;t reme=
mber which talk this was.</div><div><br></div><div>But you are right the qu=
estion of signed vs unsigned size() is a bigger issue than what we&#39;re t=
alking about here. Again, the ship has probably sailed on this unless we do=
 stl 2.0 full rewrite.</div><div><br></div><div>=C2=A0</div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #=
ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #c=
cc solid;padding-left:1ex"><div dir=3D"ltr"><blockquote class=3D"gmail_quot=
e" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-l=
eft:1ex"><div dir=3D"ltr"><div>And having a sentinel value rather than a ge=
nuine size; that&#39;s just begging for someone to break the container. Eve=
n `basic_string`, a type designed specifically for such a use case, doesn&#=
39;t actually use the NUL character to determine the string&#39;s size.<br>=
</div></div></blockquote><div><br></div><div>I&#39;ve used the sentinel in =
production code as well.</div></div></blockquote><div><br>I never said that=
 nobody uses such things in production code. I said that it&#39;s not somet=
hing the standard library should support. It&#39;s just too fragile of a co=
ntainer for the standard library.<br></div></div></blockquote><div><br></di=
v><div>Why does everything in the standard library need to be an idiot proo=
f novice friendly all out complete solution? I&#39;d really like to see mor=
e expert level building block style tools we can use to quickly construct o=
ur own types and avoid the boilerplate, drudgery, testing, and bugs coming =
from rewriting the basics over and over again.</div><div><br></div><div>Thi=
s is not the only unsafe container with loose semantics I&#39;ve had to wri=
te before. There&#39;s nothing wrong with a slightly dangerous interface th=
at&#39;s almost always intended to be wrapped in a safer more well defined =
and application specific interface which use it in slightly different ways =
depending on context.</div><div><br></div><div>std::mutex and std::atomic a=
re good examples of sharp tools most people would recommend only experts us=
e and carefully abstract away from the general application code whenever po=
ssible.</div><div><br></div><div>=C2=A0</div><blockquote class=3D"gmail_quo=
te" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;paddi=
ng-left: 1ex;"><div dir=3D"ltr"><div><br></div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;paddin=
g-left:1ex"><div dir=3D"ltr"><div>Again I don&#39;t need to store a size va=
riable anywhere, saving valuable cache space. The most common use case for =
this is when you have a list of pointers to callbacks to be iterated throug=
h. All of the pointers except the last one are null.</div><div><br></div><d=
iv>This makes size() and push_back() slow, but in my use case it was a situ=
ation where I set everything up on startup and then need to iterate the lis=
t over and over again in the hotpath. I don&#39;t give a damn about a bit s=
lower slow setup (not even measurable in real tests), when it buys me the f=
astest possible iteration loop.</div><div><br></div><div>This optimizes the=
 hell out of iteration. After optimization its essentially this:</div><div>=
<div style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,18=
7);border-style:solid;border-width:1px;word-wrap:break-word"><font face=3D"=
monospace" color=3D"#000000">for(T**p =3D v.data(); *p !=3D nullptr; ++p) {=
<br>=C2=A0 doSomething(*p);<br>}</font></div><br></div></div></blockquote><=
div><br>Which you can do right now by manually putting a NULL pointer at th=
e end of the list. This sounds like something best handled by some kind of =
iterator/range adapter, not by changing the container itself. Indeed, by ma=
king it an adapter rather than part of the class, it can now be used for lo=
ts of tasks, the equivalent of doing a loop until you reach the value that =
`find_if` would return.<br></div></div></blockquote><div><br></div><div>Add=
ing wrappers on-top doesn&#39;t let you optimize out data and logic inside =
the underlying data structure that your limited interface doesn&#39;t need =
anymore. The only thing wrappers can do is improve</div><div>correctness by=
 constricting the interface. They can&#39;t provide optimization.</div><div=
><br></div><div>I&#39;m still wasting memory storing the size and capacity.=
 =C2=A0Also in my loop I need to add an additional check for empty(), other=
wise dereferencing the first element will crash.</div><div><br></div><div>I=
 could try to remember at runtime to always allocate one sentinel. That&#39=
;s an invariant now that has to be guaranteed at runtime, instead of at com=
pile time with sentinel_vector. Also, sentinel_vector can store one copy of=
 the sentinel object as a static const data member. Then all empty sentinel=
_vectors can avoid allocating at all and their sentinel_nodes all share the=
 same address, improving cache locality and reducing heap fragmentation if =
you have a lot of empty sentinel_vectors.</div><div>=C2=A0</div><blockquote=
 class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1=
px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><br></div><blockquo=
te class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>The vector itself only=
 stores a single pointer and is only 8 bytes in size.</div></div></blockquo=
te><div><br>So you create this incredibly fragile container... just to save=
 16 bytes.<br></div></div></blockquote><div><br></div><div>Yes, and it resu=
lted in a measurable improvement in application runtime. 16 bytes is alread=
y 1/4 of a cache line on Intel.</div><div>=C2=A0</div><blockquote class=3D"=
gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc so=
lid;padding-left: 1ex;"><div dir=3D"ltr"><div><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div dir=3D"ltr"><div></div><div>Capacity can either=
 be a function of size (size % N, next power of 2, etc..) or a static compi=
le time upper bound.</div></div></blockquote><div><br>Um, if the capacity i=
s a function of the size, then the capacity must change whenever the size d=
oes. Which makes the capacity functionally useless; it will have to realloc=
ate on any insertion or removal.<br></div></div></blockquote><div><br></div=
><div>Not exactly. If capacity is ceil_pow2(size()), the capacity stays con=
stant until your size hits the next power of 2 boundary. =C2=A0For push_bac=
k(), just check if size is a power of 2, if so you need to reallocate more =
up to the next boundary.</div><div><br></div><div>The modulus example is li=
ke a linear growth factor. For example if N is 5, you&#39;ll reallocate whe=
n size is 5, 10, 15, etc..</div><div><br></div><div>These options are not a=
ppropriate if you want insertion/removal to be fast. Many times however, we=
 just do setup once and then need to iterate (read) over and over again in =
the hot path. Any kind of simulation use case where you set everything up a=
nd then run the simulation has this general paradigm. Sometimes we only nee=
d to push_back() and never do any removal until we tear down the whole syst=
em at shutdown.</div><div><br></div><div>Finally, the other example is stat=
ic_vector&lt;T,N&gt;, where the capacity is a compile time constant. Essent=
ially now you&#39;ve got a fixed upper bound on the number of things you ca=
n store, and instead of storing and checking size, you have a sentinel.</di=
v><div><br></div><div>Admittedly for many uses, storing the size counter in=
side the allocated memory buffer could be a good alternative to using a sen=
tinel. You still get the space savings in the container. Empty vectors agai=
n could point to a static 0 size_type somewhere to avoid allocations, and n=
ow you avoid all of that messy fragility of the sentinel.</div><div><br></d=
iv><div><br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;"><div dir=3D"ltr"><div><br></div><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1e=
x"><div dir=3D"ltr"><div></div><div>Now I agree that this is easy to use wr=
ong in the general case. But again, omni_vec is a toolbox that doesn&#39;t =
always have to stand on its own in the wild. I can create a sentinel based =
omni_vec inside and then further wrap it in a safer interface.</div><div><b=
r></div><div>I think the decision for string was more about 2 things: (1) a=
llowing for strings with embedded nulls (mandatory for binary string data) =
and (2) making size() O(1). For string data, this is the right trade-off be=
cause in the context of string, those are 2 very important properties to ha=
ve. For some other generic situations, they may not be necessary.</div><div=
><br></div><div>One might also want to make a C style null terminated strin=
g type which doesn&#39;t store the size, and they could easily start out by=
 using omni_vec&lt;char,Traits&gt; to define the storage policy and build a=
 semantic string wrapper on-top.</div><div>=C2=A0</div><blockquote class=3D=
"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc soli=
d;padding-left:1ex"><div dir=3D"ltr"><div>Similarly, no form of `vector` sh=
ould support &quot;Bit Storage and proxy iterators&quot;. `vector&lt;T&gt;`=
 is supposed to mean &quot;contiguous storage of `T`&quot;, and every form =
of `vector` ought to provide that.<br></div></div></blockquote><div><br></d=
iv><div>I think my original idea of using some kind of type T to enable thi=
s is wrong, as its similar to vector&lt;bool&gt;. Certaintly though it coul=
d make sense to add a traits parameter to enable bitset behavior, with a st=
atic_assert() that T is bool.</div><div><br></div><div>Iterating over bits =
is fundamentally different than iterating over T. I agree that it is a bit =
uncomfortable how it crosses the turf of vector a bitset. However, if we ad=
ded some facility to omni_vec, it means we get all the storage foundations =
for all possible bitsets for free.</div><div><br></div><div>Bitsets operate=
 exactly like vectors and arrays.</div></div></blockquote><div><br>No, they=
 do not. A `vector&lt;T&gt;` is a contiguous container of `T`s, which can b=
e iterated over and accessed by pointers. A bitset isn&#39;t that. So no, t=
hey do not &quot;operate <i>exactly</i>&quot; like `vector`.<br><br>You can=
 use a `vector` to <i>create</i> a bitset, but that&#39;s different from a =
bitset actually <i>being</i> a specialization of `vector`. I could even ima=
gine a new `bitset` class that takes the same parameters as `omni_vector`, =
forwarding them to an internal `vector` implementation.<br>=C2=A0</div><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-le=
ft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>The only differen=
ce is that bits need special handling because they can&#39;t be represented=
 with a type T directly.</div><div><br></div><div>Another option could be a=
n omni_bitset, which uses the exact same traits as omni_vec but has bitset =
semantics.</div><div><br></div><div>I guess the idea I&#39;m envisioning he=
re is a completely flexible array-like storage backend for any possible kin=
d of array like thing you would want. Simple inheritance/composition can be=
 used to add additional semantic layers as needed (strings, bitsets, circul=
ar buffers, etc..).</div></div></blockquote><div><br>You can use `vector` i=
n an implementation of bitset as it currently stands; you don&#39;t need to=
 shove bitset functionality <i>into</i> `vector` to do that. You&#39;ll jus=
t have to write a bit more code.<br><br>And that &quot;bit more code&quot; =
is not the hard code of implementing `vector`.</div></div></blockquote><div=
><br></div><div>Fair enough.</div><div><br></div><div>Anyway after thinking=
 about it more, if we wanted to talk about bitset, I think omni_bitset&lt;T=
raits&gt; would be the way to go. It can be implemented ontop of omni_vec a=
s you suggested and all the bitset related proxy hackery kept cleanly separ=
ated.</div><div><br></div><div>Some configuration options just make no sens=
e for bitset (example: sentinels) and should be static_asserted away.</div>=
<div><br></div><div>Also, bitset has some other configuration parameters yo=
u might want to tweak with traits.</div><div><br></div><div>Specifically co=
ntrolling the word size and alignment used to construct it. Right now std::=
bitset&lt;T,32&gt; on gcc uses 64 bits. This makes it space inefficient at =
best and unusable at worse. A good example is a struct which is supposed to=
 overlay binary protocols such as network packet headers. If I could contro=
l the size and alignment of my bitset, I could overlay it directly over bin=
ary data without making copies. Then I can manipulate my data using the nic=
e already tested bitset interface instead of hacking my own logical ops.</d=
iv><div><br></div><div>I tried to propose something like this for bitset be=
fore and it failed to go through. If we had an omni_bitset, these fine cont=
rols would fall in nicely and it would be better than trying to add them to=
 std::bitset and breaking ABI compatibility.</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/0e40ab99-3066-4579-8f51-0db825d814f7%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/0e40ab99-3066-4579-8f51-0db825d814f7=
%40isocpp.org</a>.<br />

------=_Part_242_951793341.1492463804493--

------=_Part_241_288065310.1492463804493--

.

------=_Part_2227_1937749974.1492468380092
Content-Type: multipart/alternative;
 boundary="----=_Part_2228_254316246.1492468380092"

------=_Part_2228_254316246.1492468380092
Content-Type: text/plain; charset=UTF-8



On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Nicol Bolas wrote:
>
> On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:
>
>> I've used the sentinel in production code as well.
>>
>
> I never said that nobody uses such things in production code. I said that
> it's not something the standard library should support. It's just too
> fragile of a container for the standard library.
>
> Again I don't need to store a size variable anywhere, saving valuable
>> cache space. The most common use case for this is when you have a list of
>> pointers to callbacks to be iterated through. All of the pointers except
>> the last one are null.
>>
>> This makes size() and push_back() slow, but in my use case it was a
>> situation where I set everything up on startup and then need to iterate the
>> list over and over again in the hotpath. I don't give a damn about a bit
>> slower slow setup (not even measurable in real tests), when it buys me the
>> fastest possible iteration loop.
>>
>> This optimizes the hell out of iteration. After optimization its
>> essentially this:
>> for(T**p = v.data(); *p != nullptr; ++p) {
>>   doSomething(*p);
>> }
>>
>>
> Which you can do right now by manually putting a NULL pointer at the end
> of the list. This sounds like something best handled by some kind of
> iterator/range adapter, not by changing the container itself. Indeed, by
> making it an adapter rather than part of the class, it can now be used for
> lots of tasks, the equivalent of doing a loop until you reach the value
> that `find_if` would return.
>
> The vector itself only stores a single pointer and is only 8 bytes in size.
>>
>
> So you create this incredibly fragile container... just to save 16 bytes.
>

I do not see that will be more fragile than normal `begin`/`end` combo.
Trick would be use pair of iterators from range TS (`begin` and `end`
return different types).
Adding sentinel could be done automatically too.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/ef1d6f85-5cdc-45af-8e98-33d2b7159be7%40isocpp.org.

------=_Part_2228_254316246.1492468380092
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Ni=
col Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"lt=
r">On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:=
<br><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;b=
order-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>I&#39;ve =
used the sentinel in production code as well.</div></div></blockquote><div>=
<br>I never said that nobody uses such things in production code. I said th=
at it&#39;s not something the standard library should support. It&#39;s jus=
t too fragile of a container for the standard library.<br><br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:=
1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Again I don&#39;t ne=
ed to store a size variable anywhere, saving valuable cache space. The most=
 common use case for this is when you have a list of pointers to callbacks =
to be iterated through. All of the pointers except the last one are null.</=
div><div><br></div><div>This makes size() and push_back() slow, but in my u=
se case it was a situation where I set everything up on startup and then ne=
ed to iterate the list over and over again in the hotpath. I don&#39;t give=
 a damn about a bit slower slow setup (not even measurable in real tests), =
when it buys me the fastest possible iteration loop.</div><div><br></div><d=
iv>This optimizes the hell out of iteration. After optimization its essenti=
ally this:</div><div><div style=3D"background-color:rgb(250,250,250);border=
-color:rgb(187,187,187);border-style:solid;border-width:1px;word-wrap:break=
-word"><font face=3D"monospace" color=3D"#000000">for(T**p =3D v.data(); *p=
 !=3D nullptr; ++p) {<br>=C2=A0 doSomething(*p);<br>}</font></div><br></div=
></div></blockquote><div><br>Which you can do right now by manually putting=
 a NULL pointer at the end of the list. This sounds like something best han=
dled by some kind of iterator/range adapter, not by changing the container =
itself. Indeed, by making it an adapter rather than part of the class, it c=
an now be used for lots of tasks, the equivalent of doing a loop until you =
reach the value that `find_if` would return.<br><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div dir=3D"ltr"><div>The vector itself only stores =
a single pointer and is only 8 bytes in size.</div></div></blockquote><div>=
<br>So you create this incredibly fragile container... just to save 16 byte=
s.</div></div></blockquote><div><br>I do not see that will be more fragile =
than normal `begin`/`end` combo. Trick would be use pair of iterators from =
range TS (`begin` and `end` return different types).<br>Adding sentinel cou=
ld be done automatically too.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/ef1d6f85-5cdc-45af-8e98-33d2b7159be7%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/ef1d6f85-5cdc-45af-8e98-33d2b7159be7=
%40isocpp.org</a>.<br />

------=_Part_2228_254316246.1492468380092--

------=_Part_2227_1937749974.1492468380092--

.

------=_Part_580_1004201211.1492468749779
Content-Type: multipart/alternative;
 boundary="----=_Part_581_1908121140.1492468749779"

------=_Part_581_1908121140.1492468749779
Content-Type: text/plain; charset=UTF-8



On Monday, April 17, 2017 at 5:33:00 PM UTC-5, Marcin Jaczewski wrote:
>
>
>
> On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Nicol Bolas wrote:
>>
>> On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:
>>
>>> I've used the sentinel in production code as well.
>>>
>>
>> I never said that nobody uses such things in production code. I said that
>> it's not something the standard library should support. It's just too
>> fragile of a container for the standard library.
>>
>> Again I don't need to store a size variable anywhere, saving valuable
>>> cache space. The most common use case for this is when you have a list of
>>> pointers to callbacks to be iterated through. All of the pointers except
>>> the last one are null.
>>>
>>> This makes size() and push_back() slow, but in my use case it was a
>>> situation where I set everything up on startup and then need to iterate the
>>> list over and over again in the hotpath. I don't give a damn about a bit
>>> slower slow setup (not even measurable in real tests), when it buys me the
>>> fastest possible iteration loop.
>>>
>>> This optimizes the hell out of iteration. After optimization its
>>> essentially this:
>>> for(T**p = v.data(); *p != nullptr; ++p) {
>>>   doSomething(*p);
>>> }
>>>
>>>
>> Which you can do right now by manually putting a NULL pointer at the end
>> of the list. This sounds like something best handled by some kind of
>> iterator/range adapter, not by changing the container itself. Indeed, by
>> making it an adapter rather than part of the class, it can now be used for
>> lots of tasks, the equivalent of doing a loop until you reach the value
>> that `find_if` would return.
>>
>> The vector itself only stores a single pointer and is only 8 bytes in
>>> size.
>>>
>>
>> So you create this incredibly fragile container... just to save 16 bytes.
>>
>
> I do not see that will be more fragile than normal `begin`/`end` combo.
> Trick would be use pair of iterators from range TS (`begin` and `end`
> return different types).
> Adding sentinel could be done automatically too.
>

The fragility comes not from iteration, but mutation. For example with
sentintel_vector<std::unique_ptr<T>> with nullptr sentinel. There's
basically nothing stopping me from inserting a nullptr somewhere in the
middle and completely screwing up the size calculation, leaking the
trailing pointers in the process after the sentinel_vector is destroyed.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3fd71d09-dd77-4802-ace1-b4a4ae7dfd90%40isocpp.org.

------=_Part_581_1908121140.1492468749779
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, April 17, 2017 at 5:33:00 PM UTC-5, Mar=
cin Jaczewski wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;ma=
rgin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr"><br><br>On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Nicol Bola=
s wrote:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monday,=
 April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>I&#39;ve used the sent=
inel in production code as well.</div></div></blockquote><div><br>I never s=
aid that nobody uses such things in production code. I said that it&#39;s n=
ot something the standard library should support. It&#39;s just too fragile=
 of a container for the standard library.<br><br></div><blockquote class=3D=
"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc soli=
d;padding-left:1ex"><div dir=3D"ltr"><div>Again I don&#39;t need to store a=
 size variable anywhere, saving valuable cache space. The most common use c=
ase for this is when you have a list of pointers to callbacks to be iterate=
d through. All of the pointers except the last one are null.</div><div><br>=
</div><div>This makes size() and push_back() slow, but in my use case it wa=
s a situation where I set everything up on startup and then need to iterate=
 the list over and over again in the hotpath. I don&#39;t give a damn about=
 a bit slower slow setup (not even measurable in real tests), when it buys =
me the fastest possible iteration loop.</div><div><br></div><div>This optim=
izes the hell out of iteration. After optimization its essentially this:</d=
iv><div><div style=3D"background-color:rgb(250,250,250);border-color:rgb(18=
7,187,187);border-style:solid;border-width:1px;word-wrap:break-word"><font =
face=3D"monospace" color=3D"#000000">for(T**p =3D v.data(); *p !=3D nullptr=
; ++p) {<br>=C2=A0 doSomething(*p);<br>}</font></div><br></div></div></bloc=
kquote><div><br>Which you can do right now by manually putting a NULL point=
er at the end of the list. This sounds like something best handled by some =
kind of iterator/range adapter, not by changing the container itself. Indee=
d, by making it an adapter rather than part of the class, it can now be use=
d for lots of tasks, the equivalent of doing a loop until you reach the val=
ue that `find_if` would return.<br><br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-=
left:1ex"><div dir=3D"ltr"><div>The vector itself only stores a single poin=
ter and is only 8 bytes in size.</div></div></blockquote><div><br>So you cr=
eate this incredibly fragile container... just to save 16 bytes.</div></div=
></blockquote><div><br>I do not see that will be more fragile than normal `=
begin`/`end` combo. Trick would be use pair of iterators from range TS (`be=
gin` and `end` return different types).<br>Adding sentinel could be done au=
tomatically too.<br></div></div></blockquote><div><br></div><div>The fragil=
ity comes not from iteration, but mutation. For example with sentintel_vect=
or&lt;std::unique_ptr&lt;T&gt;&gt; with nullptr sentinel. There&#39;s basic=
ally nothing stopping me from inserting a nullptr somewhere in the middle a=
nd completely screwing up the size calculation, leaking the trailing pointe=
rs in the process after the sentinel_vector is destroyed.</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3fd71d09-dd77-4802-ace1-b4a4ae7dfd90%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3fd71d09-dd77-4802-ace1-b4a4ae7dfd90=
%40isocpp.org</a>.<br />

------=_Part_581_1908121140.1492468749779--

------=_Part_580_1004201211.1492468749779--

.

------=_Part_1945_1037377417.1492484733089
Content-Type: multipart/alternative;
 boundary="----=_Part_1946_1687146970.1492484733090"

------=_Part_1946_1687146970.1492484733090
Content-Type: text/plain; charset=UTF-8

On Monday, April 17, 2017 at 5:16:44 PM UTC-4, Matthew Fioravante wrote:
>
> On Monday, April 17, 2017 at 3:05:00 PM UTC-5, Nicol Bolas wrote:
>>
>> You assume that `size_type` is actually stored in the `vector` to contain
>> the size. Many `vector` implementations simply contain 3 pointers,
>> computing `size` and `capacity` as needed.
>>
>> So controlling `size_type` will not help you on such implementations.
>>
>
> I would suggest that for omni_vec, if sizeof(size_type) <
> sizeof(ptrdiff_t), a space saving integer counter implementation must be
> used instead of pointers. Otherwise then yes the option is completely
> pointless.
>
>
>>
>> Signed size_type also might let me finally start using gcc's -Wconversion
>>> without getting a ton of false positives. I don't use -Wconversion because
>>> all of the required casts around STL containers can easily cause bugs of
>>> their own. Signed size() might also enable optimizations in some cases
>>> because the compiler can assume signed arithmetic sourced from a call to
>>> size() can never overflow.
>>>
>>
>> And what exactly would control over `size_type` do for that problem *in
>> general*? Because it won't change the fact that *every other* container
>> uses an unsigned `size_type`. Nor will it change the fact that `span<T>`
>> will use an unsigned `size_type`. Nor will it change the fact that the
>> unparameterized `vector` will use an unsigned `size_type`. Nor will it
>> change the fact that someone else can pass you a `vector` that uses an
>> unsigned `size_type`.
>>
>
> While it wouldn't fix the problem in the general case (we're already
> screwed for that), it would fix the majority of use cases. First at least
> for me, I already use vector or something vector-like 90% of the time.
> Second, most of the time when I do need to work with the size() of the
> container, that container is a vector. Most commonly in an index based for
> loop. While size() is sometimes useful for unordered_map and other things,
> I find myself querying it far less often in those cases than I do with
> arrays and certainly even less often needing to compare it with signed
> values.
>
>
>>
>> Also, `container::size_type` is *required* by the standard to be an
>> unsigned integer, big enough to store any non-negative value of
>> `container::difference_type`. If you have a problem with the way
>> containers/ranges return their sizes, then that's a problem that needs to
>> be handled at the specification level, not in a specific container class.
>>
>
> I remember one of the C++ talks (I think it was a microsoft conference?)
> where some of the C++ committee members actually admitted publicly using
> unsigned types for container sizes was a mistake. I don't remember which
> talk this was.
>
> But you are right the question of signed vs unsigned size() is a bigger
> issue than what we're talking about here. Again, the ship has probably
> sailed on this unless we do stl 2.0 full rewrite.
>
>
>
>>
>> And having a sentinel value rather than a genuine size; that's just
>>>> begging for someone to break the container. Even `basic_string`, a type
>>>> designed specifically for such a use case, doesn't actually use the NUL
>>>> character to determine the string's size.
>>>>
>>>
>>> I've used the sentinel in production code as well.
>>>
>>
>> I never said that nobody uses such things in production code. I said that
>> it's not something the standard library should support. It's just too
>> fragile of a container for the standard library.
>>
>
> Why does everything in the standard library need to be an idiot proof
> novice friendly all out complete solution?
>

There's a lot of space between "not easily broken" and "idiot proof novice
friendly all out complete solution". Consider `vector` itself. Invalidating
iterators/pointers in a `vector` is a source of bugs for some people who
aren't familiar with the quirks of that type. Yet we still have `vector`,
and we recommend its use essentially for all sequence container tasks (and
for some non-sequence-container tasks).

It's not idiot proof. But it's not easy to break either.


> I'd really like to see more expert level building block style tools we can
> use to quickly construct our own types and avoid the boilerplate, drudgery,
> testing, and bugs coming from rewriting the basics over and over again.
>

This type is not for all C++ experts. It's for C++ experts who *really care*
about 16 bytes, who care so much that they're willing to use a very fiddly
type to achieve their goals (not to mention the capacity issues,
essentially allocating more memory than is needed). So you're not talking
about what every C++ expert would use; you're talking about a very specific
subset of C++ experts.

This sort of thing can go on and on and on. Everyone has some need, some
tool that they use which might be useful to someone else. *At some point*,
you have to decide that something is too small of a corner case for the
standard library. At some point, you *have to* tell people to go implement
it themselves.

I can see broad utility for a lot of these options: small storage, fixed
capacity, the combination of the two, and others. These tools are useful to
more than just C++ experts who work in very specific, high-performance
code. It's a lot harder to show that sentinel vectors have such broad
utility.

This is not the only unsafe container with loose semantics I've had to
> write before. There's nothing wrong with a slightly dangerous interface
> that's almost always intended to be wrapped in a safer more well defined
> and application specific interface which use it in slightly different ways
> depending on context.
>
> std::mutex and std::atomic are good examples of sharp tools most people
> would recommend only experts use and carefully abstract away from the
> general application code whenever possible.
>

This is not a question of "let's not give people easily broken low-level
tools". It's "when giving people exceedingly fragile tools, let's examine
the cost/benefit of doing so". If you don't standardize low-level thread
synchronization tools, then users will be unable to effectively use
threading without using platform-dependent tools and/or other libraries.

So on the one had, you have the large burden on the standard to define its
behavior (which includes the various interactions with other parameters),
implementers to implement it (which again includes the various interactions
with other parameters), and users to use it without breaking it. And all of
this effort benefits only a small group of users.

Again I don't need to store a size variable anywhere, saving valuable cache
>>> space. The most common use case for this is when you have a list of
>>> pointers to callbacks to be iterated through. All of the pointers except
>>> the last one are null.
>>>
>>> This makes size() and push_back() slow, but in my use case it was a
>>> situation where I set everything up on startup and then need to iterate the
>>> list over and over again in the hotpath. I don't give a damn about a bit
>>> slower slow setup (not even measurable in real tests), when it buys me the
>>> fastest possible iteration loop.
>>>
>>> This optimizes the hell out of iteration. After optimization its
>>> essentially this:
>>> for(T**p = v.data(); *p != nullptr; ++p) {
>>>   doSomething(*p);
>>> }
>>>
>>>
>> Which you can do right now by manually putting a NULL pointer at the end
>> of the list. This sounds like something best handled by some kind of
>> iterator/range adapter, not by changing the container itself. Indeed, by
>> making it an adapter rather than part of the class, it can now be used for
>> lots of tasks, the equivalent of doing a loop until you reach the value
>> that `find_if` would return.
>>
>
> Adding wrappers on-top doesn't let you optimize out data and logic inside
> the underlying data structure that your limited interface doesn't need
> anymore. The only thing wrappers can do is improve
> correctness by constricting the interface. They can't provide optimization.
>

Your example was of iterating over such a range. The optimization in
question was about the mechanism of iteration ("*This optimizes the hell
out of iteration*"), not of the size of the container. So the adapter does
provide the optimization you were asking for. As well as providing that
same optimization *elsewhere* too, such as with `span`, `array`,
`string_view`, and other types.

----

I think you mentioned something in one of your posts about the difficulty
of correctly implementing `vector`-style types. It occurs to me that we
could add utilities that make such implementations easier to write. For
example, a function like `std::uninitialized_copy`, but unlike that
function, this one will perform rollbacks on the newly constructed memory
on exceptions. They will also use the allocator's `construct` function.
There would be functions for shifting elements up/down , but with proper
exception support built into them and vector's specific copy/move behavior
based on the properties of `T`. And so forth.

Once all of the tools are available, then writing a `vector` type would be
a lot easier. What we lack is a comprehensive enumeration of the tools that
we need.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/3ff8ca82-fe42-4b2d-858e-bb98afae1cd9%40isocpp.org.

------=_Part_1946_1687146970.1492484733090
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On Monday, April 17, 2017 at 5:16:44 PM UTC-4, Matthew Fio=
ravante wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
>On Monday, April 17, 2017 at 3:05:00 PM UTC-5, Nicol Bolas wrote:<blockquo=
te class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>You assume that `size_=
type` is actually stored in the `vector` to contain the size. Many `vector`=
 implementations simply contain 3 pointers, computing `size` and `capacity`=
 as needed.<br><br>So controlling `size_type` will not help you on such imp=
lementations.<br></div></div></blockquote><div><br></div><div>I would sugge=
st that for omni_vec, if sizeof(size_type) &lt; sizeof(ptrdiff_t), a space =
saving integer counter implementation must be used instead of pointers. Oth=
erwise then yes the option is completely pointless.</div><div>=C2=A0</div><=
blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border=
-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><br></div><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-le=
ft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div></div><div>Signed=
 size_type also might let me finally start using gcc&#39;s -Wconversion wit=
hout getting a ton of false positives. I don&#39;t use -Wconversion because=
 all of the required casts around STL containers can easily cause bugs of t=
heir own. Signed size() might also enable optimizations in some cases becau=
se the compiler can assume signed arithmetic sourced from a call to size() =
can never overflow.</div></div></blockquote><div><br>And what exactly would=
 control over `size_type` do for that problem <i>in general</i>? Because it=
 won&#39;t change the fact that <i>every other</i> container uses an unsign=
ed `size_type`. Nor will it change the fact that `span&lt;T&gt;` will use a=
n unsigned `size_type`. Nor will it change the fact that the unparameterize=
d `vector` will use an unsigned `size_type`. Nor will it change the fact th=
at someone else can pass you a `vector` that uses an unsigned `size_type`.<=
br></div></div></blockquote><div><br></div><div>While it wouldn&#39;t fix t=
he problem in the general case (we&#39;re already screwed for that), it wou=
ld fix the majority of use cases. First at least for me, I already use vect=
or or something vector-like 90% of the time. Second, most of the time when =
I do need to work with the size() of the container, that container is a vec=
tor. Most commonly in an index based for loop. While size() is sometimes us=
eful for unordered_map and other things, I find myself querying it far less=
 often in those cases than I do with arrays and certainly even less often n=
eeding to compare it with signed values.</div><div>=C2=A0</div><blockquote =
class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #=
ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><br>Also, `container::siz=
e_type` is <i>required</i> by the standard to be an unsigned integer, big e=
nough to store any non-negative value of `container::difference_type`. If y=
ou have a problem with the way containers/ranges return their sizes,
 then that&#39;s a problem that needs to be handled at the specification le=
vel, not in a specific container class.<br></div></div></blockquote><div><b=
r></div><div>I remember one of the C++ talks (I think it was a microsoft co=
nference?) where some of the C++ committee members actually admitted public=
ly using unsigned types for container sizes was a mistake. I don&#39;t reme=
mber which talk this was.</div><div><br></div><div>But you are right the qu=
estion of signed vs unsigned size() is a bigger issue than what we&#39;re t=
alking about here. Again, the ship has probably sailed on this unless we do=
 stl 2.0 full rewrite.</div><div><br></div><div>=C2=A0</div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc=
 solid;padding-left:1ex"><div dir=3D"ltr"><div><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div dir=3D"ltr"><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:=
1ex"><div dir=3D"ltr"><div>And having a sentinel value rather than a genuin=
e size; that&#39;s just begging for someone to break the container. Even `b=
asic_string`, a type designed specifically for such a use case, doesn&#39;t=
 actually use the NUL character to determine the string&#39;s size.<br></di=
v></div></blockquote><div><br></div><div>I&#39;ve used the sentinel in prod=
uction code as well.</div></div></blockquote><div><br>I never said that nob=
ody uses such things in production code. I said that it&#39;s not something=
 the standard library should support. It&#39;s just too fragile of a contai=
ner for the standard library.<br></div></div></blockquote><div><br></div><d=
iv>Why does everything in the standard library need to be an idiot proof no=
vice friendly all out complete solution?</div></div></blockquote><div><br>T=
here&#39;s a lot of space between &quot;not easily broken&quot; and &quot;i=
diot proof novice friendly all out complete solution&quot;. Consider `vecto=
r` itself. Invalidating iterators/pointers in a `vector` is a source of bug=
s for some people who aren&#39;t familiar with the quirks of that type. Yet=
 we still have `vector`, and we recommend its use essentially for all seque=
nce container tasks (and for some non-sequence-container tasks).<br><br>It&=
#39;s not idiot proof. But it&#39;s not easy to break either.<br>=C2=A0</di=
v><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;b=
order-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>I&#39;=
d really like to see more expert level building block style tools we can us=
e to quickly construct our own types and avoid the boilerplate, drudgery, t=
esting, and bugs coming from rewriting the basics over and over again.</div=
></div></blockquote><div><br>This type is not for all C++ experts. It&#39;s=
 for C++ experts who <i>really care</i> about 16 bytes, who care so much th=
at they&#39;re willing to use a very fiddly type to achieve their goals (no=
t to mention the capacity issues, essentially allocating more memory than i=
s needed). So you&#39;re not talking about what every C++ expert would use;=
 you&#39;re talking about a very specific subset of C++ experts.<br><br>Thi=
s sort of thing can go on and on and on. Everyone has some need, some tool =
that they use which might be useful to someone else. <i>At some point</i>, =
you have to decide that something is too small of a corner case for the sta=
ndard library. At some point, you <i>have to</i> tell people to go implemen=
t it themselves.<br><br>I can see broad utility for a lot of these options:=
 small storage, fixed capacity, the combination of the two, and others. The=
se tools are useful to more than just C++ experts who work in very specific=
, high-performance code. It&#39;s a lot harder to show that sentinel vector=
s have such broad utility.<br><br></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-le=
ft: 1ex;"><div dir=3D"ltr"><div></div><div>This is not the only unsafe cont=
ainer with loose semantics I&#39;ve had to write before. There&#39;s nothin=
g wrong with a slightly dangerous interface that&#39;s almost always intend=
ed to be wrapped in a safer more well defined and application specific inte=
rface which use it in slightly different ways depending on context.</div><d=
iv><br></div><div>std::mutex and std::atomic are good examples of sharp too=
ls most people would recommend only experts use and carefully abstract away=
 from the general application code whenever possible.</div></div></blockquo=
te><div><br>This is not a question of &quot;let&#39;s not give people easil=
y broken low-level tools&quot;. It&#39;s &quot;when giving people exceeding=
ly fragile tools, let&#39;s examine the cost/benefit of doing so&quot;. If =
you don&#39;t standardize low-level thread synchronization tools, then user=
s will be unable to effectively use threading without using platform-depend=
ent tools and/or other libraries.<br><br>So on the one had, you have the la=
rge burden on the standard to define its behavior (which includes the vario=
us interactions with other parameters), implementers to implement it (which=
 again includes the various interactions with other parameters), and users =
to use it without breaking it. And all of this effort benefits only a small=
 group of users.<br><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">=
<div dir=3D"ltr"><div></div><blockquote class=3D"gmail_quote" style=3D"marg=
in:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div di=
r=3D"ltr"><div></div><blockquote class=3D"gmail_quote" style=3D"margin:0;ma=
rgin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"lt=
r"><div>Again I don&#39;t need to store a size variable anywhere, saving va=
luable cache space. The most common use case for this is when you have a li=
st of pointers to callbacks to be iterated through. All of the pointers exc=
ept the last one are null.</div><div><br></div><div>This makes size() and p=
ush_back() slow, but in my use case it was a situation where I set everythi=
ng up on startup and then need to iterate the list over and over again in t=
he hotpath. I don&#39;t give a damn about a bit slower slow setup (not even=
 measurable in real tests), when it buys me the fastest possible iteration =
loop.</div><div><br></div><div>This optimizes the hell out of iteration. Af=
ter optimization its essentially this:</div><div><div style=3D"background-c=
olor:rgb(250,250,250);border-color:rgb(187,187,187);border-style:solid;bord=
er-width:1px;word-wrap:break-word"><font face=3D"monospace" color=3D"#00000=
0">for(T**p =3D v.data(); *p !=3D nullptr; ++p) {<br>=C2=A0 doSomething(*p)=
;<br>}</font></div><br></div></div></blockquote><div><br>Which you can do r=
ight now by manually putting a NULL pointer at the end of the list. This so=
unds like something best handled by some kind of iterator/range adapter, no=
t by changing the container itself. Indeed, by making it an adapter rather =
than part of the class, it can now be used for lots of tasks, the equivalen=
t of doing a loop until you reach the value that `find_if` would return.<br=
></div></div></blockquote><div><br></div><div>Adding wrappers on-top doesn&=
#39;t let you optimize out data and logic inside the underlying data struct=
ure that your limited interface doesn&#39;t need anymore. The only thing wr=
appers can do is improve</div><div>correctness by constricting the interfac=
e. They can&#39;t provide optimization.</div></div></blockquote><div><br>Yo=
ur example was of iterating over such a range. The optimization in question=
 was about the mechanism of iteration (&quot;<i>This optimizes the hell out=
 of iteration</i>&quot;), not of the size of the container. So the adapter =
does provide the optimization you were asking for. As well as providing tha=
t same optimization <i>elsewhere</i> too, such as with `span`, `array`, `st=
ring_view`, and other types.</div><br>----<br><br>I think you mentioned som=
ething in one of your posts about the difficulty of correctly implementing =
`vector`-style types. It occurs to me that we could add utilities that make=
 such implementations easier to write. For example, a function like `std::u=
ninitialized_copy`, but unlike that function, this one will perform rollbac=
ks on the newly constructed memory on exceptions. They will also use the al=
locator&#39;s `construct` function. There would be functions for shifting e=
lements up/down , but with proper exception support built into them and vec=
tor&#39;s specific copy/move behavior based on the properties of `T`. And s=
o forth.<br><br>Once all of the tools are available, then writing a `vector=
` type would be a lot easier. What we lack is a comprehensive enumeration o=
f the tools that we need.<br></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/3ff8ca82-fe42-4b2d-858e-bb98afae1cd9%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3ff8ca82-fe42-4b2d-858e-bb98afae1cd9=
%40isocpp.org</a>.<br />

------=_Part_1946_1687146970.1492484733090--

------=_Part_1945_1037377417.1492484733089--

.

On Mon, Apr 17, 2017 at 08:05:32PM -0700, Nicol Bolas wrote:
> On Monday, April 17, 2017 at 5:16:44 PM UTC-4, Matthew Fioravante wrote:
> >
> > On Monday, April 17, 2017 at 3:05:00 PM UTC-5, Nicol Bolas wrote:
> >>
> >> I never said that nobody uses such things in production code. I said that
> >> it's not something the standard library should support. It's just too
> >> fragile of a container for the standard library.
> >>
> >
> > Why does everything in the standard library need to be an idiot proof
> > novice friendly all out complete solution?
> >
>
> There's a lot of space between "not easily broken" and "idiot proof novice
> friendly all out complete solution". Consider `vector` itself. Invalidating
> iterators/pointers in a `vector` is a source of bugs for some people who
> aren't familiar with the quirks of that type. Yet we still have `vector`,
> and we recommend its use essentially for all sequence container tasks (and
> for some non-sequence-container tasks).
>
> It's not idiot proof. But it's not easy to break either.

I would claim that there is some validity in this complaint. Consider the
glaring absence of stl::tree (the red-black tree implementation class
underlying stl::set and stl::map, stl refers to SGI STL) from the std
library.

If I remember correctly there was a proposal to add it to one of the
later versions of the standard but it got turned down.

/MF

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170418060315.GA608%40noemi.

.

On Mon, Apr 17, 2017 at 11:28:11AM -0700, Matthew Fioravante wrote:
>
>
> On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote:
> >
> > On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote:
> >>
>
> > Similarly, no form of `vector` should support "Bit Storage and proxy
> > iterators". `vector<T>` is supposed to mean "contiguous storage of `T`",
> > and every form of `vector` ought to provide that.
> >
>
> I think my original idea of using some kind of type T to enable this is
> wrong, as its similar to vector<bool>. Certaintly though it could make
> sense to add a traits parameter to enable bitset behavior, with a
> static_assert() that T is bool.
>
> Iterating over bits is fundamentally different than iterating over T. I
> agree that it is a bit uncomfortable how it crosses the turf of vector a
> bitset. However, if we added some facility to omni_vec, it means we get all
> the storage foundations for all possible bitsets for free.
>
> Bitsets operate exactly like vectors and arrays. The only difference is
> that bits need special handling because they can't be represented with a
> type T directly.

But what about omni_vec<nybble>? Why should bits be more equal than nybbles?

(A nybble is a 4-bit number)

/MF

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170418061213.GB608%40noemi.

.

On Mon, Apr 17, 2017 at 09:51:14AM -0700, Matthew Fioravante wrote:
> As for configuration options, here's all I can think of at the moment:

I think you forgot some options:

1. Capacity is decided upon construction but is treated as constant
   afterwards.
2. Capacity is constant when the omni_vec is non-empty.
3. The growth direction is reversed, this implies the existance of *_front
   and the absence of *_back changers and so this isn't really a container
   at all but it is still useful in some cases.

Given your argumentation that it might be useful at some time then they
should be added but I would happlily agree that at least 3. should be a
separate type.

/MF

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20170418062128.GC608%40noemi.

.

------=_Part_5918_347290259.1492514294996
Content-Type: multipart/alternative;
 boundary="----=_Part_5919_1728286998.1492514294996"

------=_Part_5919_1728286998.1492514294996
Content-Type: text/plain; charset=UTF-8



On Tuesday, April 18, 2017 at 12:39:09 AM UTC+2, Matthew Fioravante wrote:
>
>
>
> On Monday, April 17, 2017 at 5:33:00 PM UTC-5, Marcin Jaczewski wrote:
>>
>>
>>
>> On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Nicol Bolas wrote:
>>>
>>> On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:
>>>
>>>> I've used the sentinel in production code as well.
>>>>
>>>
>>> I never said that nobody uses such things in production code. I said
>>> that it's not something the standard library should support. It's just too
>>> fragile of a container for the standard library.
>>>
>>> Again I don't need to store a size variable anywhere, saving valuable
>>>> cache space. The most common use case for this is when you have a list of
>>>> pointers to callbacks to be iterated through. All of the pointers except
>>>> the last one are null.
>>>>
>>>> This makes size() and push_back() slow, but in my use case it was a
>>>> situation where I set everything up on startup and then need to iterate the
>>>> list over and over again in the hotpath. I don't give a damn about a bit
>>>> slower slow setup (not even measurable in real tests), when it buys me the
>>>> fastest possible iteration loop.
>>>>
>>>> This optimizes the hell out of iteration. After optimization its
>>>> essentially this:
>>>> for(T**p = v.data(); *p != nullptr; ++p) {
>>>>   doSomething(*p);
>>>> }
>>>>
>>>>
>>> Which you can do right now by manually putting a NULL pointer at the end
>>> of the list. This sounds like something best handled by some kind of
>>> iterator/range adapter, not by changing the container itself. Indeed, by
>>> making it an adapter rather than part of the class, it can now be used for
>>> lots of tasks, the equivalent of doing a loop until you reach the value
>>> that `find_if` would return.
>>>
>>> The vector itself only stores a single pointer and is only 8 bytes in
>>>> size.
>>>>
>>>
>>> So you create this incredibly fragile container... just to save 16 bytes.
>>>
>>
>> I do not see that will be more fragile than normal `begin`/`end` combo.
>> Trick would be use pair of iterators from range TS (`begin` and `end`
>> return different types).
>> Adding sentinel could be done automatically too.
>>
>
> The fragility comes not from iteration, but mutation. For example with
> sentintel_vector<std::unique_ptr<T>> with nullptr sentinel. There's
> basically nothing stopping me from inserting a nullptr somewhere in the
> middle and completely screwing up the size calculation, leaking the
> trailing pointers in the process after the sentinel_vector is destroyed.
>

Right, probably only way to prevent it is ban not-const access to elements
outside of vector api. `data` will always return const pointer to array of
`T` but iterators will returns proxies that will check if you write proper
values. But this will create `vector<bool>` v2 and made this more
complicated that is worth.

--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/d069033a-e70b-4996-81da-235ea9560ba9%40isocpp.org.

------=_Part_5919_1728286998.1492514294996
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Tuesday, April 18, 2017 at 12:39:09 AM UTC+2, M=
atthew Fioravante wrote:<blockquote class=3D"gmail_quote" style=3D"margin: =
0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div d=
ir=3D"ltr"><br><br>On Monday, April 17, 2017 at 5:33:00 PM UTC-5, Marcin Ja=
czewski wrote:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-le=
ft:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><br>=
<br>On Monday, April 17, 2017 at 10:05:00 PM UTC+2, Nicol Bolas wrote:<bloc=
kquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-lef=
t:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monday, April 17, 20=
17 at 2:28:11 PM UTC-4, Matthew Fioravante wrote:<br><blockquote class=3D"g=
mail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;=
padding-left:1ex"><div dir=3D"ltr"><div>I&#39;ve used the sentinel in produ=
ction code as well.</div></div></blockquote><div><br>I never said that nobo=
dy uses such things in production code. I said that it&#39;s not something =
the standard library should support. It&#39;s just too fragile of a contain=
er for the standard library.<br><br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-lef=
t:1ex"><div dir=3D"ltr"><div>Again I don&#39;t need to store a size variabl=
e anywhere, saving valuable cache space. The most common use case for this =
is when you have a list of pointers to callbacks to be iterated through. Al=
l of the pointers except the last one are null.</div><div><br></div><div>Th=
is makes size() and push_back() slow, but in my use case it was a situation=
 where I set everything up on startup and then need to iterate the list ove=
r and over again in the hotpath. I don&#39;t give a damn about a bit slower=
 slow setup (not even measurable in real tests), when it buys me the fastes=
t possible iteration loop.</div><div><br></div><div>This optimizes the hell=
 out of iteration. After optimization its essentially this:</div><div><div =
style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,187);bo=
rder-style:solid;border-width:1px;word-wrap:break-word"><font face=3D"monos=
pace" color=3D"#000000">for(T**p =3D v.data(); *p !=3D nullptr; ++p) {<br>=
=C2=A0 doSomething(*p);<br>}</font></div><br></div></div></blockquote><div>=
<br>Which you can do right now by manually putting a NULL pointer at the en=
d of the list. This sounds like something best handled by some kind of iter=
ator/range adapter, not by changing the container itself. Indeed, by making=
 it an adapter rather than part of the class, it can now be used for lots o=
f tasks, the equivalent of doing a loop until you reach the value that `fin=
d_if` would return.<br><br></div><blockquote class=3D"gmail_quote" style=3D=
"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><d=
iv dir=3D"ltr"><div>The vector itself only stores a single pointer and is o=
nly 8 bytes in size.</div></div></blockquote><div><br>So you create this in=
credibly fragile container... just to save 16 bytes.</div></div></blockquot=
e><div><br>I do not see that will be more fragile than normal `begin`/`end`=
 combo. Trick would be use pair of iterators from range TS (`begin` and `en=
d` return different types).<br>Adding sentinel could be done automatically =
too.<br></div></div></blockquote><div><br></div><div>The fragility comes no=
t from iteration, but mutation. For example with sentintel_vector&lt;std::u=
nique_<wbr>ptr&lt;T&gt;&gt; with nullptr sentinel. There&#39;s basically no=
thing stopping me from inserting a nullptr somewhere in the middle and comp=
letely screwing up the size calculation, leaking the trailing pointers in t=
he process after the sentinel_vector is destroyed.</div></div></blockquote>=
<div><br>Right, probably only way to prevent it is ban not-const access to =
elements outside of vector api. `data` will always return const pointer to =
array of `T` but iterators will returns proxies that will check if you writ=
e proper values. But this will create `vector&lt;bool&gt;` v2 and made this=
 more complicated that is worth.<br></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/d069033a-e70b-4996-81da-235ea9560ba9%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/d069033a-e70b-4996-81da-235ea9560ba9=
%40isocpp.org</a>.<br />

------=_Part_5919_1728286998.1492514294996--

------=_Part_5918_347290259.1492514294996--

.

--94eb2c054376ab8814054d704b3b
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 20 March 2017 at 20:35, 'Thomas K=C3=B6ppe' via ISO C++ Standard - Futur=
e
Proposals <std-proposals@isocpp.org> wrote:

> You may also like to consider existing proposals and LEWG's response to
> them:
>
>    - P0210r0
>    <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0210r0.html>=
,
>    a light-weight, compact dynamic array, by yours truly. Reaction: meh, =
too
>    specific, not necessary.
>    - P0274r0
>    <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0274r0.pdf>,
>    clump, a vector-like container with embedded storage, by Nevin. LEWG l=
iked
>    this one quite a bit I believe, though we haven't seen it since.
>
>
I think the first one was better when it was std::dynarray.
I didn't follow the whole story and don't remember why the dynarray
proposal was killed just before C++14 was released.

For the second one (be it static_vector or small_vector), SG14 folks are
also interested in it, so if anyone wants to submit a new proposal, they
could use their backing.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CALnjya_Sb2hDXFs8MCRNmJXqz9cQc3XanK_5qw5L78cTkLm=
m2Q%40mail.gmail.com.

--94eb2c054376ab8814054d704b3b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On 2=
0 March 2017 at 20:35, &#39;Thomas K=C3=B6ppe&#39; via ISO C++ Standard - F=
uture Proposals <span dir=3D"ltr">&lt;<a href=3D"mailto:std-proposals@isocp=
p.org" target=3D"_blank">std-proposals@isocpp.org</a>&gt;</span> wrote:<br>=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr">You may also like to consid=
er existing proposals and LEWG&#39;s response to them:<div><ul><li><a href=
=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0210r0.html" t=
arget=3D"_blank">P0210r0</a>, a light-weight, compact dynamic array, by you=
rs truly. Reaction: meh, too specific, not necessary.</li><li><a href=3D"ht=
tp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0274r0.pdf" target=
=3D"_blank">P0274r0</a>, clump, a vector-like container with embedded stora=
ge, by Nevin. LEWG liked this one quite a bit I believe, though we haven&#3=
9;t seen it since.</li></ul></div></div></blockquote><div><br></div><div>I =
think the first one was better when it was std::dynarray.</div><div>I didn&=
#39;t follow the whole story and don&#39;t remember why the dynarray propos=
al was killed just before C++14 was released.</div><div><br>For the second =
one (be it static_vector or small_vector), SG14 folks are also interested i=
n it, so if anyone wants to submit a new proposal, they could use their bac=
king.</div></div></div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CALnjya_Sb2hDXFs8MCRNmJXqz9cQc3XanK_5=
qw5L78cTkLmm2Q%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CALnjya_Sb2hDXFs8=
MCRNmJXqz9cQc3XanK_5qw5L78cTkLmm2Q%40mail.gmail.com</a>.<br />

--94eb2c054376ab8814054d704b3b--

.

------=_Part_1548_497983009.1494860453342
Content-Type: multipart/alternative;
 boundary="----=_Part_1549_790112227.1494860453342"

------=_Part_1549_790112227.1494860453342
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

A blog post that just showed up on the ISO CPP rss feed today:

http://www.bfilipek.com/2017/04/packing-bools.html

And this paragraph about bitset is relevant here (emphasis mine):

The only drawback of using bitset is that it requires compile time N=20
> constant. *Also, bitset is implementation specific, so we=E2=80=99re not =
sure how=20
> the memory is laid out internally.* I would reject this version from the=
=20
> final production code, but might be good for comparisons.


An issue about bitset I raised a few years ago which failed to pass in the=
=20
committee. We really need more low level building blocks in C++ so that=20
expert users can construct the tools they need more easily.

--=20
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 e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/cc40f8bd-0470-4a44-9bef-1d3ad40c05b9%40isocpp.or=
g.

------=_Part_1549_790112227.1494860453342
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">A blog post that just showed up on the ISO CPP rss feed to=
day:<div><br></div><div>http://www.bfilipek.com/2017/04/packing-bools.html<=
/div><div><br></div><div>And this paragraph about bitset is relevant here (=
emphasis mine):</div><div><br></div><div><blockquote class=3D"gmail_quote" =
style=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 20=
4); padding-left: 1ex;"><span style=3D"font-family: &quot;Trebuchet MS&quot=
;, Trebuchet, sans-serif; text-align: justify;"><font size=3D"2">The only d=
rawback of using bitset is that it requires compile time N constant. <b>Als=
o, bitset is implementation specific, so we=E2=80=99re not sure how the mem=
ory is laid out internally.</b> I would reject this version from the final =
production code, but might be good for comparisons.</font></span></blockquo=
te><div><br></div></div><div>An issue about bitset I raised a few years ago=
 which failed to pass in the committee. We really need more low level build=
ing blocks in C++ so that expert users can construct the tools they need mo=
re easily.</div></div>

<p></p>

-- <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 <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/cc40f8bd-0470-4a44-9bef-1d3ad40c05b9%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/cc40f8bd-0470-4a44-9bef-1d3ad40c05b9=
%40isocpp.org</a>.<br />

------=_Part_1549_790112227.1494860453342--

------=_Part_1548_497983009.1494860453342--

.