Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #83921 > unrolled thread
| Started by | Muttley@dastardlyhq.com |
|---|---|
| First post | 2022-05-03 15:16 +0000 |
| Last post | 2022-06-01 14:40 +0200 |
| Articles | 20 on this page of 95 — 21 participants |
Back to article view | Back to comp.lang.c++
Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-03 15:16 +0000
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-03 16:39 +0100
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-03 16:12 +0000
Re: Anyone ever used vector<bool> ? Bo Persson <bo@bo-persson.se> - 2022-05-03 20:25 +0200
Re: Anyone ever used vector<bool> ? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-05-03 12:00 -0700
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-04 10:50 +0000
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-03 16:14 +0000
Re: Anyone ever used vector<bool> ? Jack Lemmon <invalid@invalid.net> - 2022-05-03 17:33 +0100
Re: Anyone ever used vector<bool> ? Manfred <noname@add.invalid> - 2022-05-03 19:13 +0200
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-04 09:13 +0000
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-04 10:45 +0000
Re: Anyone ever used vector<bool> ? Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-04 14:09 +0300
Re: Anyone ever used vector<bool> ? Frederick Virchanza Gotham <cauldwell.thomas@gmail.com> - 2022-05-04 14:39 -0700
Re: Anyone ever used vector<bool> ? red floyd <no.spam.here@its.invalid> - 2022-05-04 15:17 -0700
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-05 01:57 -0400
Re: Anyone ever used vector<bool> ? Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-05 09:12 +0300
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-05 06:17 +0000
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-05 10:49 +0100
Re: Anyone ever used vector<bool> ? Öö Tiib <ootiib@hot.ee> - 2022-05-05 04:29 -0700
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-05 12:56 +0100
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-05 21:37 +0200
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-05 21:13 +0100
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-06 10:39 +0200
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-06 11:54 +0100
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-06 14:29 +0200
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-06 17:05 +0100
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-06 10:22 -0700
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-06 22:18 +0200
Re: Anyone ever used vector<bool> ? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-06 13:51 -0700
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-07 08:41 +0000
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-07 12:33 +0200
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-07 16:12 +0000
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-07 09:37 -0700
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-09 09:02 +0000
Re: Anyone ever used vector<bool> ? Bo Persson <bo@bo-persson.se> - 2022-05-09 12:14 +0200
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-09 15:36 +0000
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-09 11:56 -0400
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-09 16:18 +0000
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-09 09:38 -0700
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-10 15:55 +0000
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-10 13:28 -0400
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-10 10:16 -0400
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-10 18:40 +0200
Re: Anyone ever used vector<bool> ? Manfred <noname@add.invalid> - 2022-05-10 19:50 +0200
Re: Anyone ever used vector<bool> ? Öö Tiib <ootiib@hot.ee> - 2022-05-12 05:44 -0700
Re: Anyone ever used vector<bool> ? Manfred <noname@add.invalid> - 2022-05-12 17:24 +0200
Re: Anyone ever used vector<bool> ? Öö Tiib <ootiib@hot.ee> - 2022-05-12 20:11 -0700
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-12 12:53 -0400
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-12 22:53 -0400
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-13 18:34 +0200
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-13 23:46 -0400
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-14 11:43 +0200
Re: Anyone ever used vector<bool> ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-15 07:48 -0700
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-16 03:30 +0200
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-15 22:57 -0400
Re: Anyone ever used vector<bool> ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-17 05:30 -0700
Re: Anyone ever used vector<bool> ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-17 05:19 -0700
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-16 05:46 +0000
Re: Anyone ever used vector<bool> ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-17 05:37 -0700
Re: Anyone ever used vector<bool> ? wij <wyniijj2@gmail.com> - 2022-05-12 08:05 -0700
Re: Anyone ever used vector<bool> ? scott@slp53.sl.home (Scott Lurndal) - 2022-05-09 17:20 +0000
Re: Anyone ever used vector<bool> ? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-09 12:05 -0700
Re: Anyone ever used vector<bool> ? Bo Persson <bo@bo-persson.se> - 2022-05-09 21:57 +0200
Re: Anyone ever used vector<bool> ? wij <wyniijj2@gmail.com> - 2022-05-09 13:56 -0700
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-09 08:33 -0700
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-09 11:56 -0400
Re: Anyone ever used vector<bool> ? Manfred <noname@add.invalid> - 2022-05-09 18:13 +0200
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-10 10:14 -0400
Re: Anyone ever used vector<bool> ? scott@slp53.sl.home (Scott Lurndal) - 2022-05-10 14:31 +0000
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-07 18:38 +0200
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-07 18:28 -0400
Re: Anyone ever used vector<bool> ? Manfred <noname@add.invalid> - 2022-05-08 18:37 +0200
Re: Anyone ever used vector<bool> ? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-08 11:50 -0700
Re: Anyone ever used vector<bool> ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2022-05-08 18:18 -0400
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-07 09:45 -0700
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-07 19:12 +0200
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-07 20:36 -0700
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-08 08:26 +0200
Re: Anyone ever used vector<bool> ? scott@slp53.sl.home (Scott Lurndal) - 2022-05-06 13:55 +0000
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-06 06:35 +0000
Re: Anyone ever used vector<bool> ? Ben <ben.usenet@bsb.me.uk> - 2022-05-06 11:29 +0100
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-09 04:58 +0000
Re: Anyone ever used vector<bool> ? Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-08 22:30 -0700
Re: Anyone ever used vector<bool> ? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-03 14:41 -0700
Re: Anyone ever used vector<bool> ? Andrea Venturoli <ml.diespammer@netfence.it> - 2022-05-04 08:20 +0200
Re: Anyone ever used vector<bool> ? wij wij <wyniijj2@gmail.com> - 2022-05-04 03:21 -0700
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-04 10:52 +0000
Re: Anyone ever used vector<bool> ? Juha Nieminen <nospam@thanks.invalid> - 2022-05-04 10:47 +0000
Re: Anyone ever used vector<bool> ? Muttley@dastardlyhq.com - 2022-05-04 10:53 +0000
Re: Anyone ever used vector<bool> ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-06-01 05:46 +0200
Re: Anyone ever used vector<bool> ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-06-01 07:31 +0200
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-06-01 14:20 +0200
Re: Anyone ever used vector<bool> ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-06-01 14:23 +0200
Re: Anyone ever used vector<bool> ? "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-06-01 14:26 +0200
Re: Anyone ever used vector<bool> ? Bonita Montero <Bonita.Montero@gmail.com> - 2022-06-01 14:40 +0200
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-05 21:37 +0200 |
| Message-ID | <t5192j$kud$1@dont-email.me> |
| In reply to | #83955 |
On 5 May 2022 13:56, Ben wrote: > Öö Tiib <ootiib@hot.ee> writes: > >> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote: >>> Juha Nieminen <nos...@thanks.invalid> writes: >>> >>>> Paavo Helde <ees...@osa.pri.ee> wrote: >>>>> I have hard time finding any use case at all for std::list. >>>> >>>> When I was working at the university here I once had to implement >>>> (a rather complicated and advanced) algorithm (which had something to >>>> do with graph manipulation) which required a doubly-linked list. No other >>>> data container would have done the job because the speed of the algorithm >>>> relied on the ability to splice linked lists (and sections of them). >>>> >>>> That being said, std::list couldn't be used for this, especially now >>>> that std::list::splice() is not an O(1) operation (which would pretty >>>> much defeat the purpose). >>> >>> It's O(1) in C++11, 14 and 20 (at least in the public drafts). >> >> It has 6 overloads. Most are O(1) but one case where we transfer iterator >> range from other list to this list is linear in length of said range. > > Obviously, but that's surely not what the OP was talking about. That > one could never have been, and will never be O(1). With the choice of potentially O(n) `.size()`, instead of the silly C++11 decision, all splicing overloads could be O(1) and `std::list` could have been useful for something. Since the word "now" was used, that was surely what was being mentioned. Obviously. ;-) - Alf
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-05 21:13 +0100 |
| Message-ID | <8735hnohzi.fsf@bsb.me.uk> |
| In reply to | #83957 |
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > On 5 May 2022 13:56, Ben wrote: >> Öö Tiib <ootiib@hot.ee> writes: >> >>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote: >>>> Juha Nieminen <nos...@thanks.invalid> writes: >>>> >>>>> Paavo Helde <ees...@osa.pri.ee> wrote: >>>>>> I have hard time finding any use case at all for std::list. >>>>> >>>>> When I was working at the university here I once had to implement >>>>> (a rather complicated and advanced) algorithm (which had something to >>>>> do with graph manipulation) which required a doubly-linked list. No other >>>>> data container would have done the job because the speed of the algorithm >>>>> relied on the ability to splice linked lists (and sections of them). >>>>> >>>>> That being said, std::list couldn't be used for this, especially now >>>>> that std::list::splice() is not an O(1) operation (which would pretty >>>>> much defeat the purpose). >>>> >>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts). >>> >>> It has 6 overloads. Most are O(1) but one case where we transfer iterator >>> range from other list to this list is linear in length of said range. >> Obviously, but that's surely not what the OP was talking about. That >> one could never have been, and will never be O(1). > > With the choice of potentially O(n) `.size()`, instead of the silly > C++11 decision, all splicing overloads could be O(1) and `std::list` > could have been useful for something. > > Since the word "now" was used, that was surely what was being mentioned. > > Obviously. ;-) How much of your post does the smiley apply to? I don't want to waste everyone's time... -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-06 10:39 +0200 |
| Message-ID | <t52msn$64k$1@dont-email.me> |
| In reply to | #83958 |
On 5 May 2022 22:13, Ben wrote: > "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > >> On 5 May 2022 13:56, Ben wrote: >>> Öö Tiib <ootiib@hot.ee> writes: >>> >>>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote: >>>>> Juha Nieminen <nos...@thanks.invalid> writes: >>>>> >>>>>> Paavo Helde <ees...@osa.pri.ee> wrote: >>>>>>> I have hard time finding any use case at all for std::list. >>>>>> >>>>>> When I was working at the university here I once had to implement >>>>>> (a rather complicated and advanced) algorithm (which had something to >>>>>> do with graph manipulation) which required a doubly-linked list. No other >>>>>> data container would have done the job because the speed of the algorithm >>>>>> relied on the ability to splice linked lists (and sections of them). >>>>>> >>>>>> That being said, std::list couldn't be used for this, especially now >>>>>> that std::list::splice() is not an O(1) operation (which would pretty >>>>>> much defeat the purpose). >>>>> >>>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts). >>>> >>>> It has 6 overloads. Most are O(1) but one case where we transfer iterator >>>> range from other list to this list is linear in length of said range. >>> Obviously, but that's surely not what the OP was talking about. That >>> one could never have been, and will never be O(1). >> >> With the choice of potentially O(n) `.size()`, instead of the silly >> C++11 decision, all splicing overloads could be O(1) and `std::list` >> could have been useful for something. >> >> Since the word "now" was used, that was surely what was being mentioned. >> >> Obviously. ;-) > > How much of your post does the smiley apply to? I don't want to waste > everyone's time... I guess you're unfamiliar with the history. The fight was about the guaranteed complexity of `.size()`. With O(1) complexity a splice has to count the number of spliced nice, which turns a simple O(1) link manipulation into O(n) counting. The academic idealists won, the practically oriented people lost, and `std::list` became useless. As I see it that was the turning point in the C++ standard's evolution. - Alf
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-06 11:54 +0100 |
| Message-ID | <87sfpn7wz2.fsf@bsb.me.uk> |
| In reply to | #83960 |
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > On 5 May 2022 22:13, Ben wrote: >> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: >> >>> On 5 May 2022 13:56, Ben wrote: >>>> Öö Tiib <ootiib@hot.ee> writes: >>>> >>>>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote: >>>>>> Juha Nieminen <nos...@thanks.invalid> writes: >>>>>> >>>>>>> Paavo Helde <ees...@osa.pri.ee> wrote: >>>>>>>> I have hard time finding any use case at all for std::list. >>>>>>> >>>>>>> When I was working at the university here I once had to implement >>>>>>> (a rather complicated and advanced) algorithm (which had something to >>>>>>> do with graph manipulation) which required a doubly-linked list. No other >>>>>>> data container would have done the job because the speed of the algorithm >>>>>>> relied on the ability to splice linked lists (and sections of them). >>>>>>> >>>>>>> That being said, std::list couldn't be used for this, especially now >>>>>>> that std::list::splice() is not an O(1) operation (which would pretty >>>>>>> much defeat the purpose). >>>>>> >>>>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts). >>>>> >>>>> It has 6 overloads. Most are O(1) but one case where we transfer iterator >>>>> range from other list to this list is linear in length of said range. >>>> Obviously, but that's surely not what the OP was talking about. That >>>> one could never have been, and will never be O(1). >>> >>> With the choice of potentially O(n) `.size()`, instead of the silly >>> C++11 decision, all splicing overloads could be O(1) and `std::list` >>> could have been useful for something. >>> >>> Since the word "now" was used, that was surely what was being mentioned. >>> >>> Obviously. ;-) >> How much of your post does the smiley apply to? I don't want to waste >> everyone's time... > > I guess you're unfamiliar with the history. The fight was about the > guaranteed complexity of `.size()`. With O(1) complexity a splice has > to count the number of spliced nice, which turns a simple O(1) link > manipulation into O(n) counting. I'm familiar with the trade-off in abstract (since it crops up every time one implements a list as was so common in days gone by), but I did not know there had been a fight about it in C++. > The academic idealists won, the practically oriented people lost, and > `std::list` became useless. Curious that you put it like that. There doesn't seem to be anything obviously idealistic in opting for O(1) size and linear splicing for "foreign" sub-lists. I don't recall ever wanting that form of splice, so I would consider C++'s choice quite practical (for me). What makes this the "idealists" preferred option? The engineer's perspective might be to have two list variants, one with a maintained length and one without. Did that option crop up in the fight? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-06 14:29 +0200 |
| Message-ID | <t534c8$c7b$1@dont-email.me> |
| In reply to | #83962 |
On 6 May 2022 12:54, Ben wrote:
> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:
>
>> On 5 May 2022 22:13, Ben wrote:
>>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:
>>>
>>>> On 5 May 2022 13:56, Ben wrote:
>>>>> Öö Tiib <ootiib@hot.ee> writes:
>>>>>
>>>>>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote:
>>>>>>> Juha Nieminen <nos...@thanks.invalid> writes:
>>>>>>>
>>>>>>>> Paavo Helde <ees...@osa.pri.ee> wrote:
>>>>>>>>> I have hard time finding any use case at all for std::list.
>>>>>>>>
>>>>>>>> When I was working at the university here I once had to implement
>>>>>>>> (a rather complicated and advanced) algorithm (which had something to
>>>>>>>> do with graph manipulation) which required a doubly-linked list. No other
>>>>>>>> data container would have done the job because the speed of the algorithm
>>>>>>>> relied on the ability to splice linked lists (and sections of them).
>>>>>>>>
>>>>>>>> That being said, std::list couldn't be used for this, especially now
>>>>>>>> that std::list::splice() is not an O(1) operation (which would pretty
>>>>>>>> much defeat the purpose).
>>>>>>>
>>>>>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts).
>>>>>>
>>>>>> It has 6 overloads. Most are O(1) but one case where we transfer iterator
>>>>>> range from other list to this list is linear in length of said range.
>>>>> Obviously, but that's surely not what the OP was talking about. That
>>>>> one could never have been, and will never be O(1).
>>>>
>>>> With the choice of potentially O(n) `.size()`, instead of the silly
>>>> C++11 decision, all splicing overloads could be O(1) and `std::list`
>>>> could have been useful for something.
>>>>
>>>> Since the word "now" was used, that was surely what was being mentioned.
>>>>
>>>> Obviously. ;-)
>>> How much of your post does the smiley apply to? I don't want to waste
>>> everyone's time...
>>
>> I guess you're unfamiliar with the history. The fight was about the
>> guaranteed complexity of `.size()`. With O(1) complexity a splice has
>> to count the number of spliced nice, which turns a simple O(1) link
>> manipulation into O(n) counting.
>
> I'm familiar with the trade-off in abstract (since it crops up every
> time one implements a list as was so common in days gone by), but I did
> not know there had been a fight about it in C++.
>
>> The academic idealists won, the practically oriented people lost, and
>> `std::list` became useless.
>
> Curious that you put it like that. There doesn't seem to be anything
> obviously idealistic in opting for O(1) size and linear splicing for
> "foreign" sub-lists. I don't recall ever wanting that form of splice,
> so I would consider C++'s choice quite practical (for me). What makes
> this the "idealists" preferred option?
E.g. as Howard Hinnant put it some time before C++11, in an article at
<url: https://howardhinnant.github.io/On_list_size.html>:
❝As the standard is written today, none of the containers are required
to have an O(1) size(). I believe that this should be corrected in
C++0X. [Expressing an academic ideal:] If a container has a size()
member, it should be required to have O(1) complexity. [Again expressing
an academic ideal:] If a container can not manage this, it should not
have a size() member at all. Clients can always compute
distance(begin(),end()).❞
The inline square brackets notes are my annotations.
In the article Howard makes a number of to me dubious claims and
presents a misleading feature sheet, where the reader is led to compare
number of alleged advantages for O(1) and O(n) `.size()`. I'd say that
kind of misleading argument indicates that in this matter he represented
an academic view. But possibly that reflects my personal impression of
academics (I've held an academic position but I didn't really fit in).
Likelihood argument of academic POV: Howard was the designer of
`std::unique_ptr`, and in a slightly heated discussion between us over
on SO, where I see now that I presented a needlessly complicated example
(not proud of that, but at least it was an example), he turned out to be
unaware that `unique_ptr` could exhibit undefined behavior due to
implicit conversion of `unique_ptr<Derived>` to `unique_ptr<Base>`, i.e.
that it's not as type safe in this respect as `std::shared_ptr`.
I guess the most upsetting thing about that was not his ignorance of the
issue, but that most anybody would /assume/ that the following would
either be safe, or else would not compile at all, while reality is that
it compiles and exhibits manifest UB with both MSVC 2022 and g++ 9.2:
#include <memory>
#include <utility>
using std::unique_ptr, std::make_unique,
std::move;
struct Base{ int m_answer = 42; };
struct Derived: Base{ virtual ~Derived(){}; };
auto main() -> int
{
auto p_derived = unique_ptr<Derived>( new Derived() );
#if PLEASE_FAIL
auto p_base = unique_ptr<Base>( move( p_derived ) );
(void) p_base;
#endif
(void) p_derived;
}
`std::shared_ptr` is safe for code like above because it retains the
original object pointer.
> The engineer's perspective might be to have two list variants, one with
> a maintained length and one without. Did that option crop up in the
> fight?
Sorry I don't remember, and I was not involved other than e.g. in
discussions here in clc++ and clc++m (I've never been involved, really).
But I can imagine a lot of ways to let client code decide instead of
forcing a decision. Two list variants, as you mention, is one way.
Cheers,
- Alf
[toc] | [prev] | [next] | [standalone]
| From | Ben <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-05-06 17:05 +0100 |
| Message-ID | <87bkwa8x46.fsf@bsb.me.uk> |
| In reply to | #83963 |
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > On 6 May 2022 12:54, Ben wrote: >> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: >> >>> On 5 May 2022 22:13, Ben wrote: >>>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: >>>> >>>>> On 5 May 2022 13:56, Ben wrote: >>>>>> Öö Tiib <ootiib@hot.ee> writes: >>>>>> >>>>>>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote: >>>>>>>> Juha Nieminen <nos...@thanks.invalid> writes: >>>>>>>> >>>>>>>>> Paavo Helde <ees...@osa.pri.ee> wrote: >>>>>>>>>> I have hard time finding any use case at all for std::list. >>>>>>>>> >>>>>>>>> When I was working at the university here I once had to implement >>>>>>>>> (a rather complicated and advanced) algorithm (which had something to >>>>>>>>> do with graph manipulation) which required a doubly-linked list. No other >>>>>>>>> data container would have done the job because the speed of the algorithm >>>>>>>>> relied on the ability to splice linked lists (and sections of them). >>>>>>>>> >>>>>>>>> That being said, std::list couldn't be used for this, especially now >>>>>>>>> that std::list::splice() is not an O(1) operation (which would pretty >>>>>>>>> much defeat the purpose). >>>>>>>> >>>>>>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts). >>>>>>> >>>>>>> It has 6 overloads. Most are O(1) but one case where we transfer iterator >>>>>>> range from other list to this list is linear in length of said range. >>>>>> Obviously, but that's surely not what the OP was talking about. That >>>>>> one could never have been, and will never be O(1). >>>>> >>>>> With the choice of potentially O(n) `.size()`, instead of the silly >>>>> C++11 decision, all splicing overloads could be O(1) and `std::list` >>>>> could have been useful for something. >>>>> >>>>> Since the word "now" was used, that was surely what was being mentioned. >>>>> >>>>> Obviously. ;-) >>>> How much of your post does the smiley apply to? I don't want to waste >>>> everyone's time... >>> >>> I guess you're unfamiliar with the history. The fight was about the >>> guaranteed complexity of `.size()`. With O(1) complexity a splice has >>> to count the number of spliced nice, which turns a simple O(1) link >>> manipulation into O(n) counting. >> I'm familiar with the trade-off in abstract (since it crops up every >> time one implements a list as was so common in days gone by), but I did >> not know there had been a fight about it in C++. >> >>> The academic idealists won, the practically oriented people lost, and >>> `std::list` became useless. >> Curious that you put it like that. There doesn't seem to be anything >> obviously idealistic in opting for O(1) size and linear splicing for >> "foreign" sub-lists. I don't recall ever wanting that form of splice, >> so I would consider C++'s choice quite practical (for me). What makes >> this the "idealists" preferred option? > > E.g. as Howard Hinnant put it some time before C++11, in an article at > <url: https://howardhinnant.github.io/On_list_size.html>: > > ❝As the standard is written today, none of the containers are required > to have an O(1) size(). I believe that this should be corrected in > C++0X. [Expressing an academic ideal:] If a container has a size() > member, it should be required to have O(1) complexity. [Again > expressing an academic ideal:] If a container can not manage this, it > should not have a size() member at all. Clients can always compute > distance(begin(),end()).❞ > > The inline square brackets notes are my annotations. > > In the article Howard makes a number of to me dubious claims and > presents a misleading feature sheet, where the reader is led to > compare number of alleged advantages for O(1) and O(n) `.size()`. I'd > say that kind of misleading argument indicates that in this matter he > represented an academic view. But possibly that reflects my personal > impression of academics (I've held an academic position but I didn't > really fit in). Seems odd. The paper appears to be motivated entirely by practical concerns and Howard Hinnart is not an academic. He does not even have a CS degree (that's not criticism, just a point against your idea that it espouses an academic idealist's view). But the main point is that he is proposing the exact opposite of what you cited as the academic idealist position that won the day. Have I misinterpreted something somewhere? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-06 10:22 -0700 |
| Message-ID | <t53lh5$rv8$1@dont-email.me> |
| In reply to | #83963 |
On 5/6/2022 5:29 AM, Alf P. Steinbach wrote: > On 6 May 2022 12:54, Ben wrote: >> >>> The academic idealists won, the practically oriented people lost, and >>> `std::list` became useless. >> >> Curious that you put it like that. There doesn't seem to be anything >> obviously idealistic in opting for O(1) size and linear splicing for >> "foreign" sub-lists. I don't recall ever wanting that form of splice, >> so I would consider C++'s choice quite practical (for me). What makes >> this the "idealists" preferred option? > > E.g. as Howard Hinnant put it some time before C++11, in an article at > <url: https://howardhinnant.github.io/On_list_size.html>: > > ❝As the standard is written today, none of the containers are required > to have an O(1) size(). I believe that this should be corrected in > C++0X. [Expressing an academic ideal:] If a container has a size() > member, it should be required to have O(1) complexity. [Again expressing > an academic ideal:] If a container can not manage this, it should not > have a size() member at all. Clients can always compute > distance(begin(),end()).❞ > > The inline square brackets notes are my annotations. The quoted text actually makes an extremely good and logical point. This is exactly why we have such "red flag" functions as `std::distance` and `std::advance` in standard library: as deliberately conspicuous indicators of potentially inefficient temporary/stub/niche code. If the objective were to keep `splice()` efficient, then removing inefficient `size()` from `std::list<>` entirely and forcing the user to use `std::distance` would have been an ideal solution. Beautiful idea! But alas, the committee decided that having `std::list<>` to conform to common interface is of greater value... What it really is is conformance to legacy code. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-06 22:18 +0200 |
| Message-ID | <t53vrg$fvm$1@dont-email.me> |
| In reply to | #83966 |
On 6 May 2022 19:22, Andrey Tarasevich wrote: > On 5/6/2022 5:29 AM, Alf P. Steinbach wrote: >> On 6 May 2022 12:54, Ben wrote: >>> >>>> The academic idealists won, the practically oriented people lost, and >>>> `std::list` became useless. >>> >>> Curious that you put it like that. There doesn't seem to be anything >>> obviously idealistic in opting for O(1) size and linear splicing for >>> "foreign" sub-lists. I don't recall ever wanting that form of splice, >>> so I would consider C++'s choice quite practical (for me). What makes >>> this the "idealists" preferred option? >> >> E.g. as Howard Hinnant put it some time before C++11, in an article at >> <url: https://howardhinnant.github.io/On_list_size.html>: >> >> ❝As the standard is written today, none of the containers are required >> to have an O(1) size(). I believe that this should be corrected in >> C++0X. [Expressing an academic ideal:] If a container has a size() >> member, it should be required to have O(1) complexity. [Again >> expressing an academic ideal:] If a container can not manage this, it >> should not have a size() member at all. Clients can always compute >> distance(begin(),end()).❞ >> >> The inline square brackets notes are my annotations. > > > The quoted text actually makes an extremely good and logical point. This > is exactly why we have such "red flag" functions as `std::distance` and > `std::advance` in standard library: as deliberately conspicuous > indicators of potentially inefficient temporary/stub/niche code. > > If the objective were to keep `splice()` efficient, then removing > inefficient `size()` from `std::list<>` entirely and forcing the user to > use `std::distance` would have been an ideal solution. Beautiful idea! No no no. A `std::list` with O(1) other list splice can in most cases of ordinary usage know its size, and it can keep track of whether it knows or this time needs to count. This is a near cost free optimization (relative to overhead of e.g. creating a node, with internal dynamic allocation) with great dividends, that I believe client code can't do. I.e. requiring client code to always get O(n) size checking, instead of mainly O(1) and O(n) just in rare cases that may not even appear in one's code, is IMO not a beautiful idea. If that pessimization of mostly O(1) to always O(n) size checking is a kind of beauty, then it's an entirely academic, impractical, almost sabotage-like sense of beauty -- as I see it. > But alas, the committee decided that having `std::list<>` to conform to > common interface is of greater value... What it really is is conformance > to legacy code. Yeah I think you're right. Cheers, - Alf
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-06 13:51 -0700 |
| Message-ID | <0a29e3b3-c987-4702-a197-99dd45b50a3bn@googlegroups.com> |
| In reply to | #83968 |
On Friday, 6 May 2022 at 21:19:12 UTC+1, alf.p.s...@gmail.com wrote: > On 6 May 2022 19:22, Andrey Tarasevich wrote: > > On 5/6/2022 5:29 AM, Alf P. Steinbach wrote: > >> On 6 May 2022 12:54, Ben wrote: > >>> > >>>> The academic idealists won, the practically oriented people lost, and > >>>> `std::list` became useless. > >>> > >>> Curious that you put it like that. There doesn't seem to be anything > >>> obviously idealistic in opting for O(1) size and linear splicing for > >>> "foreign" sub-lists. I don't recall ever wanting that form of splice, > >>> so I would consider C++'s choice quite practical (for me). What makes > >>> this the "idealists" preferred option? > >> > >> E.g. as Howard Hinnant put it some time before C++11, in an article at > >> <url: https://howardhinnant.github.io/On_list_size.html>: > >> > >> ❝As the standard is written today, none of the containers are required > >> to have an O(1) size(). I believe that this should be corrected in > >> C++0X. [Expressing an academic ideal:] If a container has a size() > >> member, it should be required to have O(1) complexity. [Again > >> expressing an academic ideal:] If a container can not manage this, it > >> should not have a size() member at all. Clients can always compute > >> distance(begin(),end()).❞ > >> > >> The inline square brackets notes are my annotations. > > > > > > The quoted text actually makes an extremely good and logical point. This > > is exactly why we have such "red flag" functions as `std::distance` and > > `std::advance` in standard library: as deliberately conspicuous > > indicators of potentially inefficient temporary/stub/niche code. > > > > If the objective were to keep `splice()` efficient, then removing > > inefficient `size()` from `std::list<>` entirely and forcing the user to > > use `std::distance` would have been an ideal solution. Beautiful idea! > No no no. A `std::list` with O(1) other list splice can in most cases of > ordinary usage know its size, and it can keep track of whether it knows > or this time needs to count. This is a near cost free optimization > (relative to overhead of e.g. creating a node, with internal dynamic > allocation) with great dividends, that I believe client code can't do. > Often when we splice a list, we will know the size of the portion to be spliced, because we have previously traversed it. You could provide an O(1) splice that takes the size as a parameter. But if you go down that route, the library becomes steadily more complicated, difficult to learn, and bug prone (because you can't enforce that the size passed is the actual size of the splice, leading to bugs in later processing).
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-07 08:41 +0000 |
| Message-ID | <t55bbv$1vbf$1@gioia.aioe.org> |
| In reply to | #83968 |
On Fri, 6 May 2022 22:18:52 +0200 "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >On 6 May 2022 19:22, Andrey Tarasevich wrote: >> If the objective were to keep `splice()` efficient, then removing >> inefficient `size()` from `std::list<>` entirely and forcing the user to >> use `std::distance` would have been an ideal solution. Beautiful idea! > >No no no. A `std::list` with O(1) other list splice can in most cases of >ordinary usage know its size, and it can keep track of whether it knows Why wouldn't it always know its size? Or are you suggesting it can occasionally insert and delete without updating its element count?
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-07 12:33 +0200 |
| Message-ID | <t55hub$f9f$1@dont-email.me> |
| In reply to | #83970 |
On 7 May 2022 10:41, Muttley@dastardlyhq.com wrote: > On Fri, 6 May 2022 22:18:52 +0200 > "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >> On 6 May 2022 19:22, Andrey Tarasevich wrote: >>> If the objective were to keep `splice()` efficient, then removing >>> inefficient `size()` from `std::list<>` entirely and forcing the user to >>> use `std::distance` would have been an ideal solution. Beautiful idea! >> >> No no no. A `std::list` with O(1) other list splice can in most cases of >> ordinary usage know its size, and it can keep track of whether it knows > > Why wouldn't it always know its size? Or are you suggesting it can occasionally > insert and delete without updating its element count? With O(1) splice it doesn't know how many nodes are inserted unless it's told, and two of the splice overload don't tell it. These are the two overloads numbered (3) in the cppreference list at <url: https://en.cppreference.com/w/cpp/container/list/splice>. One practical design for that case is, as I see it, to just mark the count as unknown, e.g. set an `optional<Size>` to empty. Then when `.size()` is called, do an O(n) count and cache that. Next call of `.size()` then has efficient O(1), and this is simple to relate to for programmers, but not so for academic who wants a clear single O(what?). One way to instead force inefficiency on the client code is ¹the C++11 design where `.size()` is required to be O(1), so that those two splice overloads have to count the nodes, every time. This is inefficient but affords a simple description in the standard. O(1) here, O(n) there. And since efficient O(1) splice was about the only advantage of `std::list` over other containers such as `std::vector`, that silly C11 decision removed the ~only advantage and made `std::list` dead meat, much like `std::valarray` which was a not ungood idea once. Cheers, - Alf Notes: ¹ In C++98 and C++03 the standard expressed an intent of O(1) `.size()` via a note, "Note A" in the table of general container requirements, but notes in ISO standard are non-normative text.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-07 16:12 +0000 |
| Message-ID | <t565q5$10ln$1@gioia.aioe.org> |
| In reply to | #83971 |
On Sat, 7 May 2022 12:33:41 +0200 "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >On 7 May 2022 10:41, Muttley@dastardlyhq.com wrote: >> On Fri, 6 May 2022 22:18:52 +0200 >> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>> On 6 May 2022 19:22, Andrey Tarasevich wrote: >>>> If the objective were to keep `splice()` efficient, then removing >>>> inefficient `size()` from `std::list<>` entirely and forcing the user to >>>> use `std::distance` would have been an ideal solution. Beautiful idea! >>> >>> No no no. A `std::list` with O(1) other list splice can in most cases of >>> ordinary usage know its size, and it can keep track of whether it knows >> >> Why wouldn't it always know its size? Or are you suggesting it can >occasionally >> insert and delete without updating its element count? > >With O(1) splice it doesn't know how many nodes are inserted unless it's >told, and two of the splice overload don't tell it. splice() is a list method, not a standalone function. Its given the list to insert into itself. It can just take its size and add it to its own size. I don't see the problem.
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-07 09:37 -0700 |
| Message-ID | <t5677q$fuu$1@dont-email.me> |
| In reply to | #83974 |
On 5/7/2022 9:12 AM, Muttley@dastardlyhq.com wrote: > On Sat, 7 May 2022 12:33:41 +0200 > "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >> On 7 May 2022 10:41, Muttley@dastardlyhq.com wrote: >>> On Fri, 6 May 2022 22:18:52 +0200 >>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>>> On 6 May 2022 19:22, Andrey Tarasevich wrote: >>>>> If the objective were to keep `splice()` efficient, then removing >>>>> inefficient `size()` from `std::list<>` entirely and forcing the user to >>>>> use `std::distance` would have been an ideal solution. Beautiful idea! >>>> >>>> No no no. A `std::list` with O(1) other list splice can in most cases of >>>> ordinary usage know its size, and it can keep track of whether it knows >>> >>> Why wouldn't it always know its size? Or are you suggesting it can >> occasionally >>> insert and delete without updating its element count? >> >> With O(1) splice it doesn't know how many nodes are inserted unless it's >> told, and two of the splice overload don't tell it. > > splice() is a list method, not a standalone function. Its given the list to > insert into itself. It can just take its size and add it to its own size. > I don't see the problem. `splice` has multiple overloaded versions. And the version being discussed here is the one that really matters: `splice` that takes a pair of iterators into another list. So, no, it is not given a list, it is given a range of iterators. It doesn't know how many list elements are linked inside that range. It doesn't know how much to "add to its own size". That's what's being discussed here. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-09 09:02 +0000 |
| Message-ID | <t5albt$2g3$1@gioia.aioe.org> |
| In reply to | #83975 |
On Sat, 7 May 2022 09:37:13 -0700 Andrey Tarasevich <andreytarasevich@hotmail.com> wrote: >On 5/7/2022 9:12 AM, Muttley@dastardlyhq.com wrote: >> On Sat, 7 May 2022 12:33:41 +0200 >> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>> On 7 May 2022 10:41, Muttley@dastardlyhq.com wrote: >>>> On Fri, 6 May 2022 22:18:52 +0200 >>>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>>>> On 6 May 2022 19:22, Andrey Tarasevich wrote: >>>>>> If the objective were to keep `splice()` efficient, then removing >>>>>> inefficient `size()` from `std::list<>` entirely and forcing the user to >>>>>> use `std::distance` would have been an ideal solution. Beautiful idea! >>>>> >>>>> No no no. A `std::list` with O(1) other list splice can in most cases of >>>>> ordinary usage know its size, and it can keep track of whether it knows >>>> >>>> Why wouldn't it always know its size? Or are you suggesting it can >>> occasionally >>>> insert and delete without updating its element count? >>> >>> With O(1) splice it doesn't know how many nodes are inserted unless it's >>> told, and two of the splice overload don't tell it. >> >> splice() is a list method, not a standalone function. Its given the list to >> insert into itself. It can just take its size and add it to its own size. >> I don't see the problem. > >`splice` has multiple overloaded versions. And the version being >discussed here is the one that really matters: `splice` that takes a >pair of iterators into another list. > >So, no, it is not given a list, it is given a range of iterators. It >doesn't know how many list elements are linked inside that range. It >doesn't know how much to "add to its own size". > >That's what's being discussed here. Last time I looked you could subtract one iterator from another and get a difference. I presume that applies to std::list though I almost never use this container.
[toc] | [prev] | [next] | [standalone]
| From | Bo Persson <bo@bo-persson.se> |
|---|---|
| Date | 2022-05-09 12:14 +0200 |
| Message-ID | <jds7siF965aU1@mid.individual.net> |
| In reply to | #83996 |
On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: > On Sat, 7 May 2022 09:37:13 -0700 > Andrey Tarasevich <andreytarasevich@hotmail.com> wrote: >> On 5/7/2022 9:12 AM, Muttley@dastardlyhq.com wrote: >>> On Sat, 7 May 2022 12:33:41 +0200 >>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>>> On 7 May 2022 10:41, Muttley@dastardlyhq.com wrote: >>>>> On Fri, 6 May 2022 22:18:52 +0200 >>>>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> wrote: >>>>>> On 6 May 2022 19:22, Andrey Tarasevich wrote: >>>>>>> If the objective were to keep `splice()` efficient, then removing >>>>>>> inefficient `size()` from `std::list<>` entirely and forcing the user to >>>>>>> use `std::distance` would have been an ideal solution. Beautiful idea! >>>>>> >>>>>> No no no. A `std::list` with O(1) other list splice can in most cases of >>>>>> ordinary usage know its size, and it can keep track of whether it knows >>>>> >>>>> Why wouldn't it always know its size? Or are you suggesting it can >>>> occasionally >>>>> insert and delete without updating its element count? >>>> >>>> With O(1) splice it doesn't know how many nodes are inserted unless it's >>>> told, and two of the splice overload don't tell it. >>> >>> splice() is a list method, not a standalone function. Its given the list to >>> insert into itself. It can just take its size and add it to its own size. >>> I don't see the problem. >> >> `splice` has multiple overloaded versions. And the version being >> discussed here is the one that really matters: `splice` that takes a >> pair of iterators into another list. >> >> So, no, it is not given a list, it is given a range of iterators. It >> doesn't know how many list elements are linked inside that range. It >> doesn't know how much to "add to its own size". >> >> That's what's being discussed here. > > Last time I looked you could subtract one iterator from another and get > a difference. I presume that applies to std::list though I almost never use > this container. > No, it does not work for std::list, as each node is allocated separately. For splice to work the elements are not required to be stored sequentially, like in a std::vector. Do you begin to see the problem now?
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-09 15:36 +0000 |
| Message-ID | <t5bced$16o3$1@gioia.aioe.org> |
| In reply to | #83997 |
On Mon, 9 May 2022 12:14:10 +0200 Bo Persson <bo@bo-persson.se> wrote: >On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: >> Last time I looked you could subtract one iterator from another and get >> a difference. I presume that applies to std::list though I almost never use >> this container. >> > >No, it does not work for std::list, as each node is allocated >separately. For splice to work the elements are not required to be >stored sequentially, like in a std::vector. > >Do you begin to see the problem now? Not really because there's obviously some way of counting them even if its inefficient. Perhaps iterate through them. Clues in the name.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-09 11:56 -0400 |
| Message-ID | <t5bdjm$v7i$2@dont-email.me> |
| In reply to | #84001 |
On 5/9/22 11:36, Muttley@dastardlyhq.com wrote: > On Mon, 9 May 2022 12:14:10 +0200 > Bo Persson <bo@bo-persson.se> wrote: >> On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: >>> Last time I looked you could subtract one iterator from another and get >>> a difference. I presume that applies to std::list though I almost >>> never use >>> this container. >>> >> >> No, it does not work for std::list, as each node is allocated >> separately. For splice to work the elements are not required to be >> stored sequentially, like in a std::vector. >> >> Do you begin to see the problem now? > > Not really because there's obviously some way of counting them even if its > inefficient. Perhaps iterate through them. Clues in the name. Yes, std::distance<> does precisely that for iterators which are not random-access iterators (23.4.2p5). For such iterators, it is an O(n) algorithm.
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-09 16:18 +0000 |
| Message-ID | <t5bes1$fgp$1@gioia.aioe.org> |
| In reply to | #84003 |
On Mon, 9 May 2022 11:56:38 -0400 James Kuyper <jameskuyper@alumni.caltech.edu> wrote: >On 5/9/22 11:36, Muttley@dastardlyhq.com wrote: >> On Mon, 9 May 2022 12:14:10 +0200 >> Bo Persson <bo@bo-persson.se> wrote: >>> On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: >>>> Last time I looked you could subtract one iterator from another and get >>>> a difference. I presume that applies to std::list though I almost >>>> never use >>>> this container. >>>> >>> >>> No, it does not work for std::list, as each node is allocated >>> separately. For splice to work the elements are not required to be >>> stored sequentially, like in a std::vector. >>> >>> Do you begin to see the problem now? >> >> Not really because there's obviously some way of counting them even if its >> inefficient. Perhaps iterate through them. Clues in the name. > >Yes, std::distance<> does precisely that for iterators which are not >random-access iterators (23.4.2p5). For such iterators, it is an O(n) >algorithm. > So why are certain people claiming a std::list won't always know the size of whats being inserted into it?
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-09 09:38 -0700 |
| Message-ID | <t5bg1j$8fj$1@dont-email.me> |
| In reply to | #84005 |
On 5/9/2022 9:18 AM, Muttley@dastardlyhq.com wrote: > On Mon, 9 May 2022 11:56:38 -0400 > James Kuyper <jameskuyper@alumni.caltech.edu> wrote: >> On 5/9/22 11:36, Muttley@dastardlyhq.com wrote: >>> On Mon, 9 May 2022 12:14:10 +0200 >>> Bo Persson <bo@bo-persson.se> wrote: >>>> On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: >>>>> Last time I looked you could subtract one iterator from another and get >>>>> a difference. I presume that applies to std::list though I almost >>>>> never use >>>>> this container. >>>>> >>>> >>>> No, it does not work for std::list, as each node is allocated >>>> separately. For splice to work the elements are not required to be >>>> stored sequentially, like in a std::vector. >>>> >>>> Do you begin to see the problem now? >>> >>> Not really because there's obviously some way of counting them even if its >>> inefficient. Perhaps iterate through them. Clues in the name. >> >> Yes, std::distance<> does precisely that for iterators which are not >> random-access iterators (23.4.2p5). For such iterators, it is an O(n) >> algorithm. >> > > So why are certain people claiming a std::list won't always know the size > of whats being inserted into it? I think it's been explained rather clearly already: spending O(n) to "know" it is prohibitively expensive. That's, again, the crux of the issue: if we don't know "the size of whats being inserted", we don't want to spend O(n) to calculate that size. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | Muttley@dastardlyhq.com |
|---|---|
| Date | 2022-05-10 15:55 +0000 |
| Message-ID | <t5e1tn$175o$1@gioia.aioe.org> |
| In reply to | #84006 |
On Mon, 9 May 2022 09:38:11 -0700 Andrey Tarasevich <andreytarasevich@hotmail.com> wrote: >On 5/9/2022 9:18 AM, Muttley@dastardlyhq.com wrote: >> On Mon, 9 May 2022 11:56:38 -0400 >> James Kuyper <jameskuyper@alumni.caltech.edu> wrote: >>> On 5/9/22 11:36, Muttley@dastardlyhq.com wrote: >>>> On Mon, 9 May 2022 12:14:10 +0200 >>>> Bo Persson <bo@bo-persson.se> wrote: >>>>> On 2022-05-09 at 11:02, Muttley@dastardlyhq.com wrote: >>>>>> Last time I looked you could subtract one iterator from another and get >>>>>> a difference. I presume that applies to std::list though I almost >>>>>> never use >>>>>> this container. >>>>>> >>>>> >>>>> No, it does not work for std::list, as each node is allocated >>>>> separately. For splice to work the elements are not required to be >>>>> stored sequentially, like in a std::vector. >>>>> >>>>> Do you begin to see the problem now? >>>> >>>> Not really because there's obviously some way of counting them even if its >>>> inefficient. Perhaps iterate through them. Clues in the name. >>> >>> Yes, std::distance<> does precisely that for iterators which are not >>> random-access iterators (23.4.2p5). For such iterators, it is an O(n) >>> algorithm. >>> >> >> So why are certain people claiming a std::list won't always know the size >> of whats being inserted into it? > >I think it's been explained rather clearly already: spending O(n) to >"know" it is prohibitively expensive. > >That's, again, the crux of the issue: if we don't know "the size of >whats being inserted", we don't want to spend O(n) to calculate that size. And then you end up with a container where size() returns an incorrect value. How is that a good thing?
[toc] | [prev] | [next] | [standalone]
Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →
Back to top | Article view | comp.lang.c++
csiph-web