------=_Part_2430_311490329.1410371330689
Content-Type: text/plain; charset=UTF-8

Simple enough question: have there been proposals to add containers similar
to boost.flat_map (and flat_set, flat_multimap, and flat_multiset) to the
standard library, possibly under different names and (hopefully, IMO)
slightly different interfaces? I'm not finding any in the public archives,
but I know the subject has been mentioned a few times circumstantially.

Chandler Carruth mentioned a desire for a similar data structure in the
standard library during his CppCon talk Monday. Several game studios (at
least) have used various home-rolled versions of these containers for a
while now (mostly because Boost's has some unfortunate design decisions,
and then also for the same reasons that many games use their own
std::vector reimplementation to avoid inefficiencies in vendor-supplied
versions esp. in debug builds, and often with different names like
contiguous_map or vector_map or so on).

--

---
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/.

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

<div dir=3D"ltr">Simple enough question: have there been proposals to add c=
ontainers similar to boost.flat_map (and flat_set, flat_multimap, and flat_=
multiset) to the standard library, possibly under different names and (hope=
fully, IMO) slightly different interfaces? I'm not finding any in the publi=
c archives, but I know the subject has been mentioned a few times circumsta=
ntially.<div><br></div><div>Chandler Carruth mentioned a desire for a simil=
ar data structure in the standard library during his CppCon talk Monday. Se=
veral game studios (at least) have used various home-rolled versions of the=
se containers for a while now (mostly because Boost's has some unfortunate =
design decisions, and then also for the same reasons that many games use th=
eir own std::vector reimplementation to avoid inefficiencies in vendor-supp=
lied versions esp. in debug builds, and often with different names like con=
tiguous_map or vector_map or so on).</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 />

------=_Part_2430_311490329.1410371330689--

.

On 10 September 2014 20:48, Sean Middleditch <sean.middleditch@gmail.com> wrote:
> Simple enough question: have there been proposals to add containers similar
> to boost.flat_map (and flat_set, flat_multimap, and flat_multiset) to the
> standard library, possibly under different names and (hopefully, IMO)
> slightly different interfaces? I'm not finding any in the public archives,


I don't recall seeing such a proposal. It gets mentioned more and more
often nowadays.

--

---
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/.

.

El 10/09/2014 19:48, Sean Middleditch escribi=C3=B3:
> (mostly because Boost's has some unfortunate design decisions,
> and then also for the same reasons that many games use their own
> std::vector reimplementation to avoid inefficiencies in vendor-supplied
> versions esp. in debug builds, and often with different names like
> contiguous_map or vector_map or so on).

It would be good to know which are those unfortunate design decisions so=20
that Boost implementation can be improved, those improvements could be=20
widely tested by the community and offer a strong existing practice for=20
a proposal.

Best,

Ion

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

Hi Ion,

It's painful to not have index-based access when I know it's most
appropriate. Yes, I can emulate index-based access with the
random-access iterator arithmetic and the begin() iterator, but that
seems... messy.

Secondly, it appears to me that the specification bars implementations
that use separate arrays for the key vs the value (important when the
value is bigger or has wildly differing alignment requirements to the
key, as otherwise you'd get far too much bloat in the std::pair and
poor cache behavior when searching/sorting/finding). I'm unsure on
this one, though, as it's something I'm inferring from the
informal-ish spec rather than something that's spelled out explicitly,
so maybe such an implementation optimization is already possible.

My third point appears to be addressed in recent Boost versions (bulk
insert is now there).

Fourth, it's missing initializer_list support. at least according to
the latest docs.

In hindsight these are less "unfortunate design decisions" and more
"missing features" other than the second one (assuming I inferred
correctly). I over-stated things as I sometimes tend to do; sorry. :)

Add a sanctioned index-based accessor, initializer_list construction,
and double check that the optimization I mentioned is at least legal
and I think it's golden.

On Wed, Sep 10, 2014 at 1:55 PM, Ion Gazta=C3=B1aga <igaztanaga@gmail.com> =
wrote:
> El 10/09/2014 19:48, Sean Middleditch escribi=C3=B3:
>>
>> (mostly because Boost's has some unfortunate design decisions,
>> and then also for the same reasons that many games use their own
>> std::vector reimplementation to avoid inefficiencies in vendor-supplied
>> versions esp. in debug builds, and often with different names like
>> contiguous_map or vector_map or so on).
>
>
> It would be good to know which are those unfortunate design decisions so
> that Boost implementation can be improved, those improvements could be
> widely tested by the community and offer a strong existing practice for a
> proposal.
>
> Best,
>
> Ion
>
>
> --
>
> --- You received this message because you are subscribed to a topic in th=
e
> Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/rFzIHMSN77k/=
unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.



--=20
Sean Middleditch
http://seanmiddleditch.com

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

El 11/09/2014 8:53, Sean Middleditch escribi=C3=B3:
> Hi Ion,
>
> It's painful to not have index-based access when I know it's most
> appropriate. Yes, I can emulate index-based access with the
> random-access iterator arithmetic and the begin() iterator, but that
> seems... messy.

flat_xxx follows std::set/map interface as much as possible and it's not=20
the only one. Folly's sorted_vector_set/map and other implementations=20
also look for drop-in replacements of associative containers. When do=20
you need random-access access into an associative container?


> Secondly, it appears to me that the specification bars implementations
> that use separate arrays for the key vs the value (important when the
> value is bigger or has wildly differing alignment requirements to the
> key, as otherwise you'd get far too much bloat in the std::pair and
> poor cache behavior when searching/sorting/finding). I'm unsure on
> this one, though, as it's something I'm inferring from the
> informal-ish spec rather than something that's spelled out explicitly,
> so maybe such an implementation optimization is already possible.

I don't think it's possible with the standard interface, as in=20
map/multimap value_type is defined as the type the container holds. a=20
separate storage for "key" and "value" needs to return a reference to=20
what? I think it's a good idea to separate key_type and mapped_type in=20
some uses cases, as it could speed up several operations but some parts=20
of the interface (e.g. the insertion functions) will need to be rewritten.

For iterators, one option is to have two-level iterators, one for the=20
type and another type for the mapped_type.

> Fourth, it's missing initializer_list support. at least according to
> the latest docs.

Already added in develop branch:

http://www.boost.org/doc/libs/develop/doc/html/boost/container/flat_map.htm=
l

> Add a sanctioned index-based accessor, initializer_list construction,
> and double check that the optimization I mentioned is at least legal
> and I think it's golden.

Index-based accesor is not hard to add if there is demand for that.=20
Separate keys and values, that requires a non-stl like interface and I=20
suspect a very different implemntation. Maybe (I'm not sure) the answer=20
for separate keys and values is to have a different container family.

Ion

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

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

On Thursday, September 11, 2014 5:31:04 AM UTC-7, Ion Gazta=C3=B1aga wrote:
>
> El 11/09/2014 8:53, Sean Middleditch escribi=C3=B3:=20
> > Hi Ion,=20
> >=20
> > It's painful to not have index-based access when I know it's most=20
> > appropriate. Yes, I can emulate index-based access with the=20
> > random-access iterator arithmetic and the begin() iterator, but that=20
> > seems... messy.=20
>
> flat_xxx follows std::set/map interface as much as possible and it's not=
=20
> the only one. Folly's sorted_vector_set/map and other implementations=20
> also look for drop-in replacements of associative containers. When do=20
> you need random-access access into an associative container?=20
>
>
One case I use often is to convert a flat_set's iterator to an index to use=
=20
for access to companion vectors. Then some operations on those vectors need=
=20
to get back the data in the flat_set e.g.

  flat_set<key> keys;
  vector<foo> foos;
  vector<bar> bars;

  for (auto i =3D 0U; i !=3D foos.size(); ++i)
    do_something(*(keys.begin() + i), foos[i]);

flat_* gets a lot of use in data-oriented systems and in many cases these=
=20
are best built with multiple distinct arrays rather than a single value=20
struct/tuple in a flat_map.

For inserts, of course, we calculate the index of the inserted item in the=
=20
flat_set, use that to calculate an iterator to the vectors, and then=20
insert() into those vectors.

>
> > Secondly, it appears to me that the specification bars implementations=
=20
> > that use separate arrays for the key vs the value (important when the=
=20
> > value is bigger or has wildly differing alignment requirements to the=
=20
> > key, as otherwise you'd get far too much bloat in the std::pair and=20
> > poor cache behavior when searching/sorting/finding). I'm unsure on=20
> > this one, though, as it's something I'm inferring from the=20
> > informal-ish spec rather than something that's spelled out explicitly,=
=20
> > so maybe such an implementation optimization is already possible.=20
>
> I don't think it's possible with the standard interface, as in=20
> map/multimap value_type is defined as the type the container holds. a=20
> separate storage for "key" and "value" needs to return a reference to=20
> what? I think it's a good idea to separate key_type and mapped_type in=20
> some uses cases, as it could speed up several operations but some parts=
=20
> of the interface (e.g. the insertion functions) will need to be rewritten=
..=20
>

insert can still take a pair of values but access can return a pair of=20
references. This is precisely what our custom flat_* types do, albeit we=20
don't try to adhere 100% to the STL API in places it ties our hands behind=
=20
our backs.

For iterators, one option is to have two-level iterators, one for the=20
> type and another type for the mapped_type.=20
>
> > Fourth, it's missing initializer_list support. at least according to=20
> > the latest docs.=20
>
> Already added in develop branch:=20
>
>
> http://www.boost.org/doc/libs/develop/doc/html/boost/container/flat_map.h=
tml=20
>
>
Yay!
=20

> > Add a sanctioned index-based accessor, initializer_list construction,=
=20
> > and double check that the optimization I mentioned is at least legal=20
> > and I think it's golden.=20
>
> Index-based accesor is not hard to add if there is demand for that.=20
> Separate keys and values, that requires a non-stl like interface and I=20
> suspect a very different implemntation. Maybe (I'm not sure) the answer=
=20
> for separate keys and values is to have a different container family.=20
>

Hmm, maybe. That's an avenue for me to think about.=20

>
> Ion=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

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

<div dir=3D"ltr">On Thursday, September 11, 2014 5:31:04 AM UTC-7, Ion Gazt=
a=C3=B1aga wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">El 11/09/2014=
 8:53, Sean Middleditch escribi=C3=B3:
<br>&gt; Hi Ion,
<br>&gt;
<br>&gt; It's painful to not have index-based access when I know it's most
<br>&gt; appropriate. Yes, I can emulate index-based access with the
<br>&gt; random-access iterator arithmetic and the begin() iterator, but th=
at
<br>&gt; seems... messy.
<br>
<br>flat_xxx follows std::set/map interface as much as possible and it's no=
t=20
<br>the only one. Folly's sorted_vector_set/map and other implementations=
=20
<br>also look for drop-in replacements of associative containers. When do=
=20
<br>you need random-access access into an associative container?
<br>
<br></blockquote><div><br></div><div>One case I use often is to convert a f=
lat_set's iterator to an index to use for access to companion vectors. Then=
 some operations on those vectors need to get back the data in the flat_set=
 e.g.</div><div><br></div><div>&nbsp; flat_set&lt;key&gt; keys;</div><div>&=
nbsp; vector&lt;foo&gt; foos;</div><div>&nbsp; vector&lt;bar&gt; bars;</div=
><div><br></div><div>&nbsp; for (auto i =3D 0U; i !=3D foos.size(); ++i)</d=
iv><div>&nbsp; &nbsp; do_something(*(keys.begin() + i), foos[i]);</div><div=
><br></div><div>flat_* gets a lot of use in data-oriented systems and in ma=
ny cases these are best built with multiple distinct arrays rather than a s=
ingle value struct/tuple in a flat_map.</div><div><br></div><div>For insert=
s, of course, we calculate the index of the inserted item in the flat_set, =
use that to calculate an iterator to the vectors, and then insert() into th=
ose vectors.</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;marg=
in-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>&gt; Secondly, it appears to me that the specification bars implementat=
ions
<br>&gt; that use separate arrays for the key vs the value (important when =
the
<br>&gt; value is bigger or has wildly differing alignment requirements to =
the
<br>&gt; key, as otherwise you'd get far too much bloat in the std::pair an=
d
<br>&gt; poor cache behavior when searching/sorting/finding). I'm unsure on
<br>&gt; this one, though, as it's something I'm inferring from the
<br>&gt; informal-ish spec rather than something that's spelled out explici=
tly,
<br>&gt; so maybe such an implementation optimization is already possible.
<br>
<br>I don't think it's possible with the standard interface, as in=20
<br>map/multimap value_type is defined as the type the container holds. a=
=20
<br>separate storage for "key" and "value" needs to return a reference to=
=20
<br>what? I think it's a good idea to separate key_type and mapped_type in=
=20
<br>some uses cases, as it could speed up several operations but some parts=
=20
<br>of the interface (e.g. the insertion functions) will need to be rewritt=
en.
<br></blockquote><div><br></div><div>insert can still take a pair of values=
 but access can return a pair of references. This is precisely what our cus=
tom flat_* types do, albeit we don't try to adhere 100% to the STL API in p=
laces it ties our hands behind our backs.</div><div><br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px=
 #ccc solid;padding-left: 1ex;">For iterators, one option is to have two-le=
vel iterators, one for the=20
<br>type and another type for the mapped_type.
<br>
<br>&gt; Fourth, it's missing initializer_list support. at least according =
to
<br>&gt; the latest docs.
<br>
<br>Already added in develop branch:
<br>
<br><a href=3D"http://www.boost.org/doc/libs/develop/doc/html/boost/contain=
er/flat_map.html" target=3D"_blank" onmousedown=3D"this.href=3D'http://www.=
google.com/url?q\75http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2Fdevelop%2Fdoc%=
2Fhtml%2Fboost%2Fcontainer%2Fflat_map.html\46sa\75D\46sntz\0751\46usg\75AFQ=
jCNFGPl0wII2gYpjzu3FoSwB3lzMCWw';return true;" onclick=3D"this.href=3D'http=
://www.google.com/url?q\75http%3A%2F%2Fwww.boost.org%2Fdoc%2Flibs%2Fdevelop=
%2Fdoc%2Fhtml%2Fboost%2Fcontainer%2Fflat_map.html\46sa\75D\46sntz\0751\46us=
g\75AFQjCNFGPl0wII2gYpjzu3FoSwB3lzMCWw';return true;">http://www.boost.org/=
doc/libs/<wbr>develop/doc/html/boost/<wbr>container/flat_map.html</a>
<br>
<br></blockquote><div><br></div><div>Yay!</div><div>&nbsp;</div><blockquote=
 class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1=
px #ccc solid;padding-left: 1ex;">&gt; Add a sanctioned index-based accesso=
r, initializer_list construction,
<br>&gt; and double check that the optimization I mentioned is at least leg=
al
<br>&gt; and I think it's golden.
<br>
<br>Index-based accesor is not hard to add if there is demand for that.=20
<br>Separate keys and values, that requires a non-stl like interface and I=
=20
<br>suspect a very different implemntation. Maybe (I'm not sure) the answer=
=20
<br>for separate keys and values is to have a different container family.
<br></blockquote><div><br></div><div>Hmm, maybe. That's an avenue for me to=
 think about.&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margin:=
 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>Ion
<br></blockquote></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 />

------=_Part_2822_1327204471.1410451326289--

.

El 11/09/2014 18:02, Sean Middleditch escribi=C3=B3:
> One case I use often is to convert a flat_set's iterator to an index to
> use for access to companion vectors. Then some operations on those
> vectors need to get back the data in the flat_set e.g.
>
>    flat_set<key> keys;
>    vector<foo> foos;
>    vector<bar> bars;
>
>    for (auto i =3D 0U; i !=3D foos.size(); ++i)
>      do_something(*(keys.begin() + i), foos[i]);
>
> flat_* gets a lot of use in data-oriented systems and in many cases
> these are best built with multiple distinct arrays rather than a single
> value struct/tuple in a flat_map.
>
> For inserts, of course, we calculate the index of the inserted item in
> the flat_set, use that to calculate an iterator to the vectors, and then
> insert() into those vectors.

Something like this would work?

class flat_xxx
{
   //Requires: 0 <=3D index <=3D size()
   //Returns: an iterator to the nth element
   //Note: end iterator is returned for index =3D=3D this->size()
   iterator nth(size_type index);
   const_iterator nth(size_type index) const;
};

for (auto i =3D 0U; i !=3D foos.size(); ++i)
   do_something(*keys.nth(i), foos[i]);

That could be added also to boost::container::vector (return an iterator=20
to the nth element). The inverse operation might be

class flat_xxx
{
   //Returns the index of the element pointed by pos
   size_type index_of(const_iterator pos) const;
};

Would that be generic enough and useful? A similar idea was proposed in=20
N3450 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3450.pdf)

Best,

Ion

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

Yeah, I think that would be a great start. Looking at the sample code
now looks ugly not because of the iterator math but the for-loop
itself, which could become:

  for (auto i : size_range(foos))
    do_something(*keys.nth(i), foos[i]);

Although in some distant future where we have the extra machinery in
the standard and implementations don't impose such massive overhead
(esp. in debug builds) for most simple STL operations, we could even
remove the whole need for index and use an equivalent STL algorithm
(std::for_each(std::zip_range(keys, foos, bars), do_something) ?).
Even in the above example, the iterator overhead may keep it
beneficial to use keys.nth_item or something rather than going through
an iterator (really, a single iterator in a tight loop can have really
massive perf consequences when optimizations are low/off and even with
iterator debugging turned off in the vendor's library), but that might
be getting into domain-specific worries.

Would you think that a paper that just presents the flat_* containers
with a header synopsis lifted from Boost and some justification for
the need would be a good first step?

On Fri, Sep 12, 2014 at 2:49 AM, Ion Gazta=C3=B1aga <igaztanaga@gmail.com> =
wrote:
> El 11/09/2014 18:02, Sean Middleditch escribi=C3=B3:
>>
>> One case I use often is to convert a flat_set's iterator to an index to
>> use for access to companion vectors. Then some operations on those
>> vectors need to get back the data in the flat_set e.g.
>>
>>    flat_set<key> keys;
>>    vector<foo> foos;
>>    vector<bar> bars;
>>
>>    for (auto i =3D 0U; i !=3D foos.size(); ++i)
>>      do_something(*(keys.begin() + i), foos[i]);
>>
>> flat_* gets a lot of use in data-oriented systems and in many cases
>> these are best built with multiple distinct arrays rather than a single
>> value struct/tuple in a flat_map.
>>
>> For inserts, of course, we calculate the index of the inserted item in
>> the flat_set, use that to calculate an iterator to the vectors, and then
>> insert() into those vectors.
>
>
> Something like this would work?
>
> class flat_xxx
> {
>   //Requires: 0 <=3D index <=3D size()
>   //Returns: an iterator to the nth element
>   //Note: end iterator is returned for index =3D=3D this->size()
>   iterator nth(size_type index);
>   const_iterator nth(size_type index) const;
> };
>
> for (auto i =3D 0U; i !=3D foos.size(); ++i)
>   do_something(*keys.nth(i), foos[i]);
>
> That could be added also to boost::container::vector (return an iterator =
to
> the nth element). The inverse operation might be
>
> class flat_xxx
> {
>   //Returns the index of the element pointed by pos
>   size_type index_of(const_iterator pos) const;
> };
>
> Would that be generic enough and useful? A similar idea was proposed in
> N3450 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3450.pdf)
>
>
> Best,
>
> Ion
>
> --
>
> --- You received this message because you are subscribed to a topic in th=
e
> Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/rFzIHMSN77k/=
unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.



--=20
Sean Middleditch
http://seanmiddleditch.com

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

El 12/09/2014 16:40, Sean Middleditch escribi=C3=B3:
> Yeah, I think that would be a great start. Looking at the sample code
> now looks ugly not because of the iterator math but the for-loop
> itself, which could become:
>
>    for (auto i : size_range(foos))
>      do_something(*keys.nth(i), foos[i]);
>
> Although in some distant future where we have the extra machinery in
> the standard and implementations don't impose such massive overhead
> (esp. in debug builds) for most simple STL operations, we could even
> remove the whole need for index and use an equivalent STL algorithm

I hope soon all compilers will offer "-Og" optimization level where at=20
least one-liners are always inlined (e.g. dereferencing, iterator=20
increment, subscript...). I agree that debug builds are really slow in=20
C++, but many times I noticed we make many tiny functions that ease code=20
review and maintenance because we know inlining is there.

> Would you think that a paper that just presents the flat_* containers
> with a header synopsis lifted from Boost and some justification for
> the need would be a good first step?

I really don't know ;-) I've presented two papers in my life without any=20
luck so maybe you should ask advice to committee members reading this=20
list ;-)

Best,

Ion

--=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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

------=_Part_31_839584632.1410576876382
Content-Type: text/plain; charset=UTF-8

There was a group of developers that got together with Michael Wong, with
members of the game industry, finance industry, medical industry, and
defense industry (basically soft/hard real time system developers).  Were
you a part of that meeting?  If so, perhaps we should gather
emails/contacts of everyone that was there and do an offline email chain to
focus on what aspects to tackle in what order.  If not, want to tackle it
together?

After speaking with Stephan Lavavej about why unordered_map is as bad as it
is, and what parts of the standardize force it to basically be a std::list
for the buckets, I think it'd be a nice, low-hanging fruit to tackle.
 Especially as a Key/Value hashmap is one of the more important data
structures available to us, and every company I spoke to has rolled their
own to bypass the STL's implementation.

On Wednesday, September 10, 2014 10:48:51 AM UTC-7, Sean Middleditch wrote:
>
> Simple enough question: have there been proposals to add containers
> similar to boost.flat_map (and flat_set, flat_multimap, and flat_multiset)
> to the standard library, possibly under different names and (hopefully,
> IMO) slightly different interfaces? I'm not finding any in the public
> archives, but I know the subject has been mentioned a few times
> circumstantially.
>
> Chandler Carruth mentioned a desire for a similar data structure in the
> standard library during his CppCon talk Monday. Several game studios (at
> least) have used various home-rolled versions of these containers for a
> while now (mostly because Boost's has some unfortunate design decisions,
> and then also for the same reasons that many games use their own
> std::vector reimplementation to avoid inefficiencies in vendor-supplied
> versions esp. in debug builds, and often with different names like
> contiguous_map or vector_map or so on).
>

--

---
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/.

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

<div dir=3D"ltr">There was a group of developers that got together with&nbs=
p;<font color=3D"#545454" face=3D"arial, sans-serif" size=3D"2"><span style=
=3D"line-height: 18.2000007629395px;">Michael Wong, with members of the gam=
e industry, finance industry, medical industry, and defense industry (basic=
ally soft/hard real time system developers). &nbsp;Were you a part of that =
meeting? &nbsp;If so, perhaps we should gather emails/contacts of everyone =
that was there and do an offline email chain to focus on what aspects to ta=
ckle in what order. &nbsp;If not, want to tackle it together? &nbsp;</span>=
</font><div><font color=3D"#545454" face=3D"arial, sans-serif" size=3D"2"><=
span style=3D"line-height: 18.2000007629395px;"><br></span></font></div><di=
v><font color=3D"#545454" face=3D"arial, sans-serif" size=3D"2"><span style=
=3D"line-height: 18.2000007629395px;">After speaking with&nbsp;Stephan Lava=
vej about why unordered_map is as bad as it is, and what parts of the stand=
ardize force it to basically be a std::list for the buckets, I think it'd b=
e a nice, low-hanging fruit to tackle. &nbsp;Especially as a Key/Value hash=
map is one of the more important data structures&nbsp;available&nbsp;to us,=
 and every company I spoke to has rolled their own to bypass the STL's impl=
ementation.</span></font><br><br>On Wednesday, September 10, 2014 10:48:51 =
AM UTC-7, Sean Middleditch 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">Simple enough question: have there been proposals to ad=
d containers similar to boost.flat_map (and flat_set, flat_multimap, and fl=
at_multiset) to the standard library, possibly under different names and (h=
opefully, IMO) slightly different interfaces? I'm not finding any in the pu=
blic archives, but I know the subject has been mentioned a few times circum=
stantially.<div><br></div><div>Chandler Carruth mentioned a desire for a si=
milar data structure in the standard library during his CppCon talk Monday.=
 Several game studios (at least) have used various home-rolled versions of =
these containers for a while now (mostly because Boost's has some unfortuna=
te design decisions, and then also for the same reasons that many games use=
 their own std::vector reimplementation to avoid inefficiencies in vendor-s=
upplied versions esp. in debug builds, and often with different names like =
contiguous_map or vector_map or so on).</div></div></blockquote></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 />

------=_Part_31_839584632.1410576876382--

.

Hi Caladin,

I unfortunately missed that meeting (I didn't remember it was
happening until after I had taken some overseas colleagues from
Wargaming out to lunch, and I'm still kicking myself in the butt for
missing it; it would've been one of the more useful things for me to
have done at CppCon I think), though I've spoken with Michael a bit
the day after.

I'd totally be down for a real-time(-ish) in C++ discussion
group/list. Heck, maybe even make it an SG if the committee's
interested (I'll email Michael about that actually).

Regarding unordered_map... yeah, we've known about the issues since
back in the Boost days. I generally prefer an open-addressed hash
table with keys in a separate arrays to improve chaining efficiency
(once again, due to cache behavior), but only when a hash_table makes
sense; there's still cases where a flat_map-like structure makes more
sense (and yet other cases where a "linear_map" makes more sense).
There's yet other specialized data structures that allow constant time
(not amortized-constant-time!) lookup with certain kinds of keys that
are rather popular at least in games (I've called them "slot maps" and
there's also a great article by the Bitsquid guys that referred to
them as "packed arrays"), plus cases where it's beneficial to generate
perfect hash functions for hash tables. We should probably pull this
off to another thread, though.

On Fri, Sep 12, 2014 at 7:54 PM,  <caladain@gmail.com> wrote:
> There was a group of developers that got together with Michael Wong, with
> members of the game industry, finance industry, medical industry, and
> defense industry (basically soft/hard real time system developers).  Were
> you a part of that meeting?  If so, perhaps we should gather emails/contacts
> of everyone that was there and do an offline email chain to focus on what
> aspects to tackle in what order.  If not, want to tackle it together?
>
> After speaking with Stephan Lavavej about why unordered_map is as bad as it
> is, and what parts of the standardize force it to basically be a std::list
> for the buckets, I think it'd be a nice, low-hanging fruit to tackle.
> Especially as a Key/Value hashmap is one of the more important data
> structures available to us, and every company I spoke to has rolled their
> own to bypass the STL's implementation.
>
>
> On Wednesday, September 10, 2014 10:48:51 AM UTC-7, Sean Middleditch wrote:
>>
>> Simple enough question: have there been proposals to add containers
>> similar to boost.flat_map (and flat_set, flat_multimap, and flat_multiset)
>> to the standard library, possibly under different names and (hopefully, IMO)
>> slightly different interfaces? I'm not finding any in the public archives,
>> but I know the subject has been mentioned a few times circumstantially.
>>
>> Chandler Carruth mentioned a desire for a similar data structure in the
>> standard library during his CppCon talk Monday. Several game studios (at
>> least) have used various home-rolled versions of these containers for a
>> while now (mostly because Boost's has some unfortunate design decisions, and
>> then also for the same reasons that many games use their own std::vector
>> reimplementation to avoid inefficiencies in vendor-supplied versions esp. in
>> debug builds, and often with different names like contiguous_map or
>> vector_map or so on).
>
> --
>
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/rFzIHMSN77k/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.



--
Sean Middleditch
http://seanmiddleditch.com

--

---
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/.

.