------=_Part_1718_1459121929.1490147570635
Content-Type: multipart/alternative;
 boundary="----=_Part_1719_166655105.1490147570636"

------=_Part_1719_166655105.1490147570636
Content-Type: text/plain; charset=UTF-8

Proposal N3657
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm> added
the following heterogeneous lookup functions in the presence of a
`Compare::is_transparent` tag:

find
count
lower_bound
upper_bound
equal_range

However, heterogeneous keys are not supported for modifiers. My use case is
wanting to use a `string_view` as a key into a `map<string, X>`. For
efficiency, I only want a `string` to be constructed if the entry doesn't
already exist.

auto count_k_mers(std::string_view s, std::size_t length) {
  std::map<std::string, std::size_t, std::less<>> counts;
  for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
    ++counts[s.substr(i, length)]; // error: no such function
`operator[](string_view)`
  }
  return counts;
}

No overload of `operator[]` takes a heterogeneous key, hence the
compilation error. The same is true for `try_emplace`:

    ++counts.try_emplace(k_mer).first->second; // error: no such function
`try_emplace(string_view)`

I can't use `emplace` naively because that will create a `string` on every
call. Instead, I am forced to do something like this:

auto count_k_mers(std::string_view s, std::size_t length) {
  std::map<std::string, std::size_t, std::less<>> counts;
  for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
    auto k_mer = s.substr(i, length);
    auto it = counts.find(k_mer);
    if (it == counts.end()) {
      it = counts.emplace(k_mer, std::size_t()).first;
    }
    ++it->second;
  }
  return counts;
}

This could obviously be optimized by using `lower_bound` and `emplace_hint`,
but what are the chances the average user will do this? So why not provide
a heterogeneous `operator[]` that gives optimal performance by default?

template <typename K>
T& operator[](K const& k) {
  auto it = lower_bound(k);
  if (it == end() || Compare()(k, it->first)) {
    it = emplace_hint(it, k, T());
  }
  return it->second;
}

Pretty much any function that takes a key could have a heterogeneous
overload (`at`, `try_emplace`, `extract`, `erase`). Is there some reason
these functions don't exist yet?

--
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/b7fedc9e-d39a-4bb9-b6fe-0b02e3a8fe88%40isocpp.org.

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

<div dir=3D"ltr">Proposal <a href=3D"http://www.open-std.org/jtc1/sc22/wg21=
/docs/papers/2013/n3657.htm">N3657</a> added the following heterogeneous lo=
okup functions in the presence of a <span style=3D"font-family: courier new=
,monospace;">`Compare::is_transparent`</span> tag:<br><br><div style=3D"bac=
kground-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187); border=
-style: solid; border-width: 1px; overflow-wrap: break-word;" class=3D"pret=
typrint"><code class=3D"prettyprint"><div class=3D"subprettyprint"><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify">find<br>count<br>lower_bo=
und<br>upper_bound<br>equal_range</span></div></code></div><br>However, het=
erogeneous keys are not supported for modifiers. My use case is wanting to =
use a <span style=3D"font-family: courier new,monospace;">`string_view`</sp=
an> as a key into a <span style=3D"font-family: courier new,monospace;">`ma=
p&lt;string, X&gt;`</span>. For efficiency, I only want a <span style=3D"fo=
nt-family: courier new,monospace;">`string`</span> to be constructed if the=
 entry doesn&#39;t already exist.<br><br><div style=3D"background-color: rg=
b(250, 250, 250); border-color: rgb(187, 187, 187); border-style: solid; bo=
rder-width: 1px; overflow-wrap: break-word;" class=3D"prettyprint"><code cl=
ass=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #00=
8;" class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"> count_k_mers</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">string_view s</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
 std</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">size_t length<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>=C2=A0 std</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">map</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">&lt;</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">::</span><span style=3D"color: #008;" class=3D"styled-by-pret=
tify">string</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> std</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify">size_t</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">less</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">&lt;&gt;&gt;</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> counts</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"><br>=C2=A0 </span><span style=3D"color: #008;" class=3D"styled-=
by-prettify">for</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify">std</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify">size_t i </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #066;=
" class=3D"styled-by-prettify">0</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> i </span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">&lt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> s</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify">length</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">()</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">-</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"> length </span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">+</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> </span><span style=3D"color: #066;" class=3D"styled-by-=
prettify">1</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: #660;" class=3D"styled-by-prettify">++</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify">i</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">++</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">counts</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">[</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y">s</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify">substr</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">i</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> length</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">)];</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> </span><span style=3D"color: #800;" class=3D"styled-by-=
prettify">// error: no such function `operator[](string_view)`</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 </span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">return</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> counts</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">}</span></div></code></div><br>No overload of <spa=
n style=3D"font-family: courier new,monospace;">`operator[]`</span> takes a=
 heterogeneous key, hence the compilation error. The same is true for <span=
 style=3D"font-family: courier new,monospace;">`try_emplace`</span>:<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-wo=
rd;" class=3D"prettyprint"><code class=3D"prettyprint"><div class=3D"subpre=
ttyprint"><span style=3D"color: #000;" class=3D"styled-by-prettify">=C2=A0 =
=C2=A0 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">++<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify">counts</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify">try_emplace</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify">k_mer</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">).</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify">first</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">-&gt;</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">second</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: #800;" class=3D"styled-by-prettify">//=
 error: no such function `try_emplace(string_view)`</span></div></code></di=
v><br>I can&#39;t use <span style=3D"font-family: courier new,monospace;">`=
emplace`</span> naively because that will create a <span style=3D"font-fami=
ly: courier new,monospace;">`string`</span> on every call. Instead, I am fo=
rced to do something like this:<br><br><div style=3D"background-color: rgb(=
250, 250, 250); border-color: rgb(187, 187, 187); border-style: solid; bord=
er-width: 1px; overflow-wrap: break-word;" class=3D"prettyprint"><code clas=
s=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #008;=
" class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> count_k_mers</span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy">string_view s</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> s=
td</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">size_t length</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"><br>=C2=A0 std</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify">map</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&lt;</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">::</span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">string</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> std</span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify">size_t</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">less</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">&lt;&gt;&gt;</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> counts</span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br>=C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-p=
rettify">for</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">std</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify">size_t i </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 style=3D"color: #066;" cl=
ass=3D"styled-by-prettify">0</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"> i </span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">&lt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> s</=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify">length</span><span st=
yle=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: #66=
0;" class=3D"styled-by-prettify">-</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> length </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><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">++</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">i</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: #660;" class=3D"=
styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"s=
tyled-by-prettify">auto</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> k_mer </span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> s</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">substr</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify">i</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"> length</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" cl=
ass=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> it </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> counts</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">find=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify">k_mer</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><span s=
tyle=3D"color: #008;" class=3D"styled-by-prettify">if</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify">it </span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">=3D=3D</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"> counts</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">.</span><span style=3D"color: #008;" class=3D"styled-by-prettify=
">end</span><span style=3D"color: #660;" class=3D"styled-by-prettify">())</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 =C2=A0 it =
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> counts</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">emplace</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify">k_mer</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> std</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify">size_t</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">()).</span><span style=3D"color: #000;" class=3D"styled-by-prettify">fir=
st</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0=
 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 =
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">++</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify">it</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">-&gt;</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify">second</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"><br>=C2=A0 </span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">}</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>=C2=A0 </span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">return</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> counts</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: #660;" class=3D"styled-by-prettif=
y">}</span></div></code></div><br>This could obviously be optimized by usin=
g <span style=3D"font-family: courier new,monospace;">`lower_bound`</span> =
and <span style=3D"font-family: courier new,monospace;">`emplace_hint`</spa=
n>, but what are the chances the average user will do this? So why not prov=
ide a heterogeneous <span style=3D"font-family: courier new,monospace;">`op=
erator[]`</span> that gives optimal performance by default?<br><br><div sty=
le=3D"background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187=
); border-style: solid; border-width: 1px; overflow-wrap: break-word;" clas=
s=3D"prettyprint"><code class=3D"prettyprint"><div class=3D"subprettyprint"=
><span style=3D"color: #008;" class=3D"styled-by-prettify">template</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">typename</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> K</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"><br>T</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">&amp;</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pre=
ttify">operator</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">[](</span><span style=3D"color: #000;" class=3D"styled-by-prettify">K =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">const</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">&amp;</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> k</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: #660;" =
class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>=C2=A0 </span><span style=3D"color: #008;" class=3D=
"styled-by-prettify">auto</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> it </span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> lower_bound</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">k</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">);</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 </span><spa=
n style=3D"color: #008;" class=3D"styled-by-prettify">if</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">it </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">=3D=3D</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by=
-prettify">end</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">()</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">||</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #606;" class=3D"styled-by-prettify">Compare</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">()(</span><span style=3D"color:=
 #000;" class=3D"styled-by-prettify">k</span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> it</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">-&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify">first</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">))</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 it </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> emplace_hint</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">it</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> k</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> T</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">());</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
><br>=C2=A0 </span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=
=A0 </span><span style=3D"color: #008;" class=3D"styled-by-prettify">return=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> it</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">-&gt;</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify">second</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">}</span></div></code></div><br>Pretty muc=
h any function that takes a key could have a heterogeneous overload (<span =
style=3D"font-family: courier new,monospace;">`at`</span>, <span style=3D"f=
ont-family: courier new,monospace;">`try_emplace`</span>, <span style=3D"fo=
nt-family: courier new,monospace;">`extract`</span>, <span style=3D"font-fa=
mily: courier new,monospace;">`erase`</span>). Is there some reason these f=
unctions don&#39;t exist yet?<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/b7fedc9e-d39a-4bb9-b6fe-0b02e3a8fe88%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/b7fedc9e-d39a-4bb9-b6fe-0b02e3a8fe88=
%40isocpp.org</a>.<br />

------=_Part_1719_166655105.1490147570636--

------=_Part_1718_1459121929.1490147570635--

.

------=_Part_4217_1557193294.1490153952252
Content-Type: multipart/alternative;
 boundary="----=_Part_4218_526221182.1490153952253"

------=_Part_4218_526221182.1490153952253
Content-Type: text/plain; charset=UTF-8



On Tuesday, March 21, 2017 at 9:52:50 PM UTC-4, joseph....@gmail.com wrote:
>
> Proposal N3657
> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm> added
> the following heterogeneous lookup functions in the presence of a
> `Compare::is_transparent` tag:
>
> find
> count
> lower_bound
> upper_bound
> equal_range
>
> However, heterogeneous keys are not supported for modifiers. My use case
> is wanting to use a `string_view` as a key into a `map<string, X>`. For
> efficiency, I only want a `string` to be constructed if the entry doesn't
> already exist.
>
> auto count_k_mers(std::string_view s, std::size_t length) {
>   std::map<std::string, std::size_t, std::less<>> counts;
>   for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
>     ++counts[s.substr(i, length)]; // error: no such function
> `operator[](string_view)`
>   }
>   return counts;
> }
>
> No overload of `operator[]` takes a heterogeneous key, hence the
> compilation error. The same is true for `try_emplace`:
>
>     ++counts.try_emplace(k_mer).first->second; // error: no such function
> `try_emplace(string_view)`
>
> I can't use `emplace` naively because that will create a `string` on
> every call. Instead, I am forced to do something like this:
>
> auto count_k_mers(std::string_view s, std::size_t length) {
>   std::map<std::string, std::size_t, std::less<>> counts;
>   for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
>     auto k_mer = s.substr(i, length);
>     auto it = counts.find(k_mer);
>     if (it == counts.end()) {
>       it = counts.emplace(k_mer, std::size_t()).first;
>     }
>     ++it->second;
>   }
>   return counts;
> }
>
> This could obviously be optimized by using `lower_bound` and
> `emplace_hint`, but what are the chances the average user will do this?
> So why not provide a heterogeneous `operator[]` that gives optimal
> performance by default?
>
> template <typename K>
> T& operator[](K const& k) {
>   auto it = lower_bound(k);
>   if (it == end() || Compare()(k, it->first)) {
>     it = emplace_hint(it, k, T());
>   }
>   return it->second;
> }
>
> Pretty much any function that takes a key could have a heterogeneous
> overload (`at`, `try_emplace`, `extract`, `erase`). Is there some reason
> these functions don't exist yet?
>

Well here's one. Currently, heterogeneous lookup requires precisely one
thing out of `K`: that `Compare` can compare it to `key_type`.  To
implement many of the functions you specify (like `emplace` and the like),
`K` now must be *convertible* to `key_type`. And that's a very different
requirement, one that not all heterogeneous lookup types will permit. This
is particularly true for `set`s, where the `T` type is usually a much more
complex object than `K` (which is why you want heterogeneous lookup in the
first place).

Now, you could make it so that these overloads only exist for `K`'s where
`is_convertible<K, key_type>` is true. This would be needed for any of the
functions that potentially insert a new item.

Indeed, `emplace` doesn't even include `key_type` in its signature; the
assumption is that it will always create a `pair<const key_type, T>` from
the values. So changing that would require a non-trivial change.
`try_emplace` at least has a specific value which is `key_type` that could
be augmented with an overload for a generic `K`.

--
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/62d6a375-9f86-4ec2-819f-4d22936d4701%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Tuesday, March 21, 2017 at 9:52:50 PM UTC-4, jo=
seph....@gmail.com 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">Proposal <a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs=
/papers/2013/n3657.htm" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"t=
his.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.open-std.or=
g%2Fjtc1%2Fsc22%2Fwg21%2Fdocs%2Fpapers%2F2013%2Fn3657.htm\x26sa\x3dD\x26snt=
z\x3d1\x26usg\x3dAFQjCNHpeX6NBNd4wdL7NE6JCy1c3aIhWg&#39;;return true;" oncl=
ick=3D"this.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.ope=
n-std.org%2Fjtc1%2Fsc22%2Fwg21%2Fdocs%2Fpapers%2F2013%2Fn3657.htm\x26sa\x3d=
D\x26sntz\x3d1\x26usg\x3dAFQjCNHpeX6NBNd4wdL7NE6JCy1c3aIhWg&#39;;return tru=
e;">N3657</a> added the following heterogeneous lookup functions in the pre=
sence of a <span style=3D"font-family:courier new,monospace">`Compare::is_t=
ransparent`</span> tag:<br><br><div style=3D"background-color:rgb(250,250,2=
50);border-color:rgb(187,187,187);border-style:solid;border-width:1px"><cod=
e><div><span style=3D"color:#000">find<br>count<br>lower_bound<br>upper_bou=
nd<br>equal_range</span></div></code></div><br>However, heterogeneous keys =
are not supported for modifiers. My use case is wanting to use a <span styl=
e=3D"font-family:courier new,monospace">`string_view`</span> as a key into =
a <span style=3D"font-family:courier new,monospace">`map&lt;string, X&gt;`<=
/span>. For efficiency, I only want a <span style=3D"font-family:courier ne=
w,monospace">`string`</span> to be constructed if the entry doesn&#39;t alr=
eady exist.<br><br><div style=3D"background-color:rgb(250,250,250);border-c=
olor:rgb(187,187,187);border-style:solid;border-width:1px"><code><div><span=
 style=3D"color:#008">auto</span><span style=3D"color:#000"> count_k_mers</=
span><span style=3D"color:#660">(</span><span style=3D"color:#000">std</spa=
n><span style=3D"color:#660">::</span><span style=3D"color:#000">string_vie=
w s</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> st=
d</span><span style=3D"color:#660">::</span><span style=3D"color:#000">size=
_t length</span><span style=3D"color:#660">)</span><span style=3D"color:#00=
0"> </span><span style=3D"color:#660">{</span><span style=3D"color:#000"><b=
r>=C2=A0 std</span><span style=3D"color:#660">::</span><span style=3D"color=
:#000">map</span><span style=3D"color:#660">&lt;</span><span style=3D"color=
:#000">std</span><span style=3D"color:#660">::</span><span style=3D"color:#=
008">string</span><span style=3D"color:#660">,</span><span style=3D"color:#=
000"> std</span><span style=3D"color:#660">::</span><span style=3D"color:#0=
00">size_t</span><span style=3D"color:#660">,</span><span style=3D"color:#0=
00"> std</span><span style=3D"color:#660">::</span><span style=3D"color:#00=
0">less</span><span style=3D"color:#660">&lt;&gt;&gt;</span><span style=3D"=
color:#000"> counts</span><span style=3D"color:#660">;</span><span style=3D=
"color:#000"><br>=C2=A0 </span><span style=3D"color:#008">for</span><span s=
tyle=3D"color:#000"> </span><span style=3D"color:#660">(</span><span style=
=3D"color:#000">std</span><span style=3D"color:#660">::</span><span style=
=3D"color:#000">size_t i </span><span style=3D"color:#660">=3D</span><span =
style=3D"color:#000"> </span><span style=3D"color:#066">0</span><span style=
=3D"color:#660">;</span><span style=3D"color:#000"> i </span><span style=3D=
"color:#660">&lt;</span><span style=3D"color:#000"> s</span><span style=3D"=
color:#660">.</span><span style=3D"color:#000">length</span><span style=3D"=
color:#660">()</span><span style=3D"color:#000"> </span><span style=3D"colo=
r:#660">-</span><span style=3D"color:#000"> length </span><span style=3D"co=
lor:#660">+</span><span style=3D"color:#000"> </span><span style=3D"color:#=
066">1</span><span style=3D"color:#660">;</span><span style=3D"color:#000">=
 </span><span style=3D"color:#660">++</span><span style=3D"color:#000">i</s=
pan><span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><=
span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=
=A0 </span><span style=3D"color:#660">++</span><span style=3D"color:#000">c=
ounts</span><span style=3D"color:#660">[</span><span style=3D"color:#000">s=
</span><span style=3D"color:#660">.</span><span style=3D"color:#000">substr=
</span><span style=3D"color:#660">(</span><span style=3D"color:#000">i</spa=
n><span style=3D"color:#660">,</span><span style=3D"color:#000"> length</sp=
an><span style=3D"color:#660">)];</span><span style=3D"color:#000"> </span>=
<span style=3D"color:#800">// error: no such function `operator[](string_vi=
ew)`</span><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"colo=
r:#660">}</span><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D=
"color:#008">return</span><span style=3D"color:#000"> counts</span><span st=
yle=3D"color:#660">;</span><span style=3D"color:#000"><br></span><span styl=
e=3D"color:#660">}</span></div></code></div><br>No overload of <span style=
=3D"font-family:courier new,monospace">`operator[]`</span> takes a heteroge=
neous key, hence the compilation error. The same is true for <span style=3D=
"font-family:courier new,monospace">`try_emplace`</span>:<br><br><div style=
=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,187);border-=
style:solid;border-width:1px"><code><div><span style=3D"color:#000">=C2=A0 =
=C2=A0 </span><span style=3D"color:#660">++</span><span style=3D"color:#000=
">counts</span><span style=3D"color:#660">.</span><span style=3D"color:#000=
">try_emplace</span><span style=3D"color:#660">(</span><span style=3D"color=
:#000">k_mer</span><span style=3D"color:#660">).</span><span style=3D"color=
:#000">fi<wbr>rst</span><span style=3D"color:#660">-&gt;</span><span style=
=3D"color:#000">second</span><span style=3D"color:#660">;</span><span style=
=3D"color:#000"> </span><span style=3D"color:#800">// error: no such functi=
on `try_emplace(string_view)`</span></div></code></div><br>I can&#39;t use =
<span style=3D"font-family:courier new,monospace">`emplace`</span> naively =
because that will create a <span style=3D"font-family:courier new,monospace=
">`string`</span> on every call. Instead, I am forced to do something like =
this:<br><br><div style=3D"background-color:rgb(250,250,250);border-color:r=
gb(187,187,187);border-style:solid;border-width:1px"><code><div><span style=
=3D"color:#008">auto</span><span style=3D"color:#000"> count_k_mers</span><=
span style=3D"color:#660">(</span><span style=3D"color:#000">std</span><spa=
n style=3D"color:#660">::</span><span style=3D"color:#000">string_view s</s=
pan><span style=3D"color:#660">,</span><span style=3D"color:#000"> std</spa=
n><span style=3D"color:#660">::</span><span style=3D"color:#000">size_t len=
gth</span><span style=3D"color:#660">)</span><span style=3D"color:#000"> </=
span><span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=
=A0 std</span><span style=3D"color:#660">::</span><span style=3D"color:#000=
">map</span><span style=3D"color:#660">&lt;</span><span style=3D"color:#000=
">std</span><span style=3D"color:#660">::</span><span style=3D"color:#008">=
string</span><span style=3D"color:#660">,</span><span style=3D"color:#000">=
 std</span><span style=3D"color:#660">::</span><span style=3D"color:#000">s=
ize_t</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> =
std</span><span style=3D"color:#660">::</span><span style=3D"color:#000">le=
ss</span><span style=3D"color:#660">&lt;&gt;&gt;</span><span style=3D"color=
:#000"> counts</span><span style=3D"color:#660">;</span><span style=3D"colo=
r:#000"><br>=C2=A0 </span><span style=3D"color:#008">for</span><span style=
=3D"color:#000"> </span><span style=3D"color:#660">(</span><span style=3D"c=
olor:#000">std</span><span style=3D"color:#660">::</span><span style=3D"col=
or:#000">size_t i </span><span style=3D"color:#660">=3D</span><span style=
=3D"color:#000"> </span><span style=3D"color:#066">0</span><span style=3D"c=
olor:#660">;</span><span style=3D"color:#000"> i </span><span style=3D"colo=
r:#660">&lt;</span><span style=3D"color:#000"> s</span><span style=3D"color=
:#660">.</span><span style=3D"color:#000">length</span><span style=3D"color=
:#660">()</span><span style=3D"color:#000"> </span><span style=3D"color:#66=
0">-</span><span style=3D"color:#000"> length </span><span style=3D"color:#=
660">+</span><span style=3D"color:#000"> </span><span style=3D"color:#066">=
1</span><span style=3D"color:#660">;</span><span style=3D"color:#000"> </sp=
an><span style=3D"color:#660">++</span><span style=3D"color:#000">i</span><=
span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span =
style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 <=
/span><span style=3D"color:#008">auto</span><span style=3D"color:#000"> k_m=
er </span><span style=3D"color:#660">=3D</span><span style=3D"color:#000"> =
s</span><span style=3D"color:#660">.</span><span style=3D"color:#000">subst=
r</span><span style=3D"color:#660">(</span><span style=3D"color:#000">i</sp=
an><span style=3D"color:#660">,</span><span style=3D"color:#000"> length</s=
pan><span style=3D"color:#660">);</span><span style=3D"color:#000"><br>=C2=
=A0 =C2=A0 </span><span style=3D"color:#008">auto</span><span style=3D"colo=
r:#000"> it </span><span style=3D"color:#660">=3D</span><span style=3D"colo=
r:#000"> counts</span><span style=3D"color:#660">.</span><span style=3D"col=
or:#000">find</span><span style=3D"color:#660">(</span><span style=3D"color=
:#000">k_mer</span><span style=3D"color:#660">);</span><span style=3D"color=
:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">if</span><span s=
tyle=3D"color:#000"> </span><span style=3D"color:#660">(</span><span style=
=3D"color:#000">it </span><span style=3D"color:#660">=3D=3D</span><span sty=
le=3D"color:#000"> counts</span><span style=3D"color:#660">.</span><span st=
yle=3D"color:#008">end</span><span style=3D"color:#660">())</span><span sty=
le=3D"color:#000"> </span><span style=3D"color:#660">{</span><span style=3D=
"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 it </span><span style=3D"color:#660">=
=3D</span><span style=3D"color:#000"> counts</span><span style=3D"color:#66=
0">.</span><span style=3D"color:#000">emplace</span><span style=3D"color:#6=
60">(</span><span style=3D"color:#000">k_mer</span><span style=3D"color:#66=
0">,</span><span style=3D"color:#000"> std</span><span style=3D"color:#660"=
>::</span><span style=3D"color:#000">size_t</span><span style=3D"color:#660=
">()).</span><span style=3D"color:#000">first</span><span style=3D"color:#6=
60">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=
=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span=
><span style=3D"color:#660">++</span><span style=3D"color:#000">it</span><s=
pan style=3D"color:#660">-&gt;</span><span style=3D"color:#000">second</spa=
n><span style=3D"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =
</span><span style=3D"color:#660">}</span><span style=3D"color:#000"><br>=
=C2=A0 </span><span style=3D"color:#008">return</span><span style=3D"color:=
#000"> counts</span><span style=3D"color:#660">;</span><span style=3D"color=
:#000"><br></span><span style=3D"color:#660">}</span></div></code></div><br=
>This could obviously be optimized by using <span style=3D"font-family:cour=
ier new,monospace">`lower_bound`</span> and <span style=3D"font-family:cour=
ier new,monospace">`emplace_hint`</span>, but what are the chances the aver=
age user will do this? So why not provide a heterogeneous <span style=3D"fo=
nt-family:courier new,monospace">`operator[]`</span> that gives optimal per=
formance by default?<br><br><div style=3D"background-color:rgb(250,250,250)=
;border-color:rgb(187,187,187);border-style:solid;border-width:1px"><code><=
div><span style=3D"color:#008">template</span><span style=3D"color:#000"> <=
/span><span style=3D"color:#660">&lt;</span><span style=3D"color:#008">type=
name</span><span style=3D"color:#000"> K</span><span style=3D"color:#660">&=
gt;</span><span style=3D"color:#000"><br>T</span><span style=3D"color:#660"=
>&amp;</span><span style=3D"color:#000"> </span><span style=3D"color:#008">=
operator</span><span style=3D"color:#660">[](</span><span style=3D"color:#0=
00">K </span><span style=3D"color:#008">const</span><span style=3D"color:#6=
60">&amp;</span><span style=3D"color:#000"> k</span><span style=3D"color:#6=
60">)</span><span style=3D"color:#000"> </span><span style=3D"color:#660">{=
</span><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#0=
08">auto</span><span style=3D"color:#000"> it </span><span style=3D"color:#=
660">=3D</span><span style=3D"color:#000"> lower_bound</span><span style=3D=
"color:#660">(</span><span style=3D"color:#000">k</span><span style=3D"colo=
r:#660">);</span><span style=3D"color:#000"><br>=C2=A0 </span><span style=
=3D"color:#008">if</span><span style=3D"color:#000"> </span><span style=3D"=
color:#660">(</span><span style=3D"color:#000">it </span><span style=3D"col=
or:#660">=3D=3D</span><span style=3D"color:#000"> </span><span style=3D"col=
or:#008">end</span><span style=3D"color:#660">()</span><span style=3D"color=
:#000"> </span><span style=3D"color:#660">||</span><span style=3D"color:#00=
0"> </span><span style=3D"color:#606">Compare</span><span style=3D"color:#6=
60">()(</span><span style=3D"color:#000">k</span><span style=3D"color:#660"=
>,</span><span style=3D"color:#000"> it</span><span style=3D"color:#660">-&=
gt;</span><span style=3D"color:#000">first</span><span style=3D"color:#660"=
>))</span><span style=3D"color:#000"> </span><span style=3D"color:#660">{</=
span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 it </span><span style=3D"=
color:#660">=3D</span><span style=3D"color:#000"> emplace_hint</span><span =
style=3D"color:#660">(</span><span style=3D"color:#000">it</span><span styl=
e=3D"color:#660">,</span><span style=3D"color:#000"> k</span><span style=3D=
"color:#660">,</span><span style=3D"color:#000"> T</span><span style=3D"col=
or:#660">());</span><span style=3D"color:#000"><br>=C2=A0 </span><span styl=
e=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 </span><span=
 style=3D"color:#008">return</span><span style=3D"color:#000"> it</span><sp=
an style=3D"color:#660">-&gt;</span><span style=3D"color:#000">second</span=
><span style=3D"color:#660">;</span><span style=3D"color:#000"><br></span><=
span style=3D"color:#660">}</span></div></code></div><br>Pretty much any fu=
nction that takes a key could have a heterogeneous overload (<span style=3D=
"font-family:courier new,monospace">`at`</span>, <span style=3D"font-family=
:courier new,monospace">`try_emplace`</span>, <span style=3D"font-family:co=
urier new,monospace">`extract`</span>, <span style=3D"font-family:courier n=
ew,monospace">`erase`</span>). Is there some reason these functions don&#39=
;t exist yet?<br></div></blockquote><div><br>Well here&#39;s one. Currently=
, heterogeneous lookup requires precisely one thing out of `K`: that `Compa=
re` can compare it to `key_type`.=C2=A0 To implement many of the functions =
you specify (like `emplace` and the like), `K` now must be <i>convertible</=
i> to `key_type`. And that&#39;s a very different requirement, one that not=
 all heterogeneous lookup types will permit. This is particularly true for =
`set`s, where the `T` type is usually a much more complex object than `K` (=
which is why you want heterogeneous lookup in the first place).<br><br>Now,=
 you could make it so that these overloads only exist for `K`&#39;s=20
where `is_convertible&lt;K, key_type&gt;` is true. This would be needed=20
for any of the functions that potentially insert a new item.<br><br>Indeed,=
 `emplace` doesn&#39;t even include `key_type` in its signature; the assump=
tion is that it will always create a `pair&lt;const key_type, T&gt;` from t=
he values. So changing that would require a non-trivial change. `try_emplac=
e` at least has a specific value which is `key_type` that could be augmente=
d with an overload for a generic `K`.<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/62d6a375-9f86-4ec2-819f-4d22936d4701%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/62d6a375-9f86-4ec2-819f-4d22936d4701=
%40isocpp.org</a>.<br />

------=_Part_4218_526221182.1490153952253--

------=_Part_4217_1557193294.1490153952252--

.

------=_Part_2602_171116835.1490162305384
Content-Type: multipart/alternative;
 boundary="----=_Part_2603_742929530.1490162305386"

------=_Part_2603_742929530.1490162305386
Content-Type: text/plain; charset=UTF-8



On Wednesday, 22 March 2017 11:39:12 UTC+8, Nicol Bolas wrote:
>
>
>
> On Tuesday, March 21, 2017 at 9:52:50 PM UTC-4, joseph....@gmail.com
> wrote:
>>
>> Proposal N3657
>> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm>
>> added the following heterogeneous lookup functions in the presence of a
>> `Compare::is_transparent` tag:
>>
>> find
>> count
>> lower_bound
>> upper_bound
>> equal_range
>>
>> However, heterogeneous keys are not supported for modifiers. My use case
>> is wanting to use a `string_view` as a key into a `map<string, X>`. For
>> efficiency, I only want a `string` to be constructed if the entry
>> doesn't already exist.
>>
>> auto count_k_mers(std::string_view s, std::size_t length) {
>>   std::map<std::string, std::size_t, std::less<>> counts;
>>   for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
>>     ++counts[s.substr(i, length)]; // error: no such function
>> `operator[](string_view)`
>>   }
>>   return counts;
>> }
>>
>> No overload of `operator[]` takes a heterogeneous key, hence the
>> compilation error. The same is true for `try_emplace`:
>>
>>     ++counts.try_emplace(k_mer).first->second; // error: no such
>> function `try_emplace(string_view)`
>>
>> I can't use `emplace` naively because that will create a `string` on
>> every call. Instead, I am forced to do something like this:
>>
>> auto count_k_mers(std::string_view s, std::size_t length) {
>>   std::map<std::string, std::size_t, std::less<>> counts;
>>   for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
>>     auto k_mer = s.substr(i, length);
>>     auto it = counts.find(k_mer);
>>     if (it == counts.end()) {
>>       it = counts.emplace(k_mer, std::size_t()).first;
>>     }
>>     ++it->second;
>>   }
>>   return counts;
>> }
>>
>> This could obviously be optimized by using `lower_bound` and
>> `emplace_hint`, but what are the chances the average user will do this?
>> So why not provide a heterogeneous `operator[]` that gives optimal
>> performance by default?
>>
>> template <typename K>
>> T& operator[](K const& k) {
>>   auto it = lower_bound(k);
>>   if (it == end() || Compare()(k, it->first)) {
>>     it = emplace_hint(it, k, T());
>>   }
>>   return it->second;
>> }
>>
>> Pretty much any function that takes a key could have a heterogeneous
>> overload (`at`, `try_emplace`, `extract`, `erase`). Is there some reason
>> these functions don't exist yet?
>>
>
> Well here's one. Currently, heterogeneous lookup requires precisely one
> thing out of `K`: that `Compare` can compare it to `key_type`.  To
> implement many of the functions you specify (like `emplace` and the like),
> `K` now must be *convertible* to `key_type`. And that's a very different
> requirement, one that not all heterogeneous lookup types will permit. This
> is particularly true for `set`s, where the `T` type is usually a much more
> complex object than `K` (which is why you want heterogeneous lookup in the
> first place).
>

The requirements for `K` don't have to be the same for every function, so I
don't see this as a reason why they shouldn't exist.


> Now, you could make it so that these overloads only exist for `K`'s where
> `is_convertible<K, key_type>` is true. This would be needed for any of the
> functions that potentially insert a new item.
>

For my use case to be supported, the requirement would have to be `is_constructible_v<key_type,
K>` is true. At first glance this seems unwise, as it has the potential to
make explicit conversions somewhat more implicit; for example:

int i;
std::map<std::unique_ptr<int>, int> m;
m[&i] = 42; // bad

However, there is still the implicit requirement that `K` be comparable to
`key_type`, so this example would still fail as `unique_ptr<T>` is not
comparable to `T*`. It works in the `string_view` case because `string` is
convertible to `string_view`. I'm not sure why `string_view` is not
convertible to `string`. I also note that the following already *does* work:

m.insert(std::make_pair(&i, 42));

Indeed, `emplace` doesn't even include `key_type` in its signature; the
> assumption is that it will always create a `pair<const key_type, T>` from
> the values. So changing that would require a non-trivial change.
> `try_emplace` at least has a specific value which is `key_type` that could
> be augmented with an overload for a generic `K`.
>

 I don't think trying to support this for `emplace` is necessary given the
existence of `try_emplace`.

--
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/8dece81c-d0f0-43a0-b431-5c7c87686678%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Wednesday, 22 March 2017 11:39:12 UTC+8, Nicol =
Bolas  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 Tuesday, March 21, 2017 at 9:52:50 PM UTC-4, <a>joseph....@gmail=
..com</a> 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">Pro=
posal <a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3=
657.htm" rel=3D"nofollow" target=3D"_blank" onmousedown=3D"this.href=3D&#39=
;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.open-std.org%2Fjtc1%2Fsc22=
%2Fwg21%2Fdocs%2Fpapers%2F2013%2Fn3657.htm\x26sa\x3dD\x26sntz\x3d1\x26usg\x=
3dAFQjCNHpeX6NBNd4wdL7NE6JCy1c3aIhWg&#39;;return true;" onclick=3D"this.hre=
f=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.open-std.org%2Fjtc=
1%2Fsc22%2Fwg21%2Fdocs%2Fpapers%2F2013%2Fn3657.htm\x26sa\x3dD\x26sntz\x3d1\=
x26usg\x3dAFQjCNHpeX6NBNd4wdL7NE6JCy1c3aIhWg&#39;;return true;">N3657</a> a=
dded the following heterogeneous lookup functions in the presence of a <spa=
n style=3D"font-family:courier new,monospace">`Compare::is_transparent`</sp=
an> tag:<br><br><div style=3D"background-color:rgb(250,250,250);border-colo=
r:rgb(187,187,187);border-style:solid;border-width:1px"><code><div><span st=
yle=3D"color:#000">find<br>count<br>lower_bound<br>upper_bound<br>equal_ran=
ge</span></div></code></div><br>However, heterogeneous keys are not support=
ed for modifiers. My use case is wanting to use a <span style=3D"font-famil=
y:courier new,monospace">`string_view`</span> as a key into a <span style=
=3D"font-family:courier new,monospace">`map&lt;string, X&gt;`</span>. For e=
fficiency, I only want a <span style=3D"font-family:courier new,monospace">=
`string`</span> to be constructed if the entry doesn&#39;t already exist.<b=
r><br><div style=3D"background-color:rgb(250,250,250);border-color:rgb(187,=
187,187);border-style:solid;border-width:1px"><code><div><span style=3D"col=
or:#008">auto</span><span style=3D"color:#000"> count_k_mers</span><span st=
yle=3D"color:#660">(</span><span style=3D"color:#000">std</span><span style=
=3D"color:#660">::</span><span style=3D"color:#000">string_view s</span><sp=
an style=3D"color:#660">,</span><span style=3D"color:#000"> std</span><span=
 style=3D"color:#660">::</span><span style=3D"color:#000">size_t length</sp=
an><span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><s=
pan style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 std<=
/span><span style=3D"color:#660">::</span><span style=3D"color:#000">map</s=
pan><span style=3D"color:#660">&lt;</span><span style=3D"color:#000">std</s=
pan><span style=3D"color:#660">::</span><span style=3D"color:#008">string</=
span><span style=3D"color:#660">,</span><span style=3D"color:#000"> std</sp=
an><span style=3D"color:#660">::</span><span style=3D"color:#000">size_t</s=
pan><span style=3D"color:#660">,</span><span style=3D"color:#000"> std</spa=
n><span style=3D"color:#660">::</span><span style=3D"color:#000">less</span=
><span style=3D"color:#660">&lt;&gt;&gt;</span><span style=3D"color:#000"> =
counts</span><span style=3D"color:#660">;</span><span style=3D"color:#000">=
<br>=C2=A0 </span><span style=3D"color:#008">for</span><span style=3D"color=
:#000"> </span><span style=3D"color:#660">(</span><span style=3D"color:#000=
">std</span><span style=3D"color:#660">::</span><span style=3D"color:#000">=
size_t i </span><span style=3D"color:#660">=3D</span><span style=3D"color:#=
000"> </span><span style=3D"color:#066">0</span><span style=3D"color:#660">=
;</span><span style=3D"color:#000"> i </span><span style=3D"color:#660">&lt=
;</span><span style=3D"color:#000"> s</span><span style=3D"color:#660">.</s=
pan><span style=3D"color:#000">length</span><span style=3D"color:#660">()</=
span><span style=3D"color:#000"> </span><span style=3D"color:#660">-</span>=
<span style=3D"color:#000"> length </span><span style=3D"color:#660">+</spa=
n><span style=3D"color:#000"> </span><span style=3D"color:#066">1</span><sp=
an style=3D"color:#660">;</span><span style=3D"color:#000"> </span><span st=
yle=3D"color:#660">++</span><span style=3D"color:#000">i</span><span style=
=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=3D"c=
olor:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><spa=
n style=3D"color:#660">++</span><span style=3D"color:#000">counts</span><sp=
an style=3D"color:#660">[</span><span style=3D"color:#000">s</span><span st=
yle=3D"color:#660">.</span><span style=3D"color:#000">substr</span><span st=
yle=3D"color:#660">(</span><span style=3D"color:#000">i</span><span style=
=3D"color:#660">,</span><span style=3D"color:#000"> length</span><span styl=
e=3D"color:#660">)];</span><span style=3D"color:#000"> </span><span style=
=3D"color:#800">// error: no such function `operator[](string_view)`</span>=
<span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#660">}</=
span><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#008=
">return</span><span style=3D"color:#000"> counts</span><span style=3D"colo=
r:#660">;</span><span style=3D"color:#000"><br></span><span style=3D"color:=
#660">}</span></div></code></div><br>No overload of <span style=3D"font-fam=
ily:courier new,monospace">`operator[]`</span> takes a heterogeneous key, h=
ence the compilation error. The same is true for <span style=3D"font-family=
:courier new,monospace">`try_emplace`</span>:<br><br><div style=3D"backgrou=
nd-color:rgb(250,250,250);border-color:rgb(187,187,187);border-style:solid;=
border-width:1px"><code><div><span style=3D"color:#000">=C2=A0 =C2=A0 </spa=
n><span style=3D"color:#660">++</span><span style=3D"color:#000">counts</sp=
an><span style=3D"color:#660">.</span><span style=3D"color:#000">try_emplac=
e</span><span style=3D"color:#660">(</span><span style=3D"color:#000">k_mer=
</span><span style=3D"color:#660">).</span><span style=3D"color:#000">fi<wb=
r>rst</span><span style=3D"color:#660">-&gt;</span><span style=3D"color:#00=
0">second</span><span style=3D"color:#660">;</span><span style=3D"color:#00=
0"> </span><span style=3D"color:#800">// error: no such function `try_empla=
ce(string_view)`</span></div></code></div><br>I can&#39;t use <span style=
=3D"font-family:courier new,monospace">`emplace`</span> naively because tha=
t will create a <span style=3D"font-family:courier new,monospace">`string`<=
/span> on every call. Instead, I am forced to do something like this:<br><b=
r><div style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,=
187);border-style:solid;border-width:1px"><code><div><span style=3D"color:#=
008">auto</span><span style=3D"color:#000"> count_k_mers</span><span style=
=3D"color:#660">(</span><span style=3D"color:#000">std</span><span style=3D=
"color:#660">::</span><span style=3D"color:#000">string_view s</span><span =
style=3D"color:#660">,</span><span style=3D"color:#000"> std</span><span st=
yle=3D"color:#660">::</span><span style=3D"color:#000">size_t length</span>=
<span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span=
 style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 std</sp=
an><span style=3D"color:#660">::</span><span style=3D"color:#000">map</span=
><span style=3D"color:#660">&lt;</span><span style=3D"color:#000">std</span=
><span style=3D"color:#660">::</span><span style=3D"color:#008">string</spa=
n><span style=3D"color:#660">,</span><span style=3D"color:#000"> std</span>=
<span style=3D"color:#660">::</span><span style=3D"color:#000">size_t</span=
><span style=3D"color:#660">,</span><span style=3D"color:#000"> std</span><=
span style=3D"color:#660">::</span><span style=3D"color:#000">less</span><s=
pan style=3D"color:#660">&lt;&gt;&gt;</span><span style=3D"color:#000"> cou=
nts</span><span style=3D"color:#660">;</span><span style=3D"color:#000"><br=
>=C2=A0 </span><span style=3D"color:#008">for</span><span style=3D"color:#0=
00"> </span><span style=3D"color:#660">(</span><span style=3D"color:#000">s=
td</span><span style=3D"color:#660">::</span><span style=3D"color:#000">siz=
e_t i </span><span style=3D"color:#660">=3D</span><span style=3D"color:#000=
"> </span><span style=3D"color:#066">0</span><span style=3D"color:#660">;</=
span><span style=3D"color:#000"> i </span><span style=3D"color:#660">&lt;</=
span><span style=3D"color:#000"> s</span><span style=3D"color:#660">.</span=
><span style=3D"color:#000">length</span><span style=3D"color:#660">()</spa=
n><span style=3D"color:#000"> </span><span style=3D"color:#660">-</span><sp=
an style=3D"color:#000"> length </span><span style=3D"color:#660">+</span><=
span style=3D"color:#000"> </span><span style=3D"color:#066">1</span><span =
style=3D"color:#660">;</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">++</span><span style=3D"color:#000">i</span><span style=3D"=
color:#660">)</span><span style=3D"color:#000"> </span><span style=3D"color=
:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span st=
yle=3D"color:#008">auto</span><span style=3D"color:#000"> k_mer </span><spa=
n style=3D"color:#660">=3D</span><span style=3D"color:#000"> s</span><span =
style=3D"color:#660">.</span><span style=3D"color:#000">substr</span><span =
style=3D"color:#660">(</span><span style=3D"color:#000">i</span><span style=
=3D"color:#660">,</span><span style=3D"color:#000"> length</span><span styl=
e=3D"color:#660">);</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </sp=
an><span style=3D"color:#008">auto</span><span style=3D"color:#000"> it </s=
pan><span style=3D"color:#660">=3D</span><span style=3D"color:#000"> counts=
</span><span style=3D"color:#660">.</span><span style=3D"color:#000">find</=
span><span style=3D"color:#660">(</span><span style=3D"color:#000">k_mer</s=
pan><span style=3D"color:#660">);</span><span style=3D"color:#000"><br>=C2=
=A0 =C2=A0 </span><span style=3D"color:#008">if</span><span style=3D"color:=
#000"> </span><span style=3D"color:#660">(</span><span style=3D"color:#000"=
>it </span><span style=3D"color:#660">=3D=3D</span><span style=3D"color:#00=
0"> counts</span><span style=3D"color:#660">.</span><span style=3D"color:#0=
08">end</span><span style=3D"color:#660">())</span><span style=3D"color:#00=
0"> </span><span style=3D"color:#660">{</span><span style=3D"color:#000"><b=
r>=C2=A0 =C2=A0 =C2=A0 it </span><span style=3D"color:#660">=3D</span><span=
 style=3D"color:#000"> counts</span><span style=3D"color:#660">.</span><spa=
n style=3D"color:#000">emplace</span><span style=3D"color:#660">(</span><sp=
an style=3D"color:#000">k_mer</span><span style=3D"color:#660">,</span><spa=
n style=3D"color:#000"> std</span><span style=3D"color:#660">::</span><span=
 style=3D"color:#000">size_t</span><span style=3D"color:#660">()).</span><s=
pan style=3D"color:#000">first</span><span style=3D"color:#660">;</span><sp=
an style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#660"=
>}</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D=
"color:#660">++</span><span style=3D"color:#000">it</span><span style=3D"co=
lor:#660">-&gt;</span><span style=3D"color:#000">second</span><span style=
=3D"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 </span><span =
style=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 </span><=
span style=3D"color:#008">return</span><span style=3D"color:#000"> counts</=
span><span style=3D"color:#660">;</span><span style=3D"color:#000"><br></sp=
an><span style=3D"color:#660">}</span></div></code></div><br>This could obv=
iously be optimized by using <span style=3D"font-family:courier new,monospa=
ce">`lower_bound`</span> and <span style=3D"font-family:courier new,monospa=
ce">`emplace_hint`</span>, but what are the chances the average user will d=
o this? So why not provide a heterogeneous <span style=3D"font-family:couri=
er new,monospace">`operator[]`</span> that gives optimal performance by def=
ault?<br><br><div style=3D"background-color:rgb(250,250,250);border-color:r=
gb(187,187,187);border-style:solid;border-width:1px"><code><div><span style=
=3D"color:#008">template</span><span style=3D"color:#000"> </span><span sty=
le=3D"color:#660">&lt;</span><span style=3D"color:#008">typename</span><spa=
n style=3D"color:#000"> K</span><span style=3D"color:#660">&gt;</span><span=
 style=3D"color:#000"><br>T</span><span style=3D"color:#660">&amp;</span><s=
pan style=3D"color:#000"> </span><span style=3D"color:#008">operator</span>=
<span style=3D"color:#660">[](</span><span style=3D"color:#000">K </span><s=
pan style=3D"color:#008">const</span><span style=3D"color:#660">&amp;</span=
><span style=3D"color:#000"> k</span><span style=3D"color:#660">)</span><sp=
an style=3D"color:#000"> </span><span style=3D"color:#660">{</span><span st=
yle=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#008">auto</span>=
<span style=3D"color:#000"> it </span><span style=3D"color:#660">=3D</span>=
<span style=3D"color:#000"> lower_bound</span><span style=3D"color:#660">(<=
/span><span style=3D"color:#000">k</span><span style=3D"color:#660">);</spa=
n><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#008">i=
f</span><span style=3D"color:#000"> </span><span style=3D"color:#660">(</sp=
an><span style=3D"color:#000">it </span><span style=3D"color:#660">=3D=3D</=
span><span style=3D"color:#000"> </span><span style=3D"color:#008">end</spa=
n><span style=3D"color:#660">()</span><span style=3D"color:#000"> </span><s=
pan style=3D"color:#660">||</span><span style=3D"color:#000"> </span><span =
style=3D"color:#606">Compare</span><span style=3D"color:#660">()(</span><sp=
an style=3D"color:#000">k</span><span style=3D"color:#660">,</span><span st=
yle=3D"color:#000"> it</span><span style=3D"color:#660">-&gt;</span><span s=
tyle=3D"color:#000">first</span><span style=3D"color:#660">))</span><span s=
tyle=3D"color:#000"> </span><span style=3D"color:#660">{</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 it </span><span style=3D"color:#660">=3D<=
/span><span style=3D"color:#000"> emplace_hint</span><span style=3D"color:#=
660">(</span><span style=3D"color:#000">it</span><span style=3D"color:#660"=
>,</span><span style=3D"color:#000"> k</span><span style=3D"color:#660">,</=
span><span style=3D"color:#000"> T</span><span style=3D"color:#660">());</s=
pan><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:#660"=
>}</span><span style=3D"color:#000"><br>=C2=A0 </span><span style=3D"color:=
#008">return</span><span style=3D"color:#000"> it</span><span style=3D"colo=
r:#660">-&gt;</span><span style=3D"color:#000">second</span><span style=3D"=
color:#660">;</span><span style=3D"color:#000"><br></span><span style=3D"co=
lor:#660">}</span></div></code></div><br>Pretty much any function that take=
s a key could have a heterogeneous overload (<span style=3D"font-family:cou=
rier new,monospace">`at`</span>, <span style=3D"font-family:courier new,mon=
ospace">`try_emplace`</span>, <span style=3D"font-family:courier new,monosp=
ace">`extract`</span>, <span style=3D"font-family:courier new,monospace">`e=
rase`</span>). Is there some reason these functions don&#39;t exist yet?<br=
></div></blockquote><div><br>Well here&#39;s one. Currently, heterogeneous =
lookup requires precisely one thing out of `K`: that `Compare` can compare =
it to `key_type`.=C2=A0 To implement many of the functions you specify (lik=
e `emplace` and the like), `K` now must be <i>convertible</i> to `key_type`=
.. And that&#39;s a very different requirement, one that not all heterogeneo=
us lookup types will permit. This is particularly true for `set`s, where th=
e `T` type is usually a much more complex object than `K` (which is why you=
 want heterogeneous lookup in the first place).<br></div></div></blockquote=
><div><br>The requirements for <span style=3D"font-family: courier new,mono=
space;">`K`</span> don&#39;t have to be the same for every function, so I d=
on&#39;t see this as a reason why they shouldn&#39;t exist.<br>=C2=A0</div>=
<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bor=
der-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>Now, you=
 could make it so that these overloads only exist for `K`&#39;s=20
where `is_convertible&lt;K, key_type&gt;` is true. This would be needed=20
for any of the functions that potentially insert a new item.<br></div></div=
></blockquote><div><br>For my use case to be supported, the requirement wou=
ld have to be <span style=3D"font-family: courier new,monospace;">`is_const=
ructible_v&lt;key_type, K&gt;`</span> is true. At first glance this seems u=
nwise, as it has the potential to make explicit conversions somewhat more i=
mplicit; for example:<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"prett=
yprint"><div class=3D"subprettyprint"><span style=3D"color: #008;" class=3D=
"styled-by-prettify">int</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"> i</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>std</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">map</span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify">std</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify">unique_ptr</span><span style=3D"color: #08=
0;" class=3D"styled-by-prettify">&lt;int&gt;</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">int</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> m</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>m</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">[&amp;</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify">i</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: #660;" clas=
s=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"> </span><span style=3D"color: #066;" class=3D"styled-by-p=
rettify">42</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: #800;" class=3D"styled-by-prettify">// bad</span></di=
v></code></div><br>However, there is still the implicit requirement that <s=
pan style=3D"font-family: courier new,monospace;">`K`</span> be comparable =
to <span style=3D"font-family: courier new,monospace;">`key_type`</span>, s=
o this example would still fail as <span style=3D"font-family: courier new,=
monospace;">`unique_ptr&lt;T&gt;`</span> is not comparable to <span style=
=3D"font-family: courier new,monospace;">`T*`</span>. It works in the <span=
 style=3D"font-family: courier new,monospace;">`string_view`</span> case be=
cause <span style=3D"font-family: courier new,monospace;">`string`</span> i=
s convertible to <span style=3D"font-family: courier new,monospace;">`strin=
g_view`</span>. I&#39;m not sure why <span style=3D"font-family: courier ne=
w,monospace;">`string_view`</span> is not convertible to <span style=3D"fon=
t-family: courier new,monospace;">`string`</span>. I also note that the fol=
lowing already <i>does</i> work:<br><br><div style=3D"background-color: rgb=
(250, 250, 250); border-color: rgb(187, 187, 187); border-style: solid; bor=
der-width: 1px; overflow-wrap: break-word;" class=3D"prettyprint"><code cla=
ss=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #000=
;" class=3D"styled-by-prettify">m</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">insert</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
">std</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify">make_pair</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">(&amp;</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify">i</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #066;"=
 class=3D"styled-by-prettify">42</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">));</span></div></code></div><br></div><blockquote =
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>Indeed, `emplace` do=
esn&#39;t even include `key_type` in its signature; the assumption is that =
it will always create a `pair&lt;const key_type, T&gt;` from the values. So=
 changing that would require a non-trivial change. `try_emplace` at least h=
as a specific value which is `key_type` that could be augmented with an ove=
rload for a generic `K`.<br></div></div></blockquote><div><br>=C2=A0I don&#=
39;t think trying to support this for <span style=3D"font-family: courier n=
ew,monospace;">`emplace`</span> is necessary given the existence of <span s=
tyle=3D"font-family: courier new,monospace;">`try_emplace`</span>.<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/8dece81c-d0f0-43a0-b431-5c7c87686678%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/8dece81c-d0f0-43a0-b431-5c7c87686678=
%40isocpp.org</a>.<br />

------=_Part_2603_742929530.1490162305386--

------=_Part_2602_171116835.1490162305384--

.

------=_Part_3151_1276123795.1490187725267
Content-Type: multipart/alternative;
 boundary="----=_Part_3152_1847860495.1490187725267"

------=_Part_3152_1847860495.1490187725267
Content-Type: text/plain; charset=UTF-8

I could imagine extending try_emplace to transparent comparators. That was
out of scope for N4279 because I wanted to keep it simple. Also,
transparent operations are tricky for the hash containers, so we'd have to
think carefully about that. We'd probably only want to support them in
std::map::try_emplace for now.

The fundamental idea of try_emplace is that *no objects* are constructed
from the arguments until the lookup has been done. This idea has to exclude
things like comparators that take arguments by prvalue, of course, so I
suppose you could rephrase the goal to say that no objects are constructed
in order to formulate the key lookup expression. And I think that could be
consistently extended to a templated key parameter when the comparator is
transparent; the key parameter would be a forwarding reference, and no
objects would be constructed.

--
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/52ac3bc5-0509-4d16-9aa9-27ea43df4673%40isocpp.org.

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

<div dir=3D"ltr">I could imagine extending try_emplace to transparent compa=
rators. That was out of scope for N4279 because I wanted to keep it simple.=
 Also, transparent operations are tricky for the hash containers, so we&#39=
;d have to think carefully about that. We&#39;d probably only want to suppo=
rt them in std::map::try_emplace for now.<div><br></div><div>The fundamenta=
l idea of try_emplace is that *no objects* are constructed from the argumen=
ts until the lookup has been done. This idea has to exclude things like com=
parators that take arguments by prvalue, of course, so I suppose you could =
rephrase the goal to say that no objects are constructed in order to formul=
ate the key lookup expression. And I think that could be consistently exten=
ded to a templated key parameter when the comparator is transparent; the ke=
y parameter would be a forwarding reference, and no objects would be constr=
ucted.</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/52ac3bc5-0509-4d16-9aa9-27ea43df4673%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/52ac3bc5-0509-4d16-9aa9-27ea43df4673=
%40isocpp.org</a>.<br />

------=_Part_3152_1847860495.1490187725267--

------=_Part_3151_1276123795.1490187725267--

.

------=_Part_2920_1269918659.1490322688792
Content-Type: multipart/alternative;
 boundary="----=_Part_2921_1933825214.1490322688792"

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

On Wednesday, 22 March 2017 21:02:05 UTC+8, Thomas K=C3=B6ppe wrote:
>
> I could imagine extending try_emplace to transparent comparators. That wa=
s=20
> out of scope for N4279 because I wanted to keep it simple. Also,=20
> transparent operations are tricky for the hash containers, so we'd have t=
o=20
> think carefully about that. We'd probably only want to support them in=20
> std::map::try_emplace for now.
>
> The fundamental idea of try_emplace is that *no objects* are constructed=
=20
> from the arguments until the lookup has been done. This idea has to exclu=
de=20
> things like comparators that take arguments by prvalue, of course, so I=
=20
> suppose you could rephrase the goal to say that no objects are constructe=
d=20
> in order to formulate the key lookup expression. And I think that could b=
e=20
> consistently extended to a templated key parameter when the comparator is=
=20
> transparent; the key parameter would be a forwarding reference, and no=20
> objects would be constructed.
>

I agree. So the functions would look like this?

template <typename K, typename... Args>
pair<iterator, bool> try_emplace(K&& k, Args&&... args);


template <typename K>
T& operator[](K&& k);

And would only participate in overload resolution if `is_convertible_v<K&&,=
=20
key_type>`.

--=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/a6011d45-1296-4cdd-ab51-e389be399c51%40isocpp.or=
g.

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

<div dir=3D"ltr">On Wednesday, 22 March 2017 21:02:05 UTC+8, Thomas K=C3=B6=
ppe  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">I =
could imagine extending try_emplace to transparent comparators. That was ou=
t of scope for N4279 because I wanted to keep it simple. Also, transparent =
operations are tricky for the hash containers, so we&#39;d have to think ca=
refully about that. We&#39;d probably only want to support them in std::map=
::try_emplace for now.<div><br></div><div>The fundamental idea of try_empla=
ce is that *no objects* are constructed from the arguments until the lookup=
 has been done. This idea has to exclude things like comparators that take =
arguments by prvalue, of course, so I suppose you could rephrase the goal t=
o say that no objects are constructed in order to formulate the key lookup =
expression. And I think that could be consistently extended to a templated =
key parameter when the comparator is transparent; the key parameter would b=
e a forwarding reference, and no objects would be constructed.</div></div><=
/blockquote><div><br>I agree. So the functions would look like this?<br><br=
><div><div style=3D"background-color: rgb(250, 250, 250); border-color: rgb=
(187, 187, 187); border-style: solid; border-width: 1px; overflow-wrap: bre=
ak-word;" class=3D"prettyprint"><code class=3D"prettyprint"><div class=3D"s=
ubprettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">te=
mplate</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><s=
pan style=3D"color: #008;" class=3D"styled-by-prettify">typename</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> K</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: #008;" =
class=3D"styled-by-prettify">typename</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">...</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by=
-prettify">Args</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><=
br>pair</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt=
;</span><span style=3D"color: #000;" class=3D"styled-by-prettify">iterator<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">bool</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> try_emplace</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify">K</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">&amp;&amp;</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> k</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #606;" class=3D"styled-by-prettify">Args</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">&amp;&amp;...=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> args</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">);</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br><br><br></span><spa=
n 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"> K</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br>T</span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">&amp;</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify=
">operator</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
[](</span><span style=3D"color: #000;" class=3D"styled-by-prettify">K</span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">&amp;&amp;</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> k</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br></span></div></code></div><d=
iv><span class=3D"mw-geshi cpp source-cpp"><span class=3D"sy4"><br>And woul=
d only participate in overload resolution if <span style=3D"font-family: co=
urier new,monospace;">`</span></span></span><span style=3D"font-family: cou=
rier new,monospace;"><span class=3D"mw-geshi cpp source-cpp"><span class=3D=
"sy1"><span class=3D"mw-geshi cpp source-cpp"><span class=3D"sy1">is_conver=
tible_v&lt;K&amp;&amp;, key_type&gt;`.</span></span></span></span></span></=
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/a6011d45-1296-4cdd-ab51-e389be399c51%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/a6011d45-1296-4cdd-ab51-e389be399c51=
%40isocpp.org</a>.<br />

------=_Part_2921_1933825214.1490322688792--

------=_Part_2920_1269918659.1490322688792--

.