220 33175 article Path: news.gmane.org!.POSTED!not-for-mail From: Giovanni Funchal Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Add a few missing things from the iterator library Date: Tue, 11 Jul 2017 21:09:09 +0100 Lines: 257 Approved: news@gmane.org Message-ID: References: <9434787.nHRs7m2U1a@tjmaciei-mobl1> <6e2d133b-1c0a-49a9-ae2b-98d82d3a40d3@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="94eb2c12542a25a35205541048b0" X-Trace: blaine.gmane.org 1499803794 17088 195.159.176.226 (11 Jul 2017 20:09:54 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 11 Jul 2017 20:09:54 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDLLHL6CZMFBBD7BSTFQKGQED2DPYOQ@isocpp.org Tue Jul 11 22:09:49 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pg0-f69.google.com ([74.125.83.69]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dV1Tf-00044p-TA for gclcip-std-proposals@m.gmane.org; Tue, 11 Jul 2017 22:09:48 +0200 Original-Received: by mail-pg0-f69.google.com with SMTP id p10sf2947672pgr.6 for ; Tue, 11 Jul 2017 13:09:53 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1499803792; cv=pass; d=google.com; s=arc-20160816; b=mxap/XiwvgYWcZhsIxlKSW+NMSrDcJ+0Ti15L96Yv3hb+p1Ymun6tIQKVyUYRUbBrd Nb8IwzVd05ED558B7trVqwOrcilxc+HCVMnuBhnngnc7EkkGQWCiIRrBLjF0GhQQSi4O Vs34Q8q4rGdBiz1D9fN2FtZ7hv+HJhjGoSvZtmGIxycwPw+uBNQPzC0G1Gunm5R/49xm M1kenxFscccsjv74ASW/JME/f+UMVQS761vjFOhDRrDCemWhcScPboMO7vE1QE9Pcl9i z6XQqUepatPJ1cdIyoOqyWJCMXKLWEYzGoHSJM+LDGiWySc/Ib0Xz1ECUvyufrpHObfo sjfg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:to:subject:message-id:date :from:references:in-reply-to:mime-version:arc-authentication-results :arc-message-signature:dkim-signature:arc-authentication-results; bh=gb1hy79pROI7ea4Lj5RouNq/RmGsGCcXSdZ5fAfTTK0=; b=WW4YKFPirijuxgs8motHd41Y0dxBCR57AzKnK7z3GIS6DS8z3Vw/6QXJRm9ZR2zn4l AEASlJpJDlT0AaN+bhEk1gOu0PdK9aXypQ4fNVca2A+j73kde4Lq5LxwbYajMj2CKHYs 6M6EWN/RYgAuX7l31A4VCdKcihLJoy177+H9MhJ/wdKcOADH34U1WSv8gy1rCZ5U4UUz xl9bNaunxv1BWaL0GHQ79qlBxhB2x2tnjdM7dV4VsNjCbCSgpgT9r74vRR3U1sNG1F55 47R3s5civw9We8hUW1C0PN6qkESmv2CzmU5DVOkur1aDPGdW1OlHNVMB2nY3GQrlzuXm ObPw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.b=Uh+SnQqt; spf=pass (google.com: domain of gafunchal@gmail.com designates 2607:f8b0:400d:c0d::22f as permitted sender) smtp.mailfrom=gafunchal@gmail.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=gb1hy79pROI7ea4Lj5RouNq/RmGsGCcXSdZ5fAfTTK0=; b=DfB/cAqwA+u83kFeSIWlr3PiCpkFidoMYt/PBh77SrYHhJJHi7zjQ3XCvbRVU9Nwpd 1QGDwEa20wH8srMIsNLlIbcyt2HhOuRFfO/0tdrTmQqH+nEbOUpLwF2qRQ0df10VPees YO0FTQI/Pvi9t3/Xj3tH0Z2kP9lbv0bC5USNaCASbRsTrhuT2c3nKxetahuZr0SWny+v RHm6x7Z6DtyFdNJJ/UJFveKSxugAceh2d/BFD7XKE6g1gmJuFBUmMOLp5lQ12/udA5nO a1zFdoKV5qW3nxIzq6ltBhP6JR+K1oEfDWltlI/lh90vtND3y3rIhMfQtJaW4lrI6Uyk 424Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=gb1hy79pROI7ea4Lj5RouNq/RmGsGCcXSdZ5fAfTTK0=; b=mbcLBQJYy0RDrdkqxg3gqJMmBLVaDjgCf11ai4y4yaSh7EvPKGV2ul34F3vPrsuZ5o 7GfT/AigJJLxRRaONgTM/Cb3aJ2aau199Qjva0vqId1w7WCRytnESnIDRlH3ynvipp8m gKs97Km6rTs9IIMiSJjGY9en5oEWaL5q/EBG4spkN1cbIV3U+M2mOjwPiZ4ZAU0Np5PR os3R68KXRPt4XHdp1Kv4KQyFe5ESMiyo23bBzMRZN6BK/VjpQyVE15/G+3hPBG8OdXgR g6knW70LX60MsdwSODHIScKBgsuYD3z8DTrrl9iF7gbE1EZqYUqoy+0Dlps+eutbBxCL LR1A== X-Gm-Message-State: AIVw112MtjtVZhPeQgxzBdHozFoAH7yBZSfnff41YiBMg9L8w5REKJwI NmT7sav7LdSMx3K+ X-Received: by 10.99.4.151 with SMTP id 145mr100702pge.86.1499803792803; Tue, 11 Jul 2017 13:09:52 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.168.193 with SMTP id e62ls2235895ioj.6.gmail; Tue, 11 Jul 2017 13:09:51 -0700 (PDT) X-Received: by 10.237.53.79 with SMTP id b15mr2225398qte.83.1499803791095; Tue, 11 Jul 2017 13:09:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1499803791; cv=none; d=google.com; s=arc-20160816; b=N5GmQs/rosB/jL427psjXwqozICif1zjqfNDj9DDxqqU9+SamlKu9GOKXDqOYb0ySU QO/bS5qUrmDHro3ysqW01UmvQFpexoB2bC0pBsUtuOwkZEMIiXta6IlobE+2JZ2ni/dn 5S/MSfLpirbKa3nbHrxDP0yXB4HFEvf8AXyy630A0WB0zjj9jQW6yZrBZ6qVJT7dcqmu lgkMMiUTTAdQ84wEdbw/kQHJ54qYt+LO5GRJKX7jDsjtnsFUfLukhilYj2/WNtT7xXrH zSe+JZd5SlZasCdSFcm7Dvb8ABI1CeCqfbvel6l7MXKAIxASIK4cVBJW2t/+T87GMyWl Wxeg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:references:in-reply-to:mime-version :dkim-signature:arc-authentication-results; bh=3MVnfTsuaYsneQnW3CKYbcFVw1MrDP8pIeA+7O8UTt0=; b=GDXh7RCUDEzJFImPILbWk77AbALWJYqW0xZI2ne98Fqku4LSEtcDYejfVBIQxYdtjx TZr45WlAvjGFW4HXaSXjcMN41ZXJtgxzv+zolRR5vrDRTBlzYmO2P1CqcLgzc/J9emeK eRV8uHZ1kwFJ3ut/g4DQZqP8ec1qo5pCvl5qgx50SlOM9Y0B9Z6G70HhcXP/vam1hxb7 coQkY5P3y4nU5DvK4KzMCtqJrWbuGVuNJxH1A+GA33RrDMln1fjKB1tFiQnwJCAil5W2 fUpfv+vc2JIhIUVNZsN1QpqRXCodaNm58BQwJwRAhfyWly7JRCJkoQowSXRqBLNNFKio Z8cw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.b=Uh+SnQqt; spf=pass (google.com: domain of gafunchal@gmail.com designates 2607:f8b0:400d:c0d::22f as permitted sender) smtp.mailfrom=gafunchal@gmail.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gmail.com Original-Received: from mail-qt0-x22f.google.com (mail-qt0-x22f.google.com. [2607:f8b0:400d:c0d::22f]) by mx.google.com with ESMTPS id u2si241215qkh.392.2017.07.11.13.09.51 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 11 Jul 2017 13:09:51 -0700 (PDT) Received-SPF: pass (google.com: domain of gafunchal@gmail.com designates 2607:f8b0:400d:c0d::22f as permitted sender) client-ip=2607:f8b0:400d:c0d::22f; Original-Received: by mail-qt0-x22f.google.com with SMTP id i2so2614267qta.3 for ; Tue, 11 Jul 2017 13:09:51 -0700 (PDT) X-Received: by 10.237.41.225 with SMTP id o88mr2236589qtd.27.1499803790187; Tue, 11 Jul 2017 13:09:50 -0700 (PDT) Original-Received: by 10.237.33.227 with HTTP; Tue, 11 Jul 2017 13:09:09 -0700 (PDT) In-Reply-To: <6e2d133b-1c0a-49a9-ae2b-98d82d3a40d3@isocpp.org> X-Original-Sender: gafunchal@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.b=Uh+SnQqt; spf=pass (google.com: domain of gafunchal@gmail.com designates 2607:f8b0:400d:c0d::22f as permitted sender) smtp.mailfrom=gafunchal@gmail.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:33175 Archived-At: --94eb2c12542a25a35205541048b0 Content-Type: text/plain; charset="UTF-8" Hi, Thanks Thiago, Nicol, those are some very good points and I now think like you that (3) was a bad idea, but I still think proposals (1) and (2) might make sense to propose as additions. > Just try: This works: void f(std::unordered_map::const_iterator) {} void g(std::unordered_map::iterator it) { f(static_cast::const_iterator>(it)); } (this conversion is a container requirement) Granted it is not trivial to implement std::make_const_iterator so that it deduces the type to cast to, but I think disregarding implementation for one second that this just points out how useful this feature would be if g() needed a const_iterator for whatever reason, exactly because a const_iterator is not a const iterator. Furthermore, one way I like to reason about this is making the table below which illustrates the asymmetry in available functionality: (1) Iterator type -> access function templates iterator (std::begin/std::end) reverse_iterator (std::rbegin/std::rend) const_iterator (std::cbegin/std::cend) move_iterator (Missing std::mbegin/std::mend) (2) Iterator type -> conversion function template reverse_iterator (std::make_reverse_iterator) const_iterator (Missing std::make_const_iterator) move_iterator (std::make_move_iterator) Thanks, -- Giovanni On Tue, Jul 11, 2017 at 3:36 PM, Nicol Bolas wrote: > On Tuesday, July 11, 2017 at 2:14:08 AM UTC-4, Thiago Macieira wrote: >> >> On segunda-feira, 10 de julho de 2017 22:21:10 PDT Giovanni Funchal >> wrote: >> > I agree with Daniel's point that the 1:1 relation between container and >> > iterator types is not currently mandated. However: >> > - I believe it only affects (3). >> >> Strictly speaking, yes. But (2) is also difficult to achieve. You're >> asking for >> a way to transform an iterator to const_iterator, but those types are >> often >> unrelated. For example, for libstdc++'s std::unordered_map, the two >> iterator >> classes are just aliases to std::__detail::_Node_const_iterator and >> std::__detail::_Node_iterator. >> >> A const iterator is not the same as a const_iterator. >> >> > - Due to std::iterator_traits, iterators know something >> about >> > their container (iterator_category) so there is already limited scope >> for >> > an iterator to be used in multiple containers. BTW, perhaps >> > std::iterator_traits::iterator_container would be a better >> place >> > for (3). >> >> First, the category is the category of the iterator, not of the >> container. >> Second, you cannot have a link back to the container, period. (3) is >> simply >> unachievable. Just think of this, what should this be >> >> std::iterator_traits::container >> >> choose: >> std::vector >> std::string >> std::basic_string >> really... >> std::array >> QVector >> QByteArray >> > > Even better, what about iterators that do not have containers? Things like > iterator wrappers and mutators. > > No algorithm has any right to query anything about the iterator's > container. That's the whole point of iterators: to be the intermediary > between the container of the data and the algorithm that acts on the data. > If there is something lacking in our iterator interfaces which algorithms > genuinely need, then *that* is what needs to be fixed. > > -- > 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/KQII_ogpfxo/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. > To view this discussion on the web visit https://groups.google.com/a/ > isocpp.org/d/msgid/std-proposals/6e2d133b-1c0a-49a9- > ae2b-98d82d3a40d3%40isocpp.org > > . > -- 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/CAKDaRu%2BvD5_rbhJw%3DdcjYC2X4BOHVpgAjb6sM%3DuGn0QvdzmD3Q%40mail.gmail.com. --94eb2c12542a25a35205541048b0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,

Thanks Thiago, Nicol, those are som= e very good points and I now think like you that (3) was a bad idea, but I = still think proposals (1) and (2) might make sense to propose as additions.=

> Just try:

This works:
void f(std::unordered_map<int, int>::const_iterator) {}<= br>
void g(std::unordered_map<int, int>::iterator it)<= br>
{
=C2=A0 =C2=A0 f(static_cast<std::unordered_map= <int, int>::const_iterator>(it));
}

=
(this conversion is a container requirement)

= Granted it is not trivial to implement std::make_const_iterator so that it = deduces the type to cast to, but I think disregarding implementation for on= e second that this just points out how useful this feature would be if g() = needed a const_iterator for whatever reason, exactly because a const_iterat= or is not a const iterator.

Furthermore, one way I= like to reason about this is making the table below which illustrates the = asymmetry in available functionality:

(1) Iterator= type -> access function templates
iterator (std::begin/std::e= nd)
reverse_iterator (std::rbegin/std::rend)
const_iter= ator (std::cbegin/std::cend)
move_iterator (Missing std::mbegin/s= td::mend)

(2) Iterator type -> conversion funct= ion template
reverse_iterator (std::make_reverse_iterator)
const_iterator (Missing std::make_const_iterator)
move_it= erator (std::make_move_iterator)

Thanks,
=
-- Giovanni<= /div>



On Tue, Jul 11, 2017 at 3:36 PM, Nicol Bolas= <jmckesson@gmail.com> wrote:
On T= uesday, July 11, 2017 at 2:14:08 AM UTC-4, Thiago Macieira wrote:On segunda-feira, 10 de julho de 20= 17 22:21:10 PDT Giovanni Funchal wrote:
> I agree with Daniel's point that the 1:1 relation between cont= ainer and
> iterator types is not currently mandated. However:
> - I believe it only affects (3).

Strictly speaking, yes. But (2) is also difficult to achieve. You'r= e asking for=20
a way to transform an iterator to const_iterator, but those types are o= ften=20
unrelated. For example, for libstdc++'s std::unordered_map, the two= iterator=20
classes are just aliases to std::__detail::_Node_const_iterator an= d=20
std::__detail::_Node_iterator.

A const iterator is not the same as a const_iterator.

> - Due to std::iterator_traits<iterator>, iterators know= something about
> their container (iterator_category) so there is already limited sc= ope for
> an iterator to be used in multiple containers. BTW, perhaps
> std::iterator_traits<iterator>::iterator_container woul= d be a better place
> for (3).

First, the category is the category of the iterator, not of the contain= er.=20
Second, you cannot have a link back to the container, period. (3) is si= mply=20
unachievable. Just think of this, what should this be

=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0std::iterator_traits<= ;char *>::container

choose:
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0std::vector<char>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0std::string
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0std::basic_string<char, any trait, any a= llocator> really...
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0std::array<char, N&g= t;
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0QVector<char>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0QByteArray

Even better, what about iterators tha= t do not have containers? Things like iterator wrappers and mutators.
No algorithm has any right to query anything about the iterator's con= tainer. That's the whole point of iterators: to be the intermediary bet= ween the container of the data and the algorithm that acts on the data. If = there is something lacking in our iterator interfaces which algorithms genu= inely need, then that is what needs to be fixed.

--
You received this message because you are subscribed to a topic in the Goog= le Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/K= QII_ogpfxo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-prop= osals+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/6e2d= 133b-1c0a-49a9-ae2b-98d82d3a40d3%40isocpp.org.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+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/CAKDaRu%2Bv= D5_rbhJw%3DdcjYC2X4BOHVpgAjb6sM%3DuGn0QvdzmD3Q%40mail.gmail.com.
--94eb2c12542a25a35205541048b0-- .