220 34888 <79c51b8c-6cc2-4872-8651-9dae513d1e21@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: euloanty@live.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Thoughts on more methods towards containers in the future Date: Sat, 14 Oct 2017 05:45:29 -0700 (PDT) Lines: 264 Approved: news@gmane.org Message-ID: <79c51b8c-6cc2-4872-8651-9dae513d1e21@isocpp.org> References: <973f04da-1354-44f4-9d1f-23f04596b8dc@isocpp.org> <20171014085305.GA24512@fukushima.lysator.liu.se> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_5844_575063278.1507985129657" X-Trace: blaine.gmane.org 1507985144 28731 195.159.176.226 (14 Oct 2017 12:45:44 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 14 Oct 2017 12:45:44 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDPYX6PYRQNBB2UNRDHQKGQE6N4KBOQ@isocpp.org Sat Oct 14 14:45:38 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-vk0-f72.google.com ([209.85.213.72]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e3Loi-00056t-9r for gclcip-std-proposals@m.gmane.org; Sat, 14 Oct 2017 14:45:24 +0200 Original-Received: by mail-vk0-f72.google.com with SMTP id q190sf4267828vkd.20 for ; Sat, 14 Oct 2017 05:45:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=Hv2E9wkRb1kiNOSC13lrj4JCoI2I7VW9nt9jKv9wqcA=; b=AQE7UczZnXsrfQKP7J5AtzV5D16vweBR3eVnLA2NQU+SyznDE8Xrw1Zgpj6ImtLjev 3DMoxBn5dwwrNmxzuLi/CJjM8MK/ayp4P4yeLPEeNPgdtNf1aRLSSe9NrNeSfqUfZxJT hZ2KqMYDlWmX/jiEgsI3zn+l4vprv6x1064yW6qHio3X5llJKMYo3EmzyylJXHlPML45 r7F7o51ec+4S7qlOLw6fBgiNJpvVQKtXldoNQPWOwHG7D7oyg08zEfPF8HSczNAVBGFJ 0cQ53gJo7zWBgdYGKX2+P6Pjy1CWLxr7tKGY9IBLDtpB2v7PcqoWd8rm7jaQ5v3W+/Np n1mw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=Hv2E9wkRb1kiNOSC13lrj4JCoI2I7VW9nt9jKv9wqcA=; b=XhvZPkdmTY0Z/W0FvzN8gOWG4dorW3ROOGMNiqPOMBWLjl3BtQiM00OMWa+uwrtSm9 EaOzhNQXSH5xSlI085niACEHceTgC84U/Usbn/+1fHQTaQfRlCml2SjA6MkIRS4xQ90V sd9VgCFVmSmcmrirw+rLKNAs92TT8zz/g5YOlpOfJ90gd+BMhene3pclZkS8T2N8HTDp 9ZZUuYLx9tQc8w16nZKWyGxDR5i8hyHweYFUJZIH7QnY64xlsz8fXSBNcPfj+wFrE/zH SRGb2AYKXuCg9KxfV6b4Lh+GBq1vL/aamhgiVP/a/RQyV9KZUa+WBI+BYXOxePDrRaBX hlrQ== X-Gm-Message-State: AMCzsaVFGk9v8lSttOKgFpxICs5prt512pqLz1BHs3/7GJoGDqdFvMLZ RUGz6Lx11jQsBbcl8A20aXcN2g== X-Google-Smtp-Source: AOwi7QBozDxGbvA8l3cOvPIfbhxE19GHCpY9J+IsbvgyzmSvknXZP2Sn2ktXkIYD7hiCKUfIzKQmDg== X-Received: by 10.31.146.207 with SMTP id u198mr2184976vkd.84.1507985131638; Sat, 14 Oct 2017 05:45:31 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.176.86.69 with SMTP id z5ls2394945uaa.6.gmail; Sat, 14 Oct 2017 05:45:30 -0700 (PDT) X-Received: by 10.31.169.76 with SMTP id s73mr279228vke.14.1507985130092; Sat, 14 Oct 2017 05:45:30 -0700 (PDT) In-Reply-To: <20171014085305.GA24512@fukushima.lysator.liu.se> X-Original-Sender: euloanty@live.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:34888 Archived-At: ------=_Part_5844_575063278.1507985129657 Content-Type: multipart/alternative; boundary="----=_Part_5845_1785577693.1507985129658" ------=_Part_5845_1785577693.1507985129658 Content-Type: text/plain; charset="UTF-8" On Saturday, October 14, 2017 at 4:53:10 AM UTC-4, Magnus Fromreide wrote: > > On Fri, Oct 13, 2017 at 07:38:20PM -0700, eulo...@live.com > wrote: > > Contiguous Containers: > > > > vector: > > add non check push_back. non check resize etc. > > What does this mean, you are a bit thin on details here. > > ok. when you push_back an element into the vector, it will first check whether size()==capacity(). It is an overhead when you know what exactly the size of elements you need. For example: vector v; v.reserve(10000000); for(std::size_t i(0);I!=v.capacity();++i) v.emplace_back(i); will be slower than vector v; v.reserve(10000000); for(std::size_t i(0);I!=v.capacity();++i) v.nonchecked_emplace_back(i); This is my demo code implementation of these features https://github.com/euloanty/cqwrteur-vector/blob/master/vector.h > > deque: > > add bucket interface for deque (just like unordered_set). It would make > > deque as fast as vector > > What does this mean, you are a bit thin on details here. > Think of the implementation of std::deque like an two dimension array. std::deque::iterator it(deq.begin()); ++it; when you do ++it, it will first check whether its boundary . If you have a bucket interface, you can directly access it as a "2D array", which will eliminate the cost of check the boundary check cost of deque. For example: for(const auto &ele : deq) do_something(ele); would be slower than for(std::size_t i(0);I!=deq.bucket_size();++i) for(auto it(deq.cbegin(i));it!=deq.cend(I);++it) do_something(ele); since it eliminates the cost of boundry check for deque. It also gives the opportunity for std::deque to pass through C interface for part of its elements. > > list: > > remove .size() and make splice O(1) > > You are basically saying that the C++11 change to make size() O(1) was the > wrong decision and that list::size should have been removed instead? > > Yes. This .size() makes std::list useless in many situations. Even std::forward_list does not have a .size(). > I think this is a non-starter due to all uses of list::size that are out > there. > > > Associative containers: > > > > add a iterator category (log_complexity_access_iterator). > > Add +=,+,-=,-,[] > operations for (set,map,multiset,multimap) iterators. > > What does this buy you that std::advance doesn't? Notational convenience? > No. std::advance is still linear time complexity. The data structure like set, map should be implemented as a rank RB tree which allow users to find the nth element at the O(logn) time. The best way to do this is to implement the iterators of set/map as log complexity "random access" iterator. Like std::list, .size() for set&& map is also abundant information. Why not just make it actually useful? Especially after C++11, we have unordered associative containers, std::set, std::map are becoming less important in many situations. It would be great that it has more operations to compete with unordered containers. How do you check if iterator A is less than iterator B when all that you > have access to are the A and B iterators - you do specifically not have > access to the end iterator. > > That is easy if your RB tree is a ranked tree. You add an integer "rank" for every nodes of RB tree, that would give you the opportunity to know whether A > What are your thoughts? > > In the future, could you please put each proposal in it's own thread as > that > helps keeping the discussion more focused. > > /MF > It is not a proposal. I just say something useful for the future. -- 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/79c51b8c-6cc2-4872-8651-9dae513d1e21%40isocpp.org. ------=_Part_5845_1785577693.1507985129658 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Saturday, October 14, 2017 at 4:53:10 AM UTC-4, Magnus = Fromreide wrote:
On Fri, Oct 13= , 2017 at 07:38:20PM -0700, eulo...@live.com wrote:
> Contiguous Containers:
>=20
> vector:
> add non check push_back. non check resize etc.

What does this mean, you are a bit thin on details here.

ok. when you push_back an element into the vector, it= will first check whether size()=3D=3Dcapacity(). It is an overhead when yo= u know what exactly the size of elements you need.

For example:

vector<std::size_t> v;
v.reserve(10000000);
for(std::size_t i(0);I!=3Dv.capacity(= );++i)
=C2=A0 =C2=A0=C2=A0 v.emplace_back(i);

will be slower than

vector<std::size= _t> v;
v.reserve(10000000);
for(std::= size_t i(0);I!=3Dv.capacity();++i)
=C2=A0 =C2=A0=C2=A0 v.noncheck= ed_emplace_back(i);

This is my= demo code implementation of these features
https://github.com/eu= loanty/cqwrteur-vector/blob/master/vector.h


=C2=A0
> dequ= e:
> add bucket interface for deque (just like unordered_set). It would= make=20
> deque as fast as vector

What does this mean, you are a bit thin on details here.

Think of the implementation of std::de= que like an two dimension array.=C2=A0

std::deque&= lt;int>::iterator it(deq.begin());

++it;
<= div>
when you do ++it, it will first check whether its bounda= ry .

If you have a bucket interface, you can direc= tly access it as a "2D array", which will eliminate the cost of c= heck the boundary check cost of deque.

For example= :

for(const auto &ele : deq)
=C2=A0= =C2=A0 do_something(ele);

would be slower than

for(std::size_t i(0);I!=3Ddeq.bucket_size();++i)= =C2=A0
=C2=A0=C2=A0 for(auto it(deq.cbegin(i));it!=3Ddeq.ce= nd(I);++it)
=C2=A0 =C2=A0 =C2=A0 do_something(ele);
sin= ce it eliminates the cost of boundry check for deque.

<= div>It also gives the opportunity for std::deque to pass through C interfac= e for part of its elements.
> list:
> remove .size() and make splice O(1)

You are basically saying that the C++11 change to make size() O(1) was = the
wrong decision and that list::size should have been removed instead?

Yes. This .size() makes std::list useless in many sit= uations. Even std::forward_list does not have a .size().
=C2=A0
I think this is a non-star= ter due to all uses of list::size that are out
there.

> Associative containers:
>=20
> add a iterator category (log_complexity_access_iterator).
> Add +=3D,+,-=3D,-,[] > operations for (set,map,multiset,multima= p) iterators.

What does this buy you that std::advance doesn't? Notational conven= ience?=C2=A0
=C2=A0

No. std::= advance is still linear time complexity. The data structure like set, map s= hould be implemented as a rank RB tree which allow users to find the nth el= ement at the O(logn) time. The best way to do this is to implement the iter= ators of set/map as log complexity "random access" iterator. Like= std::list, .size() for set&& map is also abundant information. Why= not just make it actually useful?

Especially afte= r C++11, we have unordered associative containers, std::set, std::map are b= ecoming less important in many situations. It would be great that it has mo= re operations to compete with unordered containers.

How do you check if iterator A is= less than iterator B when all that you
have access to are the A and B iterators - you do specifically not have
access to the end iterator.


That is easy if your RB tree is a rank= ed tree. You add an integer "rank" for every nodes of RB tree, th= at would give you the opportunity to know whether A<B in the log(n) time= complexity.
=C2=A0
> What are your thoughts?

In the future, could you please put each proposal in it's own threa= d as that
helps keeping the discussion more focused.

/MF

It is not a proposal. I just say somet= hing useful for the future.
=C2=A0

--
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/79c51b8c-6cc2-4872-8651-9dae513d1e21= %40isocpp.org.
------=_Part_5845_1785577693.1507985129658-- ------=_Part_5844_575063278.1507985129657-- .