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 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2022-05-09 17:20 +0000 |
| Message-ID | <r3ceK.5331$lWNd.898@fx99.iad> |
| In reply to | #84001 |
Muttley@dastardlyhq.com writes: >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. > When I create linked lists (in C or C++) and I need to keep a count of the number of elements in the list, I keep a size_t in the listhead that is incremented by the insert/remove functions. I'm not sure why std::list (or perhaps a derived std::counted_list) couldn't do similar.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-09 12:05 -0700 |
| Message-ID | <834a88f3-6a91-4eba-9062-27759228f1dan@googlegroups.com> |
| In reply to | #84007 |
On Monday, 9 May 2022 at 18:20:39 UTC+1, Scott Lurndal wrote: > Mut...@dastardlyhq.com writes: > >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. > > > When I create linked lists (in C or C++) and I need to keep a > count of the number of elements in the list, I keep a size_t > in the listhead that is incremented by the insert/remove functions. > > I'm not sure why std::list (or perhaps a derived std::counted_list) > couldn't do similar. > Of course it can. In fact, since size() is constrained to be O(1) it must do. However if you insert a long section of another list, you pass the start and one past the end pointers. Because it is a linked list, there's no way of knowing how many elements are between them, other than by starting at the start and iterating through the list until you reach the one past the end. So you can had O(1) size, or O(1) splicing, but not both.
[toc] | [prev] | [next] | [standalone]
| From | Bo Persson <bo@bo-persson.se> |
|---|---|
| Date | 2022-05-09 21:57 +0200 |
| Message-ID | <jdta2uFfl0nU1@mid.individual.net> |
| In reply to | #84001 |
On 2022-05-09 at 17: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. > But counting them makes the operation O(n), which is not what we want. std::list has splice with (first, last)-patameters to move nodes from one list to another. Very fast if you only have to adjust a few pointers. Very slow if you then have to traverse the (first, last) sequence just to see how long it is. Could be *very* long. And most of the advantage of splice(first, last) over insert(first, last) is suddenly gone.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj2@gmail.com> |
|---|---|
| Date | 2022-05-09 13:56 -0700 |
| Message-ID | <d6062f02-0b60-4d28-8f6e-7466bb2c7269n@googlegroups.com> |
| In reply to | #84009 |
On Tuesday, 10 May 2022 at 03:58:39 UTC+8, Bo Persson wrote: > On 2022-05-09 at 17: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. > > > But counting them makes the operation O(n), which is not what we want. > > std::list has splice with (first, last)-patameters to move nodes from > one list to another. Very fast if you only have to adjust a few pointers. > > Very slow if you then have to traverse the (first, last) sequence just > to see how long it is. Could be *very* long. > > And most of the advantage of splice(first, last) over insert(first, > last) is suddenly gone. Because many questions in the thread looked odd to me, my guess is that they may be from people did not have actually written a List class. Is this the goal of C++ standard library? I think yes. But C++ standard library cannot be responsible for user's lack of experience of implementation. There are more from hiding the level stuff to the user. What is the point, then? C++ standard's explanation cannot be from 'implement' and expect user not to understand the 'implement'.
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-09 08:33 -0700 |
| Message-ID | <t5bc8j$kld$1@dont-email.me> |
| In reply to | #83996 |
On 5/9/2022 2:02 AM, 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. > Well, the very crux of the issue is that you can't do that [efficiently] with `std::list<>`s iterators. Subtraction is available for random-access iterators only. And `std::list<>`s iterators are bidirectional, not random-access. Even if subtraction were formally available for `std::list<>`s iterators, it'd still be a `std::distance` kind of operation. Not useful within the context of the issue in question. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-09 11:56 -0400 |
| Message-ID | <t5bdiu$v7i$1@dont-email.me> |
| In reply to | #83996 |
On 5/9/22 05:02, Muttley@dastardlyhq.com wrote: ... > Last time I looked you could subtract one iterator from another and get > a difference. ... That's true only for random-access iterators (23.3.5.6p1). The only standard container which is explicitly required to support random-access iterators is std::deque<>. A contiguous container is required to have a random access iterator (22.2.1p13). std::array<> is required to be a contiguous container. (22.3.7.1p1). std::vector<> used to be required to support a random access iterator, but that appears to have been dropped in C++ 2014. std::list<> has never been required to support random access iterators.
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2022-05-09 18:13 +0200 |
| Message-ID | <t5bej9$b5f$1@gioia.aioe.org> |
| In reply to | #84002 |
On 5/9/2022 5:56 PM, James Kuyper wrote: > On 5/9/22 05:02, Muttley@dastardlyhq.com wrote: > ... >> Last time I looked you could subtract one iterator from another and get >> a difference. ... > > That's true only for random-access iterators (23.3.5.6p1). The only > standard container which is explicitly required to support random-access > iterators is std::deque<>. > A contiguous container is required to have a random access iterator > (22.2.1p13). > std::array<> is required to be a contiguous container. (22.3.7.1p1). > std::vector<> used to be required to support a random access iterator, > but that appears to have been dropped in C++ 2014. 22.3.11.1p2: "A vector meets all of the requirements of a container and ..., and, for an element type other than bool, of a contiguous container (22.2.1)." That makes for the requirement of random access, except for vector<bool>, quite apropos for this thread.. > std::list<> has never been required to support random access iterators. >
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-10 10:14 -0400 |
| Message-ID | <t5drvp$667$1@dont-email.me> |
| In reply to | #84004 |
On 5/9/22 12:13, Manfred wrote: > On 5/9/2022 5:56 PM, James Kuyper wrote: >> On 5/9/22 05:02, Muttley@dastardlyhq.com wrote: >> ... >>> Last time I looked you could subtract one iterator from another and get >>> a difference. ... >> >> That's true only for random-access iterators (23.3.5.6p1). The only >> standard container which is explicitly required to support random-access >> iterators is std::deque<>. >> A contiguous container is required to have a random access iterator >> (22.2.1p13). >> std::array<> is required to be a contiguous container. (22.3.7.1p1). >> std::vector<> used to be required to support a random access iterator, >> but that appears to have been dropped in C++ 2014. > > 22.3.11.1p2: > "A vector meets all of the requirements of a container and ..., and, for > an element type other than bool, of a contiguous container (22.2.1)." Annoying. The Evince Document Viewer that I'm using does not find a match to "contiguous container" when there's a line break separating the two words. I thought the exclusion of std::vector seemed odd.
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2022-05-10 14:31 +0000 |
| Message-ID | <oHueK.11560$IQK.2898@fx02.iad> |
| In reply to | #84020 |
James Kuyper <jameskuyper@alumni.caltech.edu> writes: >On 5/9/22 12:13, Manfred wrote: >> On 5/9/2022 5:56 PM, James Kuyper wrote: >>> On 5/9/22 05:02, Muttley@dastardlyhq.com wrote: >>> ... >>>> Last time I looked you could subtract one iterator from another and get >>>> a difference. ... >>> >>> That's true only for random-access iterators (23.3.5.6p1). The only >>> standard container which is explicitly required to support random-access >>> iterators is std::deque<>. >>> A contiguous container is required to have a random access iterator >>> (22.2.1p13). >>> std::array<> is required to be a contiguous container. (22.3.7.1p1). >>> std::vector<> used to be required to support a random access iterator, >>> but that appears to have been dropped in C++ 2014. >> >> 22.3.11.1p2: >> "A vector meets all of the requirements of a container and ..., and, for >> an element type other than bool, of a contiguous container (22.2.1)." > >Annoying. The Evince Document Viewer that I'm using does not find a >match to "contiguous container" when there's a line break separating the >two words. I thought the exclusion of std::vector seemed odd. I've always preferred xpdf over evince. I really don't like evince.
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-07 18:38 +0200 |
| Message-ID | <t5679e$guu$1@dont-email.me> |
| In reply to | #83974 |
On 7 May 2022 18:12, 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. Dear, you're trolling.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-07 18:28 -0400 |
| Message-ID | <t56rqg$jgp$1@dont-email.me> |
| In reply to | #83974 |
On 5/7/22 12:12, Muttley@dastardlyhq.com wrote: ... > 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. "void splice(const_iterator position, list & x, const_iterator first, const_iterator last); void splice(const_iterator position, list && x, const_iterator first, const_iterator last); 11 Preconditions: [first, last) is a valid range in x. position is not an iterator in the range [first, last). 12 Effects: Inserts elements in the range [first, last) before position and removes the elements from x. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x. 13 Throws: Nothing. 14 Complexity: Constant time if addressof(x) == this; otherwise, linear time." Would you explain how to implement these particular overloads of std::list::splice() as constant-time operations in the case where addressof(x) != this, if [first,last) identifies an arbitrary sub-range of x?
[toc] | [prev] | [next] | [standalone]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2022-05-08 18:37 +0200 |
| Message-ID | <t58rji$1t64$1@gioia.aioe.org> |
| In reply to | #83979 |
On 5/8/2022 12:28 AM, James Kuyper wrote: > On 5/7/22 12:12, Muttley@dastardlyhq.com wrote: > ... >> 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. > > "void splice(const_iterator position, list & x, const_iterator first, > const_iterator last); > void splice(const_iterator position, list && x, const_iterator first, > const_iterator last); > > 11 Preconditions: [first, last) is a valid range in x. position is not > an iterator in the range [first, last). > 12 Effects: Inserts elements in the range [first, last) before position > and removes the elements from x. Pointers and references to the moved > elements of x now refer to those same elements but as members of *this. > Iterators referring to the moved elements will continue to refer to > their elements, but they now behave as iterators into *this, not into x. > 13 Throws: Nothing. > 14 Complexity: Constant time if addressof(x) == this; otherwise, linear > time." > > Would you explain how to implement these particular overloads of > std::list::splice() as constant-time operations in the case where > addressof(x) != this, if [first,last) identifies an arbitrary sub-range > of x? > This has already been answered in thread, but I'll recall it here next to your point: As long as you need a O(1) .size() method, you can't. If you allow for a O(n) .size() method (or, probably even better, you remove the .size() method entirely), then these overloads of splice, in addition to the other ones, become constant-time operations. In other words, the requirements you list here do not make for a necessary O(n) .splice() overload by themselves, but combined with the O(1) requirement for .size(), they do. After following this thread, I have to say that I share the sentiment that .size() should just not be a method of std::list. A doubly-linked list is inherently a series of elements that has no locality, i.e. it may be seen as a sparse set (or a scattered set). While it may make sense to know the /count/ of its elements (which I wouldn't consider a key feature of std::list, however), the concept of size (i.e how "big" it is) of a sparse set looks somewhat forced. It's no surprise that it ends up defeating the main purpose of std::list, which is O(1) insertions and deletions.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2022-05-08 11:50 -0700 |
| Message-ID | <2c4c8f74-88f4-47d1-98bf-42a224a579d2n@googlegroups.com> |
| In reply to | #83986 |
On Sunday, 8 May 2022 at 17:37:22 UTC+1, Manfred wrote: > On 5/8/2022 12:28 AM, James Kuyper wrote: > > On 5/7/22 12:12, Mut...@dastardlyhq.com wrote: > > ... > >> 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. > > > > "void splice(const_iterator position, list & x, const_iterator first, > > const_iterator last); > > void splice(const_iterator position, list && x, const_iterator first, > > const_iterator last); > > > > 11 Preconditions: [first, last) is a valid range in x. position is not > > an iterator in the range [first, last). > > 12 Effects: Inserts elements in the range [first, last) before position > > and removes the elements from x. Pointers and references to the moved > > elements of x now refer to those same elements but as members of *this. > > Iterators referring to the moved elements will continue to refer to > > their elements, but they now behave as iterators into *this, not into x. > > 13 Throws: Nothing. > > 14 Complexity: Constant time if addressof(x) == this; otherwise, linear > > time." > > > > Would you explain how to implement these particular overloads of > > std::list::splice() as constant-time operations in the case where > > addressof(x) != this, if [first,last) identifies an arbitrary sub-range > > of x? > > > This has already been answered in thread, but I'll recall it here next > to your point: > As long as you need a O(1) .size() method, you can't. > If you allow for a O(n) .size() method (or, probably even better, you > remove the .size() method entirely), then these overloads of splice, in > addition to the other ones, become constant-time operations. > > In other words, the requirements you list here do not make for a > necessary O(n) .splice() overload by themselves, but combined with the > O(1) requirement for .size(), they do. > > After following this thread, I have to say that I share the sentiment > that .size() should just not be a method of std::list. > > A doubly-linked list is inherently a series of elements that has no > locality, i.e. it may be seen as a sparse set (or a scattered set). > While it may make sense to know the /count/ of its elements (which I > wouldn't consider a key feature of std::list, however), the concept of > size (i.e how "big" it is) of a sparse set looks somewhat forced. > It's no surprise that it ends up defeating the main purpose of > std::list, which is O(1) insertions and deletions. > In C you use linked lists mainly because resizing arrays is a nuisance. You have to maintain the size separately, then the reallocation can fail and that has to be handled, and all the internal pointers become invalid. To create a linked list, however, you just add a "next" field to a structure. In C++, this is handled automatically by an std::vector. And setting up an std::list is as much overhead as setting up an std::vector .
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2022-05-08 18:18 -0400 |
| Message-ID | <t59fj8$qs3$1@dont-email.me> |
| In reply to | #83986 |
On 5/8/22 12:37, Manfred wrote: > On 5/8/2022 12:28 AM, James Kuyper wrote: >> On 5/7/22 12:12, Muttley@dastardlyhq.com wrote: >> ... >>> 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. >> >> "void splice(const_iterator position, list & x, const_iterator first, >> const_iterator last); >> void splice(const_iterator position, list && x, const_iterator first, >> const_iterator last); >> >> 11 Preconditions: [first, last) is a valid range in x. position is not >> an iterator in the range [first, last). >> 12 Effects: Inserts elements in the range [first, last) before position >> and removes the elements from x. Pointers and references to the moved >> elements of x now refer to those same elements but as members of *this. >> Iterators referring to the moved elements will continue to refer to >> their elements, but they now behave as iterators into *this, not into x. >> 13 Throws: Nothing. >> 14 Complexity: Constant time if addressof(x) == this; otherwise, linear >> time." >> >> Would you explain how to implement these particular overloads of >> std::list::splice() as constant-time operations in the case where >> addressof(x) != this, if [first,last) identifies an arbitrary sub-range >> of x? >> > > This has already been answered in thread, but I'll recall it here next > to your point: > As long as you need a O(1) .size() method, you can't. If I'm bothering to cite the words of the standard, you can safely assume that I'm talking about the case where all of the other requirements of the standard are also met. While O(n) size() has been mentioned elsewhere in this thread, as far as I could tell Muttley's comment was not based upon that idea, but on a misconception that the only splice() overload that could be used with a 'foreign' list is one that splices the entire other list into this one.
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-07 09:45 -0700 |
| Message-ID | <t567nn$kdf$1@dont-email.me> |
| In reply to | #83968 |
On 5/6/2022 1:18 PM, Alf P. Steinbach 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. Lazy evaluation of `size()` is a viable technique that nevertheless has its own set of issues. It is an operation that is "logically const" but not "physically const", since it has to updated its "size is known" state. In a single-threaded context it is viable, but cue in multithreading considerations and it becomes problematic. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-07 19:12 +0200 |
| Message-ID | <t569al$2hp$1@dont-email.me> |
| In reply to | #83977 |
On 7 May 2022 18:45, Andrey Tarasevich wrote: > On 5/6/2022 1:18 PM, Alf P. Steinbach 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. > > Lazy evaluation of `size()` is a viable technique that nevertheless has > its own set of issues. It is an operation that is "logically const" but > not "physically const", since it has to updated its "size is known" > state. Right, a reasonable C++11 implementation is a `mutable optional<Size>`, where `Size` is `ptrdiff_t`. > In a single-threaded context it is viable, but cue in > multithreading considerations and it becomes problematic. That as I see it erroneous conclusion appears to build on three invalid assumptions: Assumption 1. Any `const` object of a standard library type is or should be safe for multithreading. Assumption 2. It's impossible or impractical to let client code know if object is in mt-safe stable state. Assumption 3: It's impossible or impractical for client code to force an mt-safe stable state. In particular, a single call to `.size()` would suffice to bring the object to stable state so it could be shared for reading. Client code responsibility to do MT right, not `std::list` responsibility. I failed to mention similar technique earlier for forcing a counting of the transferred nodes in a splice. With lazy size count one can just transfer them to a temporary empty list first; transferring all from that intermediate list then effects a count. That trick could be made unnecessary in the rare cases where needed, by adding an option to the splice function to count -- which is about empowering client code, giving client code the choice, instead of forcing inefficiency on it. Cheers, - Alf
[toc] | [prev] | [next] | [standalone]
| From | Andrey Tarasevich <andreytarasevich@hotmail.com> |
|---|---|
| Date | 2022-05-07 20:36 -0700 |
| Message-ID | <t57ds7$26h$1@dont-email.me> |
| In reply to | #83978 |
On 5/7/2022 10:12 AM, Alf P. Steinbach wrote: > On 7 May 2022 18:45, Andrey Tarasevich wrote: >> On 5/6/2022 1:18 PM, Alf P. Steinbach 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. >> >> Lazy evaluation of `size()` is a viable technique that nevertheless >> has its own set of issues. It is an operation that is "logically >> const" but not "physically const", since it has to updated its "size >> is known" state. > > Right, a reasonable C++11 implementation is a `mutable optional<Size>`, > where `Size` is `ptrdiff_t`. > > >> In a single-threaded context it is viable, but cue in multithreading >> considerations and it becomes problematic. > > That as I see it erroneous conclusion appears to build on three invalid > assumptions: > > Assumption 1. Any `const` object of a standard library type is or should > be safe for multithreading. > Assumption 2. It's impossible or impractical to let client code know if > object is in mt-safe stable state. > Assumption 3: It's impossible or impractical for client code to force an > mt-safe stable state. > Nope. I did not make such a broad assumption as the one you presented under #1. I simply implied that `size()` should not belong to the family of container methods that can trigger a data race. -- Best regards, Andrey
[toc] | [prev] | [next] | [standalone]
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Date | 2022-05-08 08:26 +0200 |
| Message-ID | <t57nr0$otv$1@dont-email.me> |
| In reply to | #83980 |
On 8 May 2022 05:36, Andrey Tarasevich wrote: > On 5/7/2022 10:12 AM, Alf P. Steinbach wrote: >> On 7 May 2022 18:45, Andrey Tarasevich wrote: >>> On 5/6/2022 1:18 PM, Alf P. Steinbach 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. >>> >>> Lazy evaluation of `size()` is a viable technique that nevertheless >>> has its own set of issues. It is an operation that is "logically >>> const" but not "physically const", since it has to updated its "size >>> is known" state. >> >> Right, a reasonable C++11 implementation is a `mutable >> optional<Size>`, where `Size` is `ptrdiff_t`. >> >> >>> In a single-threaded context it is viable, but cue in multithreading >>> considerations and it becomes problematic. >> >> That as I see it erroneous conclusion appears to build on three >> invalid assumptions: >> >> Assumption 1. Any `const` object of a standard library type is or >> should be safe for multithreading. >> Assumption 2. It's impossible or impractical to let client code know >> if object is in mt-safe stable state. >> Assumption 3: It's impossible or impractical for client code to force >> an mt-safe stable state. >> > > Nope. I did not make such a broad assumption as the one you presented > under #1. I simply implied that `size()` should not belong to the family > of container methods that can trigger a data race. Well, as I wrote (but snipped here) /a single call to `.size()`/ brings the object to a stable state where it can be shared for reading. Plus that correct multi-threading is the responsibility of client code, not of each class that the client code uses. The "should" therefore sounds entirely idealistic. One gains a nice and tidy view of something that's only academically relevant, in the usual meaning of the phrase "that's academic", at the cost of inefficiency that to boot removes the ~only advantage of the class. That's why I called that kind of idealistic view "academic". But considering that COW strings have roughly the same little MT-safety gotcha in any access of pointer or reference to (even `const`) char item, perhaps the standard should have introduced a general convention of an idempotent ".ensure_safe_for_sharing()" method and an `.is_safe_for_sharing()` checker for asserts. For `std::list` the former would just call `.size()`, paying the outstanding counting debt if any. For a putative COW string type (C++11 removed the C++03 COW support for `std::string`, but perhaps an additional string type, not necessarily `std::string`) it would ensure single ownership of the buffer e.g. by calling `operator[]`, paying the outstanding copying debt if necessary. Cheers, - Alf
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2022-05-06 13:55 +0000 |
| Message-ID | <kN9dK.411$Acq9.17@fx13.iad> |
| In reply to | #83962 |
Ben <ben.usenet@bsb.me.uk> writes: >"Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes: > > >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? The practical engineer would simply code a linked list and be done with it.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2022-05-06 06:35 +0000 |
| Message-ID | <t52fjk$1l3b$1@gioia.aioe.org> |
| In reply to | #83955 |
Ben <ben.usenet@bsb.me.uk> wrote: >>> > 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). That's exactly the operation I was talking about: Splicing a segment of a list into another list. Which is (quite trivially) an O(1) operation when you have the necessary iterators (which in the algorithm I mentioned you have, at that point). It used to be O(1) in C++98 std::list, but now they made it an O(n) operation, destroying one of the few (if not the only) strengths of std::list over any other data container.
[toc] | [prev] | [next] | [standalone]
Page 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
Back to top | Article view | comp.lang.c++
csiph-web