I'm all for allowing 'dynamic' data structures at compile time. In D,
this feature has allowed me to make some very handy things.

However, this literal_vector proposal would lead to two completely
separate classes of containers: the compile-time ones (literal_vector,
and literal_{map,set,etc...} based on literal_vector) and the run-time
ones (vector, set, map, etc...). I don't think we should go there.

Also, would literal_vector be usable at both run-time and
compile-time? How would its run-time implementation be different than
std::vector? Wouldn't literal_vector be just a std::vector that's also
capable of constexpr stuff? In that case, it might be better to
propose literal_vector capabilities for std::vector itself, and then
make vector_/flat_{set,map,...} etc. based on std::vector for
constexpr-capable sets and maps.

-Maurice-

2014-03-23 2:18 GMT+01:00 Andrew Tomazos <andrewtomazos@gmail.com>:
> I've been thinking about the predynamic storage duration idea [1] I
> presented a while back and I think I may have come up with a better, simpler
> and cleaner way of dealing with the use cases:
>
> We propose the standardization of a class template std::literal_vector<T>:
>
>     template<typename T>
>     struct literal_vector;
>
> T must be a literal type, and for each T, std::literal_vector<T> is a
> literal type.
>
> std::literal_vector<T> has an interface similar to std::vector<T>.  Like
> std::vector<T>, it can store an arbitrarily-long random-access sequence of T
> that can change in size:
>
> For example:
>
>     constexpr std::literal_vector<int> concat(std::literal_vector<int> a,
> std::literal_vector<int> b)
>     {
>         std::literal_vector<int> c;
>
>         for (auto x : a)
>             c.push_back(x);
>
>         for (auto x : b)
>             c.push_back(x);
>
>         return c;
>     }
>
> Notice that concat is not a function template, it is just a regular
> constexpr function.
>
> The implementation of std::literal_vector<T> requires internal compiler
> support (it cannot be implemented in pure library code), but it does not
> require core language changes.
>
> User-defined literal types can then be composed, without further compiler
> support, by using one or more std::literal_vector<T> as subobjects.  Using
> literal_vector<T> in this fashion subsumes the use cases for predynamic
> storage duration.  new and delete expressions in constant expressions and
> constexpr functions are no longer needed.  You can just use
> std::literal_vector<T> if you need "predynamic" storage duration at
> compile-time.  The mechanism by which std::literal_vector<T> is implemented
> becomes an implementation detail not exposed to the user.  That is,
> std::literal_vector<T> becomes the fundamental primitive that is used to
> build more complex literal types.
>
> For example, using std::literal_vector<T> we can see how to create a
> non-template string_literal class of literal type:
>
>     struct string_literal
>     {
>         ...
>
>     private:
>         std::literal_vector<char> data;
>     };
>
> That was easy - but notice we can also create a binary tree of literal type:
>
>     template<class T>
>     struct node
>     {
>         T value;
>         size_t L, R; // index of subtrees in binary_tree::nodes
>     };
>
>     template<class T>
>     struct binary_tree
>     {
>         size_t root; // index of root node in nodes
>         std::literal_vector<node> nodes;
>     };
>
> You can imagine how to add a free list to reuse nodes and so on, but you get
> the idea - from here, it doesn't require much imagination to see how
> literal_vectors can be used as an "address space" to build arbitrarily
> complex self-referential data structures:
>
>     struct vertex
>     {
>         std::literal_vector<size_t> edges; // indexes into
> digraph::verticies
>     };
>
>     struct digraph
>     {
>         std::literal_vector<vertex> verticies;
>     };
>
>     template<class T>
>     struct bucket
>     {
>         hash_t hash_code;
>         std::literal_vector<T> contents;
>     };
>
>    template<class T>
>    struct dynamic_hash_table
>    {
>        std::literal_vector<bucket<T>> buckets;
>    };
>
>    template<class T>
>    struct matrix
>    {
>        ...
>
>    private:
>        std::literal_vector<T> cells; // stored in row-major order
>    };
>
> and so forth.
>
> Feedback appreciated.
>
> [1]:
> https://groups.google.com/a/isocpp.org/d/msg/std-proposals/-GbnSNmJ8bE/z3yvFxtzC6AJ
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.

--

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

.

--089e013d055cd1853c04f9b01da2
Content-Type: text/plain; charset=UTF-8

On Sat, May 17, 2014 at 12:29 PM, Maurice Bos <m-ou.se@m-ou.se> wrote:

> However, this literal_vector proposal would lead to two completely
> separate classes of containers: the compile-time ones (literal_vector,
> and literal_{map,set,etc...} based on literal_vector) and the run-time
> ones (vector, set, map, etc...). I don't think we should go there.
>

Just because two class types are distinct does not mean they are completely
separate.  If the two class types obey the same concepts they can be used
interchangably by client code according to those concepts without changing
the client code.  That is largely how the Containers library is designed
and specified.  The intention of the proposal is that std::vector and
std::literal_vector have as similar interface as possible.  In an ideal
world we would like std::vector to be a literal type, but this is very
difficult to implement.  Consequently the proposed approach is to create a
std::literal_vector of literal type, that is as close to std::vector as
possible.  One of the main problems is the allocator concept.  I think
std::literal_vector would effectively have a hard-coded
implementation-provided hidden allocator and wouldn't accept a different
one.  It's not clear how much easier that would make it to implement.

Also, would literal_vector be usable at both run-time and
> compile-time?


Yes, all literal types can be used at both compile-time and run-time.


> How would its run-time implementation be different than
> std::vector?


The implementation details are unspecified, only the interface.  If you are
asking how one possible implementation would work, then it could use a
scheme like how arrays of literal type are handled now - just with a
dynamically resizable backing store rather than a fixed sized one.


> Wouldn't literal_vector be just a std::vector that's also
> capable of constexpr stuff?


Yes, but the "constexpr stuff" requires breaking changes to the interface.


> In that case, it might be better to
> propose literal_vector capabilities for std::vector itself, and then
> make vector_/flat_{set,map,...} etc. based on std::vector for
> constexpr-capable sets and maps.
>

There are a number of problems with making std::vector a literal type
without making breaking changes to the interface.  The big one as I
mentioned is allocators I think.  There are probably other issues too.  To
be honest predynamic storage duration / std::literal_vector are both in my
too-hard basket at the moment.

--

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

--089e013d055cd1853c04f9b01da2
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 S=
at, May 17, 2014 at 12:29 PM, Maurice Bos <span dir=3D"ltr">&lt;<a href=3D"=
mailto:m-ou.se@m-ou.se" target=3D"_blank">m-ou.se@m-ou.se</a>&gt;</span> wr=
ote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border=
-left:1px #ccc solid;padding-left:1ex">
However, this literal_vector proposal would lead to two completely<br>
separate classes of containers: the compile-time ones (literal_vector,<br>
and literal_{map,set,etc...} based on literal_vector) and the run-time<br>
ones (vector, set, map, etc...). I don&#39;t think we should go there.<br><=
/blockquote><div><br></div><div>Just because two class types are distinct d=
oes not mean they are completely separate. =C2=A0If the two class types obe=
y the same concepts they can be used interchangably by client code accordin=
g to those concepts without changing the client code. =C2=A0That is largely=
 how the Containers library is designed and specified. =C2=A0The intention =
of the proposal is that std::vector and std::literal_vector have as similar=
 interface as possible. =C2=A0In an ideal world we would like std::vector t=
o be a literal type, but this is very difficult to implement. =C2=A0Consequ=
ently the proposed approach is to create a std::literal_vector of literal t=
ype, that is as close to std::vector as possible. =C2=A0One of the main pro=
blems is the allocator concept. =C2=A0I think std::literal_vector would eff=
ectively have a hard-coded implementation-provided hidden allocator and wou=
ldn&#39;t accept a different one. =C2=A0It&#39;s not clear how much easier =
that would make it to implement.</div>
<div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex">
Also, would literal_vector be usable at both run-time and<br>
compile-time?</blockquote><div><br></div><div>Yes, all literal types can be=
 used at both compile-time and run-time.</div><div>=C2=A0</div><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid=
;padding-left:1ex">
How would its run-time implementation be different than<br>
std::vector?</blockquote><div><br></div><div>The implementation details are=
 unspecified, only the interface. =C2=A0If you are asking how one possible =
implementation would work, then it could use a scheme like how arrays of li=
teral type are handled now - just with a dynamically resizable backing stor=
e rather than a fixed sized one.</div>
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex">Wouldn&#39;t literal_vector=
 be just a std::vector that&#39;s also<br>
capable of constexpr stuff?</blockquote><div><br></div><div>Yes, but the &q=
uot;constexpr stuff&quot; requires breaking changes to the interface.</div>=
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex">
In that case, it might be better to<br>
propose literal_vector capabilities for std::vector itself, and then<br>
make vector_/flat_{set,map,...} etc. based on std::vector for<br>
constexpr-capable sets and maps.<br></blockquote><div>=C2=A0</div><div>Ther=
e are a number of problems with making std::vector a literal type without m=
aking breaking changes to the interface. =C2=A0The big one as I mentioned i=
s allocators I think. =C2=A0There are probably other issues too. =C2=A0To b=
e honest predynamic storage duration / std::literal_vector are both in my t=
oo-hard basket at the moment.</div>
<div><br></div></div></div></div>

<p></p>

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

--089e013d055cd1853c04f9b01da2--

.