Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #84030

Re: Anyone ever used vector<bool> ?

From Manfred <noname@add.invalid>
Newsgroups comp.lang.c++
Subject Re: Anyone ever used vector<bool> ?
Date 2022-05-10 19:50 +0200
Organization Aioe.org NNTP Server
Message-ID <t5e8l9$gar$1@gioia.aioe.org> (permalink)
References (20 earlier) <jds7siF965aU1@mid.individual.net> <t5bced$16o3$1@gioia.aioe.org> <t5bdjm$v7i$2@dont-email.me> <t5bes1$fgp$1@gioia.aioe.org> <t5ds3o$667$2@dont-email.me>

Show all headers | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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