Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #83963
| From | "Alf P. Steinbach" <alf.p.steinbach@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Anyone ever used vector<bool> ? |
| Date | 2022-05-06 14:29 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <t534c8$c7b$1@dont-email.me> (permalink) |
| References | (7 earlier) <875ymkp4zv.fsf@bsb.me.uk> <t5192j$kud$1@dont-email.me> <8735hnohzi.fsf@bsb.me.uk> <t52msn$64k$1@dont-email.me> <87sfpn7wz2.fsf@bsb.me.uk> |
On 6 May 2022 12:54, Ben wrote:
> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:
>
>> On 5 May 2022 22:13, Ben wrote:
>>> "Alf P. Steinbach" <alf.p.steinbach@gmail.com> writes:
>>>
>>>> On 5 May 2022 13:56, Ben wrote:
>>>>> Öö Tiib <ootiib@hot.ee> writes:
>>>>>
>>>>>> On Thursday, 5 May 2022 at 12:50:26 UTC+3, Ben wrote:
>>>>>>> Juha Nieminen <nos...@thanks.invalid> writes:
>>>>>>>
>>>>>>>> Paavo Helde <ees...@osa.pri.ee> wrote:
>>>>>>>>> I have hard time finding any use case at all for std::list.
>>>>>>>>
>>>>>>>> When I was working at the university here I once had to implement
>>>>>>>> (a rather complicated and advanced) algorithm (which had something to
>>>>>>>> do with graph manipulation) which required a doubly-linked list. No other
>>>>>>>> data container would have done the job because the speed of the algorithm
>>>>>>>> relied on the ability to splice linked lists (and sections of them).
>>>>>>>>
>>>>>>>> That being said, std::list couldn't be used for this, especially now
>>>>>>>> that std::list::splice() is not an O(1) operation (which would pretty
>>>>>>>> much defeat the purpose).
>>>>>>>
>>>>>>> It's O(1) in C++11, 14 and 20 (at least in the public drafts).
>>>>>>
>>>>>> It has 6 overloads. Most are O(1) but one case where we transfer iterator
>>>>>> range from other list to this list is linear in length of said range.
>>>>> Obviously, but that's surely not what the OP was talking about. That
>>>>> one could never have been, and will never be O(1).
>>>>
>>>> With the choice of potentially O(n) `.size()`, instead of the silly
>>>> C++11 decision, all splicing overloads could be O(1) and `std::list`
>>>> could have been useful for something.
>>>>
>>>> Since the word "now" was used, that was surely what was being mentioned.
>>>>
>>>> Obviously. ;-)
>>> How much of your post does the smiley apply to? I don't want to waste
>>> everyone's time...
>>
>> I guess you're unfamiliar with the history. The fight was about the
>> guaranteed complexity of `.size()`. With O(1) complexity a splice has
>> to count the number of spliced nice, which turns a simple O(1) link
>> manipulation into O(n) counting.
>
> I'm familiar with the trade-off in abstract (since it crops up every
> time one implements a list as was so common in days gone by), but I did
> not know there had been a fight about it in C++.
>
>> The academic idealists won, the practically oriented people lost, and
>> `std::list` became useless.
>
> Curious that you put it like that. There doesn't seem to be anything
> obviously idealistic in opting for O(1) size and linear splicing for
> "foreign" sub-lists. I don't recall ever wanting that form of splice,
> so I would consider C++'s choice quite practical (for me). What makes
> this the "idealists" preferred option?
E.g. as Howard Hinnant put it some time before C++11, in an article at
<url: https://howardhinnant.github.io/On_list_size.html>:
❝As the standard is written today, none of the containers are required
to have an O(1) size(). I believe that this should be corrected in
C++0X. [Expressing an academic ideal:] If a container has a size()
member, it should be required to have O(1) complexity. [Again expressing
an academic ideal:] If a container can not manage this, it should not
have a size() member at all. Clients can always compute
distance(begin(),end()).❞
The inline square brackets notes are my annotations.
In the article Howard makes a number of to me dubious claims and
presents a misleading feature sheet, where the reader is led to compare
number of alleged advantages for O(1) and O(n) `.size()`. I'd say that
kind of misleading argument indicates that in this matter he represented
an academic view. But possibly that reflects my personal impression of
academics (I've held an academic position but I didn't really fit in).
Likelihood argument of academic POV: Howard was the designer of
`std::unique_ptr`, and in a slightly heated discussion between us over
on SO, where I see now that I presented a needlessly complicated example
(not proud of that, but at least it was an example), he turned out to be
unaware that `unique_ptr` could exhibit undefined behavior due to
implicit conversion of `unique_ptr<Derived>` to `unique_ptr<Base>`, i.e.
that it's not as type safe in this respect as `std::shared_ptr`.
I guess the most upsetting thing about that was not his ignorance of the
issue, but that most anybody would /assume/ that the following would
either be safe, or else would not compile at all, while reality is that
it compiles and exhibits manifest UB with both MSVC 2022 and g++ 9.2:
#include <memory>
#include <utility>
using std::unique_ptr, std::make_unique,
std::move;
struct Base{ int m_answer = 42; };
struct Derived: Base{ virtual ~Derived(){}; };
auto main() -> int
{
auto p_derived = unique_ptr<Derived>( new Derived() );
#if PLEASE_FAIL
auto p_base = unique_ptr<Base>( move( p_derived ) );
(void) p_base;
#endif
(void) p_derived;
}
`std::shared_ptr` is safe for code like above because it retains the
original object pointer.
> The engineer's perspective might be to have two list variants, one with
> a maintained length and one without. Did that option crop up in the
> fight?
Sorry I don't remember, and I was not involved other than e.g. in
discussions here in clc++ and clc++m (I've never been involved, really).
But I can imagine a lot of ways to let client code decide instead of
forcing a decision. Two list variants, as you mention, is one way.
Cheers,
- Alf
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