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 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-10 13:28 -0400 |
| Message-ID | <t5e7bb$38v$1@dont-email.me> |
| In reply to | #84026 |
On 5/10/22 11:55, Muttley@dastardlyhq.com wrote: > 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: ... >>> 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? Two options are under discussion: size() never returns an incorrect value, it just may require O(n) operations to give you the correct value. The advantage of this over constant-time size() is that you only need to pay the O(n) cost if you actually need the size. If size() never gets called, you never pay the price. If it only gets called once for each list after a long series of splices between lists, you only pay that cost once per list rather than once per inter-list splice(). Whether or not this is an advantage depends upon the number of inter-list splices vs. the number of different lists. Some people have suggested that inter-list splices are so rare that it isn't worth worrying about - most splices are between different parts of the same list, which never changes the list size. Other people have suggested that essentially all splices are inter-list, and that the O(N) time for inter-list splicing therefore removes the only advantage that list has over the other container types. I mistrust extreme statements, and suspect that the truth lies somewhere between those two extremes. But I have no evidence to present in favor of that suspicion. The second option is that size() never returns an incorrect value, because size() is not supported at all. If you need the number of elements in the list, you call std::distance(l.begin(), l.end()). The advantage of this approach over the previous one is that people won't accidentally call size() in the incorrect expectation that it will be an O(1) operation, as it is for most other containers.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-10 10:16 -0400 |
| Message-ID | <t5ds3o$667$2@dont-email.me> |
| In reply to | #84005 |
On 5/9/22 12:18, 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? Nobody has claimed that it can't know. They are saying that it can't find out without taking O(n) operations, somewhere. There's three main options being discussed: Current standard: l.splice(position, x, first, last) takes O(N) time because it traverses the portion of the list spliced in order to update both this->size and x.size(). l.size() is O(1) Alternative 1: l.size() is not supported, since it cannot always be O(1). If you need the equivalent, do std::distance(l.begin(), l.end()), which is O(N). l.splice(position, x, first, last) is O(1) Alternative 2: l.size() is supported, but takes O(N) time. l.splice(position, x, first, last) is O(1) Note that every option involves one thing that takes O(N) operations.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-10 18:40 +0200 |
| Message-ID | <t5e4hc$msq$1@dont-email.me> |
| In reply to | #84021 |
On 10 May 2022 16:16, James Kuyper wrote: > On 5/9/22 12:18, 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? > > Nobody has claimed that it can't know. They are saying that it can't > find out without taking O(n) operations, somewhere. There's three main > options being discussed: > > Current standard: > l.splice(position, x, first, last) takes O(N) time because it traverses > the portion of the list spliced in order to update both this->size and > x.size(). > l.size() is O(1) > > Alternative 1: > l.size() is not supported, since it cannot always be O(1). If you need > the equivalent, do std::distance(l.begin(), l.end()), which is O(N). > l.splice(position, x, first, last) is O(1) > > Alternative 2: > l.size() is supported, but takes O(N) time. > l.splice(position, x, first, last) is O(1) > > Note that every option involves one thing that takes O(N) operations. The always-O(n) size alternatives are not really practical, as I see it. The IMO only reasonable alternative, let's call it alternative 0: * A number-of-values operation (could just be .size) is supported, with cached but possibly unknown size so that it's generally O(1) but O(n) first time after a don't-know-size-of splice. * Splice of unknown size sequence is O(1). * A `const` such list is safe for MT when it knows its size, which can be forced by just calling .size(); it's MT unsafe when size is unknown, i.e. in the period between an unknown size splice and a call of .size(). Without this practically useful fastish list alternative there wouldn't be much basis for a discussion. The constraint on sharing of `const` lists, that they must have stable caches (one can call .size() to force that), is unique wrt. the current standard library. However, as I mentioned else-thread it would apply also to any COW string type, which the committee also opted out of. Their choices simplified the complexity specifications and simplified the guarantees for MT safety, but I think those advantages academic. Cheers, - Alf
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2022-05-10 19:50 +0200 |
| Message-ID | <t5e8l9$gar$1@gioia.aioe.org> |
| In reply to | #84021 |
On 5/10/2022 4:16 PM, James Kuyper wrote: > On 5/9/22 12:18, 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? > > Nobody has claimed that it can't know. They are saying that it can't > find out without taking O(n) operations, somewhere. There's three main > options being discussed: > > Current standard: > l.splice(position, x, first, last) takes O(N) time because it traverses > the portion of the list spliced in order to update both this->size and > x.size(). > l.size() is O(1) > > Alternative 1: > l.size() is not supported, since it cannot always be O(1). If you need > the equivalent, do std::distance(l.begin(), l.end()), which is O(N). > l.splice(position, x, first, last) is O(1) > > Alternative 2: > l.size() is supported, but takes O(N) time. > l.splice(position, x, first, last) is O(1) > > Note that every option involves one thing that takes O(N) operations. > This last bit is true, but there is more to the story, which I think is important: we are not talking about some list implementation for a specific application - something that anyone could do for the task at hand. This discussion is about the standard library, which has different requirements than some specific program. As a standard library feature, I think that alternative 1 or 2 would be preferred to the current status, possibly alternative 1 over alternative 2. I see two reasons for this: a) Standard library code is not supposed to be modified by application programmers, so any feature that comes with it should be well consolidated, so that there is widespread agreement that alternative solutions are to be considered suboptimal. If some feature is controversial, better leave the implementation to the programmer, who is in fact the person responsible for the actual product. b) Standard library implementations should keep complexity (including design complexity) to a minimum - this is related to having well established solutions in it. Now, in the case of a list, complete ownership of the container involves two data items: the 'begin' and 'end' iterators. Adding a 'size' data member increases complexity, and, even worse, happens to duplicate information, which brings with itself obvious management hassles. I believe that the choice to duplicate information should be justified only by analysis of the specific problem domain, which is something a standard library cannot be aware of. Putting this in other words, the distinctive feature of list is O(1) deletions and insertions (including splicing), more than counting its elements. In fact I think it's fair to say that in algorithms in which a linked list is an appropriate tool the number of elements is often not even used. So, a compromise, if needed, should favor splice() over size(). And, if for some reason one needs a linked list with an O(1) size() operation, one can easily wrap a std::list in a class that caches and manages the additional size member. The other way around, i.e. getting an O(1) splice operation from a list implementation that comes with an O(1) size() operation, is just not possible.
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2022-05-12 05:44 -0700 |
| Message-ID | <423b2f62-20d0-4578-a047-a4c2b03d917fn@googlegroups.com> |
| In reply to | #84030 |
On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: > On 5/10/2022 4:16 PM, James Kuyper wrote: > > On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: > >> On Mon, 9 May 2022 11:56:38 -0400 > >> James Kuyper <james...@alumni.caltech.edu> wrote: > >>> On 5/9/22 11:36, Mut...@dastardlyhq.com wrote: > >>>> On Mon, 9 May 2022 12:14:10 +0200 > >>>> Bo Persson <b...@bo-persson.se> wrote: > >>>>> On 2022-05-09 at 11:02, Mut...@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? > > > > Nobody has claimed that it can't know. They are saying that it can't > > find out without taking O(n) operations, somewhere. There's three main > > options being discussed: > > > > Current standard: > > l.splice(position, x, first, last) takes O(N) time because it traverses > > the portion of the list spliced in order to update both this->size and > > x.size(). > > l.size() is O(1) > > > > Alternative 1: > > l.size() is not supported, since it cannot always be O(1). If you need > > the equivalent, do std::distance(l.begin(), l.end()), which is O(N). > > l.splice(position, x, first, last) is O(1) > > > > Alternative 2: > > l.size() is supported, but takes O(N) time. > > l.splice(position, x, first, last) is O(1) > > Why the third, complex, alternative is missing? It is like that inter-list sequence splice causes next call to size() to be O(N) but after that one call to size() (or clear() or empty() that returned true) it turns subsequent calls to size() back to O(1). Vast majority of operations can upkeep size being O(1). > > Note that every option involves one thing that takes O(N) operations. > > > This last bit is true, but there is more to the story, which I think is > important: we are not talking about some list implementation for a > specific application - something that anyone could do for the task at hand. > This discussion is about the standard library, which has different > requirements than some specific program. > > As a standard library feature, I think that alternative 1 or 2 would be > preferred to the current status, possibly alternative 1 over alternative 2. > I see two reasons for this: > > a) Standard library code is not supposed to be modified by application > programmers, so any feature that comes with it should be well > consolidated, so that there is widespread agreement that alternative > solutions are to be considered suboptimal. If some feature is > controversial, better leave the implementation to the programmer, who is > in fact the person responsible for the actual product. That unfortunately is not the case with standard library. It just has couple containers that are well implemented and tested but can't be exactly optimal for every case. That raises plenty of controversy. For example the std::deque chunk size, std::vector growth factor, underlying tree type of associative containers etc. Taking better fitting or configurable implementation can sometimes win noticeable gains in performance. > b) Standard library implementations should keep complexity (including > design complexity) to a minimum - this is related to having well > established solutions in it. The main problem with O(N) size() of list I have observed was that programmers called it when they were really interested in O(1) empty(). I was bored of typing to code review that they should use c.empty() not !c.size() or c.size() < 1 etc. Their brains just are wired to want to evaluate size. > Now, in the case of a list, complete ownership of the container involves > two data items: the 'begin' and 'end' iterators. > Adding a 'size' data member increases complexity, and, even worse, > happens to duplicate information, which brings with itself obvious > management hassles. I believe that the choice to duplicate information > should be justified only by analysis of the specific problem domain, > which is something a standard library cannot be aware of. > > Putting this in other words, the distinctive feature of list is O(1) > deletions and insertions (including splicing), more than counting its > elements. In fact I think it's fair to say that in algorithms in which a > linked list is an appropriate tool the number of elements is often not > even used. So, a compromise, if needed, should favor splice() over size(). > > And, if for some reason one needs a linked list with an O(1) size() > operation, one can easily wrap a std::list in a class that caches and > manages the additional size member. > The other way around, i.e. getting an O(1) splice operation from a list > implementation that comes with an O(1) size() operation, is just not > possible. There is configurable implementation of list in boost::container. I would take it ... as there are usually better things to do than to implement mundane containers.
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2022-05-12 17:24 +0200 |
| Message-ID | <t5j8qo$1d85$1@gioia.aioe.org> |
| In reply to | #84039 |
On 5/12/2022 2:44 PM, Öö Tiib wrote: > On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: >> On 5/10/2022 4:16 PM, James Kuyper wrote: >>> On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: >>>> On Mon, 9 May 2022 11:56:38 -0400 >>>> James Kuyper <james...@alumni.caltech.edu> wrote: >>>>> On 5/9/22 11:36, Mut...@dastardlyhq.com wrote: >>>>>> On Mon, 9 May 2022 12:14:10 +0200 >>>>>> Bo Persson <b...@bo-persson.se> wrote: >>>>>>> On 2022-05-09 at 11:02, Mut...@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? >>> >>> Nobody has claimed that it can't know. They are saying that it can't >>> find out without taking O(n) operations, somewhere. There's three main >>> options being discussed: >>> >>> Current standard: >>> l.splice(position, x, first, last) takes O(N) time because it traverses >>> the portion of the list spliced in order to update both this->size and >>> x.size(). >>> l.size() is O(1) >>> >>> Alternative 1: >>> l.size() is not supported, since it cannot always be O(1). If you need >>> the equivalent, do std::distance(l.begin(), l.end()), which is O(N). >>> l.splice(position, x, first, last) is O(1) >>> >>> Alternative 2: >>> l.size() is supported, but takes O(N) time. >>> l.splice(position, x, first, last) is O(1) >>> > > Why the third, complex, alternative is missing? > It is like that inter-list sequence splice causes next call to size() to be O(N) > but after that one call to size() (or clear() or empty() that returned true) it > turns subsequent calls to size() back to O(1). Vast majority of operations > can upkeep size being O(1). > That would be Alf's proposal. Not my favorite, but sure part of the picture. > >>> Note that every option involves one thing that takes O(N) operations. >>> >> This last bit is true, but there is more to the story, which I think is >> important: we are not talking about some list implementation for a >> specific application - something that anyone could do for the task at hand. >> This discussion is about the standard library, which has different >> requirements than some specific program. >> >> As a standard library feature, I think that alternative 1 or 2 would be >> preferred to the current status, possibly alternative 1 over alternative 2. >> I see two reasons for this: >> >> a) Standard library code is not supposed to be modified by application >> programmers, so any feature that comes with it should be well >> consolidated, so that there is widespread agreement that alternative >> solutions are to be considered suboptimal. If some feature is >> controversial, better leave the implementation to the programmer, who is >> in fact the person responsible for the actual product. > > That unfortunately is not the case with standard library. This does not mean it shouldn't be its goal, right? It just has couple > containers that are well implemented and tested but can't be exactly > optimal for every case. That raises plenty of controversy. For example the > std::deque chunk size, std::vector growth factor, underlying tree type of > associative containers etc. Taking better fitting or configurable > implementation can sometimes win noticeable gains in performance. > These two examples are a different matter: you can't have a std::deque without some chunk size, and you can't have a std::vector without a growth factor - i.e. these are design parameters that must be part of the implementation, one way or the other. A 'size' cached member is /not/ required for a std::list to do its job. Moreover, at least for std::vector, the standard library gives you a valid solution if the default growth factor does not suit your needs: /If/ (and I stress _if_) the default growth factor is proven to be not good for you, then this means that you have some very specific and hard requirements - you want to use .reserve() in your program. >> b) Standard library implementations should keep complexity (including >> design complexity) to a minimum - this is related to having well >> established solutions in it. > > The main problem with O(N) size() of list I have observed was that > programmers called it when they were really interested in O(1) empty(). > I was bored of typing to code review that they should use c.empty() not > !c.size() or c.size() < 1 etc. Their brains just are wired to want to evaluate > size. > As one good project manager I once worked with used to say, this falls into the category 'laziness'. The appropriate teamleader would happily 'educate' them (citing another former coworker of mine) More seriously, if the O(N) .size() function compromises the program performance, then this means that the project requires proper attention to container usage, including questioning if 'list' is the right container choice. >> Now, in the case of a list, complete ownership of the container involves >> two data items: the 'begin' and 'end' iterators. >> Adding a 'size' data member increases complexity, and, even worse, >> happens to duplicate information, which brings with itself obvious >> management hassles. I believe that the choice to duplicate information >> should be justified only by analysis of the specific problem domain, >> which is something a standard library cannot be aware of. >> >> Putting this in other words, the distinctive feature of list is O(1) >> deletions and insertions (including splicing), more than counting its >> elements. In fact I think it's fair to say that in algorithms in which a >> linked list is an appropriate tool the number of elements is often not >> even used. So, a compromise, if needed, should favor splice() over size(). >> >> And, if for some reason one needs a linked list with an O(1) size() >> operation, one can easily wrap a std::list in a class that caches and >> manages the additional size member. >> The other way around, i.e. getting an O(1) splice operation from a list >> implementation that comes with an O(1) size() operation, is just not >> possible. > > There is configurable implementation of list in boost::container. I would > take it ... as there are usually better things to do than to implement > mundane containers. I'm not a big fan of boost, but that's an option, yes. Note, however, that when I wrote 'wrapping' I didn't suggest rewriting a linked list from scratch. On the contrary, with the current state of things you need to rewrite the whole thing if you need a O(1) .splice(). That is what is really bad. Again, in the rare case that the .size() call is critical (which really needs to be proven by detailed profiling), then the project deserves extra care with handling the container.
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2022-05-12 20:11 -0700 |
| Message-ID | <a31db01b-cd0a-47b0-a6f6-0fb65720ef76n@googlegroups.com> |
| In reply to | #84041 |
On Thursday, 12 May 2022 at 18:24:26 UTC+3, Manfred wrote: > On 5/12/2022 2:44 PM, Öö Tiib wrote: > > On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: > >> On 5/10/2022 4:16 PM, James Kuyper wrote: > >>> On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: > >>>> On Mon, 9 May 2022 11:56:38 -0400 > >>>> James Kuyper <james...@alumni.caltech.edu> wrote: > >>>>> On 5/9/22 11:36, Mut...@dastardlyhq.com wrote: > >>>>>> On Mon, 9 May 2022 12:14:10 +0200 > >>>>>> Bo Persson <b...@bo-persson.se> wrote: > >>>>>>> On 2022-05-09 at 11:02, Mut...@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? > >>> > >>> Nobody has claimed that it can't know. They are saying that it can't > >>> find out without taking O(n) operations, somewhere. There's three main > >>> options being discussed: > >>> > >>> Current standard: > >>> l.splice(position, x, first, last) takes O(N) time because it traverses > >>> the portion of the list spliced in order to update both this->size and > >>> x.size(). > >>> l.size() is O(1) > >>> > >>> Alternative 1: > >>> l.size() is not supported, since it cannot always be O(1). If you need > >>> the equivalent, do std::distance(l.begin(), l.end()), which is O(N). > >>> l.splice(position, x, first, last) is O(1) > >>> > >>> Alternative 2: > >>> l.size() is supported, but takes O(N) time. > >>> l.splice(position, x, first, last) is O(1) > >>> > > > > Why the third, complex, alternative is missing? > > It is like that inter-list sequence splice causes next call to size() to be O(N) > > but after that one call to size() (or clear() or empty() that returned true) it > > turns subsequent calls to size() back to O(1). Vast majority of operations > > can upkeep size being O(1). > > > That would be Alf's proposal. Not my favorite, but sure part of the picture. > > > >>> Note that every option involves one thing that takes O(N) operations. > >>> > >> This last bit is true, but there is more to the story, which I think is > >> important: we are not talking about some list implementation for a > >> specific application - something that anyone could do for the task at hand. > >> This discussion is about the standard library, which has different > >> requirements than some specific program. > >> > >> As a standard library feature, I think that alternative 1 or 2 would be > >> preferred to the current status, possibly alternative 1 over alternative 2. > >> I see two reasons for this: > >> > >> a) Standard library code is not supposed to be modified by application > >> programmers, so any feature that comes with it should be well > >> consolidated, so that there is widespread agreement that alternative > >> solutions are to be considered suboptimal. If some feature is > >> controversial, better leave the implementation to the programmer, who is > >> in fact the person responsible for the actual product. > > > > That unfortunately is not the case with standard library. > > This does not mean it shouldn't be its goal, right? It is impossible goal to have generics that are optimal. Point of generics is to perform good enough, and reliably, not optimally. > It just has couple > > containers that are well implemented and tested but can't be exactly > > optimal for every case. That raises plenty of controversy. For example the > > std::deque chunk size, std::vector growth factor, underlying tree type of > > associative containers etc. Taking better fitting or configurable > > implementation can sometimes win noticeable gains in performance. > > > These two examples are a different matter: you can't have a std::deque > without some chunk size, and you can't have a std::vector without a > growth factor - i.e. these are design parameters that must be part of > the implementation, one way or the other. > > A 'size' cached member is /not/ required for a std::list to do its job. > Moreover, at least for std::vector, the standard library gives you a > valid solution if the default growth factor does not suit your needs: > /If/ (and I stress _if_) the default growth factor is proven to be not > good for you, then this means that you have some very specific and hard > requirements - you want to use .reserve() in your program. These were three random examples that can matter to performance followed with "etc." > >> b) Standard library implementations should keep complexity (including > >> design complexity) to a minimum - this is related to having well > >> established solutions in it. > > > > The main problem with O(N) size() of list I have observed was that > > programmers called it when they were really interested in O(1) empty(). > > I was bored of typing to code review that they should use c.empty() not > > !c.size() or c.size() < 1 etc. Their brains just are wired to want to evaluate > > size. > > > As one good project manager I once worked with used to say, this falls > into the category 'laziness'. The appropriate teamleader would happily > 'educate' them (citing another former coworker of mine) > > More seriously, if the O(N) .size() function compromises the program > performance, then this means that the project requires proper attention > to container usage, including questioning if 'list' is the right > container choice. I did not profile if it mattered. It was just code review opinion that usage of size() was pessimal. > >> Now, in the case of a list, complete ownership of the container involves > >> two data items: the 'begin' and 'end' iterators. > >> Adding a 'size' data member increases complexity, and, even worse, > >> happens to duplicate information, which brings with itself obvious > >> management hassles. I believe that the choice to duplicate information > >> should be justified only by analysis of the specific problem domain, > >> which is something a standard library cannot be aware of. > >> > >> Putting this in other words, the distinctive feature of list is O(1) > >> deletions and insertions (including splicing), more than counting its > >> elements. In fact I think it's fair to say that in algorithms in which a > >> linked list is an appropriate tool the numiber of elements is often not > >> even used. So, a compromise, if needed, should favor splice() over size(). > >> > >> And, if for some reason one needs a linked list with an O(1) size() > >> operation, one can easily wrap a std::list in a class that caches and > >> manages the additional size member. > >> The other way around, i.e. getting an O(1) splice operation from a list > >> implementation that comes with an O(1) size() operation, is just not > >> possible. > > > > There is configurable implementation of list in boost::container. I would > > take it ... as there are usually better things to do than to implement > > mundane containers. > > I'm not a big fan of boost, but that's an option, yes. > Note, however, that when I wrote 'wrapping' I didn't suggest rewriting a > linked list from scratch. On the contrary, with the current state of > things you need to rewrite the whole thing if you need a O(1) .splice(). > That is what is really bad. > > Again, in the rare case that the .size() call is critical (which really > needs to be proven by detailed profiling), then the project deserves > extra care with handling the container. In my experience when it is worth to consider alternatives then boost has more useful things than folly or abseil.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-12 12:53 -0400 |
| Message-ID | <t5je20$aac$1@dont-email.me> |
| In reply to | #84039 |
On 5/12/2022 2:44 PM, Öö Tiib wrote: > On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: >> On 5/10/2022 4:16 PM, James Kuyper wrote: >>> On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: ... >>>> So why are certain people claiming a std::list won't always know the size >>>> of whats being inserted into it? >>> >>> Nobody has claimed that it can't know. They are saying that it can't >>> find out without taking O(n) operations, somewhere. There's three main >>> options being discussed: >>> >>> Current standard: >>> l.splice(position, x, first, last) takes O(N) time because it traverses >>> the portion of the list spliced in order to update both this->size and >>> x.size(). >>> l.size() is O(1) >>> >>> Alternative 1: >>> l.size() is not supported, since it cannot always be O(1). If you need >>> the equivalent, do std::distance(l.begin(), l.end()), which is O(N). >>> l.splice(position, x, first, last) is O(1) >>> >>> Alternative 2: >>> l.size() is supported, but takes O(N) time. >>> l.splice(position, x, first, last) is O(1) >>> > > Why the third, complex, alternative is missing? > It is like that inter-list sequence splice causes next call to size() to be O(N) > but after that one call to size() (or clear() or empty() that returned true) it > turns subsequent calls to size() back to O(1). Vast majority of operations > can upkeep size being O(1). That's covered by the current standard. Just because the standard allows size() to be O(N) doesn't meant that it's required to always involve O(N) operations.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-12 22:53 -0400 |
| Message-ID | <t5kh7g$i7n$2@dont-email.me> |
| In reply to | #84039 |
On 5/12/2022 2:44 PM, Öö Tiib wrote: > On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: >> On 5/10/2022 4:16 PM, James Kuyper wrote: >>> On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: ... >>>> So why are certain people claiming a std::list won't always know >>>> the size >>>> of whats being inserted into it? >>> >>> Nobody has claimed that it can't know. They are saying that it can't >>> find out without taking O(n) operations, somewhere. There's three main >>> options being discussed: >>> >>> Current standard: >>> l.splice(position, x, first, last) takes O(N) time because it traverses >>> the portion of the list spliced in order to update both this->size and >>> x.size(). >>> l.size() is O(1) >>> >>> Alternative 1: >>> l.size() is not supported, since it cannot always be O(1). If you need >>> the equivalent, do std::distance(l.begin(), l.end()), which is O(N). >>> l.splice(position, x, first, last) is O(1) >>> >>> Alternative 2: >>> l.size() is supported, but takes O(N) time. >>> l.splice(position, x, first, last) is O(1) >>> > > Why the third, complex, alternative is missing? > It is like that inter-list sequence splice causes next call to size() > to be O(N) > but after that one call to size() (or clear() or empty() that returned > true) it > turns subsequent calls to size() back to O(1). Vast majority of operations > can upkeep size being O(1). [Correction to my previous post, which I've cancelled - but cancellation requests are usually ignored] That's covered by the second option. Just because the specification allows size() to be O(N) doesn't meant that it's required to always involve O(N) operations.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-13 18:34 +0200 |
| Message-ID | <t5m1a7$nfc$1@dont-email.me> |
| In reply to | #84062 |
On 13 May 2022 04:53, James Kuyper wrote: > On 5/12/2022 2:44 PM, Öö Tiib wrote: >> On Tuesday, 10 May 2022 at 20:50:56 UTC+3, Manfred wrote: >>> On 5/10/2022 4:16 PM, James Kuyper wrote: >>>> On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: > ... >>>>> So why are certain people claiming a std::list won't always know >>>>> the size >>>>> of whats being inserted into it? >>>> >>>> Nobody has claimed that it can't know. They are saying that it can't >>>> find out without taking O(n) operations, somewhere. There's three main >>>> options being discussed: >>>> >>>> Current standard: >>>> l.splice(position, x, first, last) takes O(N) time because it traverses >>>> the portion of the list spliced in order to update both this->size and >>>> x.size(). >>>> l.size() is O(1) >>>> >>>> Alternative 1: >>>> l.size() is not supported, since it cannot always be O(1). If you need >>>> the equivalent, do std::distance(l.begin(), l.end()), which is O(N). >>>> l.splice(position, x, first, last) is O(1) >>>> >>>> Alternative 2: >>>> l.size() is supported, but takes O(N) time. >>>> l.splice(position, x, first, last) is O(1) >>>> >> >> Why the third, complex, alternative is missing? >> It is like that inter-list sequence splice causes next call to size() >> to be O(N) >> but after that one call to size() (or clear() or empty() that returned >> true) it >> turns subsequent calls to size() back to O(1). Vast majority of operations >> can upkeep size being O(1). > > [Correction to my previous post, which I've cancelled - but cancellation > requests are usually ignored] > That's covered by the second option. Just because the specification allows > size() to be O(N) doesn't meant that it's required to always involve > O(N) operations. > By that logic it can be described as O(n^2 ). And it's within the formal definition of big O notation. However, using it that way would be very misleading so it's not done; there is an understanding that the big O communicates something useful to know, whereas the way you used it it communicated a falsehood. - Alf
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-13 23:46 -0400 |
| Message-ID | <t5n8mv$q1m$1@dont-email.me> |
| In reply to | #84085 |
On 5/13/22 12:34, Alf P. Steinbach wrote: > On 13 May 2022 04:53, James Kuyper wrote: ... >> [Correction to my previous post, which I've cancelled - but cancellation >> requests are usually ignored] >> That's covered by the second option. Just because the specification >> allows >> size() to be O(N) doesn't meant that it's required to always involve >> O(N) operations. >> > > By that logic it can be described as O(n^2 ). You misunderstand. This isn't a description. > And it's within the formal definition of big O notation. > > However, using it that way would be very misleading so it's not done; > there is an understanding that the big O communicates something useful > to know, whereas the way you used it it communicated a falsehood. Since it's not a description, it can't be a false description, either. It's a specification. Standard specifications can neither be false, nor true. A given implementation either meets the specifications, or it doesn't. The specifications might be impossible to meet, but that's a different matter entirely from truth or falsity. Whenever the standard specifies the complexity of an operation, an implementation that has a lower complexity is always allowed. In particular, if the standard specifies O(N), an implementation that sometimes takes O(1) time, and sometimes takes O(N) meets that specification. An implementation that took O(N^2) time would not.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-14 11:43 +0200 |
| Message-ID | <t5ntkn$t4n$1@dont-email.me> |
| In reply to | #84090 |
On 14 May 2022 05:46, James Kuyper wrote: > On 5/13/22 12:34, Alf P. Steinbach wrote: >> On 13 May 2022 04:53, James Kuyper wrote: > ... >>> [Correction to my previous post, which I've cancelled - but cancellation >>> requests are usually ignored] >>> That's covered by the second option. Just because the specification >>> allows >>> size() to be O(N) doesn't meant that it's required to always involve >>> O(N) operations. >>> >> >> By that logic it can be described as O(n^2 ). > > You misunderstand. This isn't a description. > >> And it's within the formal definition of big O notation. >> >> However, using it that way would be very misleading so it's not done; >> there is an understanding that the big O communicates something useful >> to know, whereas the way you used it it communicated a falsehood. > > Since it's not a description, it can't be a false description, either. > It's a specification. Standard specifications can neither be false, nor > true. A given implementation either meets the specifications, or it > doesn't. The specifications might be impossible to meet, but that's a > different matter entirely from truth or falsity. > > Whenever the standard specifies the complexity of an operation, an > implementation that has a lower complexity is always allowed. In > particular, if the standard specifies O(N), an implementation that > sometimes takes O(1) time, and sometimes takes O(N) meets that > specification. An implementation that took O(N^2) time would not. That's a meaningless response. I guess by design. - Alf
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-05-15 07:48 -0700 |
| Message-ID | <86sfpa3l94.fsf@linuxsc.com> |
| In reply to | #84093 |
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > On 14 May 2022 05:46, James Kuyper wrote: > >> On 5/13/22 12:34, Alf P. Steinbach wrote: >> >>> On 13 May 2022 04:53, James Kuyper wrote: >> >> ... >> >>>> [Correction to my previous post, which I've cancelled - but cancellation >>>> requests are usually ignored] >>>> That's covered by the second option. Just because the specification >>>> allows >>>> size() to be O(N) doesn't meant that it's required to always involve >>>> O(N) operations. >>> >>> By that logic it can be described as O(n^2 ). >> >> You misunderstand. This isn't a description. >> >>> And it's within the formal definition of big O notation. >>> >>> However, using it that way would be very misleading so it's not done; >>> there is an understanding that the big O communicates something useful >>> to know, whereas the way you used it it communicated a falsehood. >> >> Since it's not a description, it can't be a false description, either. >> It's a specification. Standard specifications can neither be false, nor >> true. A given implementation either meets the specifications, or it >> doesn't. The specifications might be impossible to meet, but that's a >> different matter entirely from truth or falsity. >> >> Whenever the standard specifies the complexity of an operation, an >> implementation that has a lower complexity is always allowed. In >> particular, if the standard specifies O(N), an implementation that >> sometimes takes O(1) time, and sometimes takes O(N) meets that >> specification. An implementation that took O(N^2) time would not. > > That's a meaningless response. James's response is not meaningless. It is a bit sloppy in places in how it uses big-O notation, but it is not meaningless. If you have trouble understanding what he means I suggest asking a question. > I guess by design. It's hard to see this comment as anything but a gratuitous insult. Heaven know I don't always agree with what James has to say, but he is not someone given to making statements that are deliberately meaningless, and I certainly believe he did not do so in this instance.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-16 03:30 +0200 |
| Message-ID | <t5s9ff$95m$1@dont-email.me> |
| In reply to | #84102 |
On 15 May 2022 16:48, Tim Rentsch wrote: > "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > >> On 14 May 2022 05:46, James Kuyper wrote: >> >>> On 5/13/22 12:34, Alf P. Steinbach wrote: >>> >>>> On 13 May 2022 04:53, James Kuyper wrote: >>> >>> ... >>> >>>>> [Correction to my previous post, which I've cancelled - but cancellation >>>>> requests are usually ignored] >>>>> That's covered by the second option. Just because the specification >>>>> allows >>>>> size() to be O(N) doesn't meant that it's required to always involve >>>>> O(N) operations. >>>> >>>> By that logic it can be described as O(n^2 ). >>> >>> You misunderstand. This isn't a description. >>> >>>> And it's within the formal definition of big O notation. >>>> >>>> However, using it that way would be very misleading so it's not done; >>>> there is an understanding that the big O communicates something useful >>>> to know, whereas the way you used it it communicated a falsehood. >>> >>> Since it's not a description, it can't be a false description, either. >>> It's a specification. Standard specifications can neither be false, nor >>> true. A given implementation either meets the specifications, or it >>> doesn't. The specifications might be impossible to meet, but that's a >>> different matter entirely from truth or falsity. >>> >>> Whenever the standard specifies the complexity of an operation, an >>> implementation that has a lower complexity is always allowed. In >>> particular, if the standard specifies O(N), an implementation that >>> sometimes takes O(1) time, and sometimes takes O(N) meets that >>> specification. An implementation that took O(N^2) time would not. >> >> That's a meaningless response. > > James's response is not meaningless. It is a bit sloppy in > places in how it uses big-O notation, but it is not meaningless. > If you have trouble understanding what he means I suggest asking > a question. You know that I have no trouble understanding the literal meaning. It's meaningless drivel, though. If you don't understand that, then any contribution you make here is just more noise. >> I guess by design. > > It's hard to see this comment as anything but a gratuitous > insult. Heaven know I don't always agree with what James has to > say, but he is not someone given to making statements that are > deliberately meaningless, and I certainly believe he did not > do so in this instance. Your opinion of his preference in argumentation does very little to add meaning to what he wrote; rather the opposite. The natural interpretation of James' remark is an attempt to obscure and hide that he earlier misled or failed to consider a possibility, namely that of a cached list size, by posting a stream of literally true meaningless nonsense, and for your remark, that you failed to understand both the earlier exchange and the beyond-the-end obfuscation attempt. Have fun. Cheers, - Alf
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-15 22:57 -0400 |
| Message-ID | <t5sej4$378$1@dont-email.me> |
| In reply to | #84105 |
On 5/15/22 21:30, Alf P. Steinbach wrote: > On 15 May 2022 16:48, Tim Rentsch wrote: ... >> It's hard to see this comment as anything but a gratuitous >> insult. ... It was, of course, an insult, and clearly intended as such. > ... Heaven know I don't always agree with what James has to >> say, but he is not someone given to making statements that are >> deliberately meaningless, and I certainly believe he did not >> do so in this instance. > > Your opinion of his preference in argumentation does very little to add > meaning to what he wrote; rather the opposite. > > The natural interpretation of James' remark is an attempt to obscure and > hide that he earlier misled or failed to consider a possibility, namely > that of a cached list size, ... No, that is not at all the case. I was well aware that a cached list size was one possibility being discussed. I very carefully worded my summary of the options being discussed so that it would include that possibility. I very deliberately chose not to separate it out as an option distinct from the others, because doing so would serve no purpose that was relevant to the point I was making. Possibly you failed to recognize the point that I was making, and thought that some other point should have been made. My point was that, no matter how the class was defined, in order to determine the number of elements after a splice from a foreign list, O(N) operations must occur somewhere; the discussion among the other participants in this discussion has only been about where and when that cost should be incurred, and not, as Muttley claimed, about whether on not it was possible to determine the size. Resolving that confusion on Muttley's part was the primary purpose of my message. If you thought it had some other purpose, that might have been the reason you found it so upsetting.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-05-17 05:30 -0700 |
| Message-ID | <86fsl82vey.fsf@linuxsc.com> |
| In reply to | #84106 |
James Kuyper <jameskuyper@alumni.caltech.edu> writes: > On 5/15/22 21:30, Alf P. Steinbach wrote: > >> On 15 May 2022 16:48, Tim Rentsch wrote: > > ... > >>> It's hard to see this comment as anything but a gratuitous >>> insult. ... > > It was, of course, an insult, and clearly intended as such. There's an important difference between what I said and saying Alf's (now missing) statement is an insult. I don't doubt that you feel insulted, but I still wouldn't say Alf's statement is an insult.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-05-17 05:19 -0700 |
| Message-ID | <86k0ak2vx4.fsf@linuxsc.com> |
| In reply to | #84105 |
"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > On 15 May 2022 16:48, Tim Rentsch wrote: > >> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: >> >>> On 14 May 2022 05:46, James Kuyper wrote: >>> >>>> On 5/13/22 12:34, Alf P. Steinbach wrote: >>>> >>>>> On 13 May 2022 04:53, James Kuyper wrote: >>>> >>>> ... >>>> >>>>>> That's covered by the second option. Just because the >>>>>> specification allows size() to be O(N) doesn't meant that >>>>>> it's required to always involve O(N) operations. >>>>> >>>>> By that logic it can be described as O(n^2 ). >>>> >>>> You misunderstand. This isn't a description. >>>> >>>>> And it's within the formal definition of big O notation. >>>>> >>>>> However, using it that way would be very misleading so it's not >>>>> done; there is an understanding that the big O communicates >>>>> something useful to know, whereas the way you used it it >>>>> communicated a falsehood. >>>> >>>> Since it's not a description, it can't be a false description, >>>> either. It's a specification. Standard specifications can >>>> neither be false, nor true. A given implementation either meets >>>> the specifications, or it doesn't. The specifications might be >>>> impossible to meet, but that's a different matter entirely from >>>> truth or falsity. >>>> >>>> Whenever the standard specifies the complexity of an operation, >>>> an implementation that has a lower complexity is always allowed. >>>> In particular, if the standard specifies O(N), an implementation >>>> that sometimes takes O(1) time, and sometimes takes O(N) meets >>>> that specification. An implementation that took O(N^2) time >>>> would not. >>> >>> That's a meaningless response. >> >> James's response is not meaningless. It is a bit sloppy in >> places in how it uses big-O notation, but it is not meaningless. >> If you have trouble understanding what he means I suggest asking >> a question. > > You know that I have no trouble understanding the literal meaning. I don't know what kinds of statements you might have trouble understanding. My comment was only about James's statements, not about whether you understood them. > It's meaningless drivel, though. > > If you don't understand that, then any contribution you make here > is just more noise. Since I don't think his statements are meaningless I wouldn't call them meaningless drivel. Apparently you mean something different by the phrase than how I would normally read it. >>> I guess by design. >> >> It's hard to see this comment as anything but a gratuitous >> insult. Heaven know I don't always agree with what James has to >> say, but he is not someone given to making statements that are >> deliberately meaningless, and I certainly believe he did not >> do so in this instance. > > Your opinion of his preference in argumentation does very little > to add meaning to what he wrote; rather the opposite. > > The natural interpretation of James' remark is an attempt to > obscure and hide that he earlier misled or failed to consider a > possibility, namely that of a cached list size, by posting a > stream of literally true meaningless nonsense, and for your > remark, that you failed to understand both the earlier exchange > and the beyond-the-end obfuscation attempt. I'm sorry you didn't find my comments more helpful.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2022-05-16 05:46 +0000 |
| Message-ID | <t5sofp$3q8$1@gioia.aioe.org> |
| In reply to | #84090 |
James Kuyper <jameskuyper@alumni.caltech.edu> wrote: > Whenever the standard specifies the complexity of an operation, an > implementation that has a lower complexity is always allowed. In > particular, if the standard specifies O(N), an implementation that > sometimes takes O(1) time, and sometimes takes O(N) meets that > specification. An implementation that took O(N^2) time would not. One has to be quite careful with the wording used, though. "at most O(n)", "on average O(n)" and "amortized O(n)" can mean quite different things. Also things like "O(n) element comparisons" can insiduously hide the allowance of doing more than O(n) other operations.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-05-17 05:37 -0700 |
| Message-ID | <86bkvw2v35.fsf@linuxsc.com> |
| In reply to | #84108 |
Juha Nieminen <nospam@thanks.invalid> writes: > James Kuyper <jameskuyper@alumni.caltech.edu> wrote: > >> Whenever the standard specifies the complexity of an operation, an >> implementation that has a lower complexity is always allowed. In >> particular, if the standard specifies O(N), an implementation that >> sometimes takes O(1) time, and sometimes takes O(N) meets that >> specification. An implementation that took O(N^2) time would not. > > One has to be quite careful with the wording used, though. > > "at most O(n)", "on average O(n)" and "amortized O(n)" can mean > quite different things. Because James is talking about what is said in the C++ standard, what "O(n)" means is the same as what is meant in the standard.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj2@gmail.com> |
|---|---|
| Date | 2022-05-12 08:05 -0700 |
| Message-ID | <2535dab3-4a4e-476f-be99-84850520511bn@googlegroups.com> |
| In reply to | #84030 |
On Wednesday, 11 May 2022 at 01:50:56 UTC+8, Manfred wrote: > On 5/10/2022 4:16 PM, James Kuyper wrote: > > On 5/9/22 12:18, Mut...@dastardlyhq.com wrote: > >> On Mon, 9 May 2022 11:56:38 -0400 > >> James Kuyper <james...@alumni.caltech.edu> wrote: > >>> On 5/9/22 11:36, Mut...@dastardlyhq.com wrote: > >>>> On Mon, 9 May 2022 12:14:10 +0200 > >>>> Bo Persson <b...@bo-persson.se> wrote: > >>>>> On 2022-05-09 at 11:02, Mut...@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? > > > > Nobody has claimed that it can't know. They are saying that it can't > > find out without taking O(n) operations, somewhere. There's three main > > options being discussed: > > > > Current standard: > > l.splice(position, x, first, last) takes O(N) time because it traverses > > the portion of the list spliced in order to update both this->size and > > x.size(). > > l.size() is O(1) > > > > Alternative 1: > > l.size() is not supported, since it cannot always be O(1). If you need > > the equivalent, do std::distance(l.begin(), l.end()), which is O(N). > > l.splice(position, x, first, last) is O(1) > > > > Alternative 2: > > l.size() is supported, but takes O(N) time. > > l.splice(position, x, first, last) is O(1) > > > > Note that every option involves one thing that takes O(N) operations. > > > This last bit is true, but there is more to the story, which I think is > important: we are not talking about some list implementation for a > specific application - something that anyone could do for the task at hand. > This discussion is about the standard library, which has different > requirements than some specific program. > > As a standard library feature, I think that alternative 1 or 2 would be > preferred to the current status, possibly alternative 1 over alternative 2. > I see two reasons for this: > > a) Standard library code is not supposed to be modified by application > programmers, so any feature that comes with it should be well > consolidated, so that there is widespread agreement that alternative > solutions are to be considered suboptimal. If some feature is > controversial, better leave the implementation to the programmer, who is > in fact the person responsible for the actual product. What kind of library is supposed to be modified by application programmers? > b) Standard library implementations should keep complexity (including > design complexity) to a minimum - this is related to having well > established solutions in it. > Now, in the case of a list, complete ownership of the container involves > two data items: the 'begin' and 'end' iterators. > Adding a 'size' data member increases complexity, and, even worse, > happens to duplicate information, which brings with itself obvious > management hassles. I believe that the choice to duplicate information > should be justified only by analysis of the specific problem domain, > which is something a standard library cannot be aware of. What library implementations should not keep complexity (including design complexity) to a minimum? > Putting this in other words, the distinctive feature of list is O(1) > deletions and insertions (including splicing), more than counting its > elements. In fact I think it's fair to say that in algorithms in which a > linked list is an appropriate tool the number of elements is often not > even used. So, a compromise, if needed, should favor splice() over size(). > > And, if for some reason one needs a linked list with an O(1) size() > operation, one can easily wrap a std::list in a class that caches and > manages the additional size member. > The other way around, i.e. getting an O(1) splice operation from a list > implementation that comes with an O(1) size() operation, is just not > possible. Informationless. My opinion: The standard library is what it is, difficult to change (unless the goal is to change/evaluate it). The member size() should be in std::list for the standard's theory to work. Otherwise the missing of size() would cause more serious/fundamental problems. (In all practical cases I know, the cost of size() is negligibly minor)
[toc] | [prev] | [next] | [standalone]
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
Back to top | Article view | comp.lang.c++
csiph-web