Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #84041
| From | Manfred <noname@add.invalid> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Anyone ever used vector<bool> ? |
| Date | 2022-05-12 17:24 +0200 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <t5j8qo$1d85$1@gioia.aioe.org> (permalink) |
| References | (22 earlier) <t5bdjm$v7i$2@dont-email.me> <t5bes1$fgp$1@gioia.aioe.org> <t5ds3o$667$2@dont-email.me> <t5e8l9$gar$1@gioia.aioe.org> <423b2f62-20d0-4578-a047-a4c2b03d917fn@googlegroups.com> |
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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web