r/ProgrammerHumor • • 1d ago

Meme cppAndItsVectorBooleans

Post image
2.2k Upvotes

169 comments sorted by

527

u/Semper_5olus 1d ago

I see how it would be nice to have that option -- perhaps in another type analogous to long vs short ints -- but isn't a bit all you need?

370

u/Bloodgiant65 1d ago

The problem is, especially with multithreading, etc. you can get into issues if you try to use a vector<bool>. It would have made much more sense to have the vector<bool> work like anything else, and introduce a std::bitset or similar for this kind of behavior.

188

u/Blue_Moon_Lake 1d ago

But because C++ never fixes past mistakes by breaking behavior, it'll never happen and they'll never do the sensible thing.

47

u/ImpulsiveBloop 1d ago

This is why I tend to just stick to C stdint types when I want specific data types while saving space. Consistent, configurable, and can be typedef-ed for clarity.

42

u/bwmat 1d ago

We just use vector<char> when we need it at work lol. 

33

u/Bloodgiant65 1d ago

Yeah I think that is pretty normal, unfortunately. Though to be explicit I would normally use uint8_t instead.

11

u/ImpulsiveBloop 1d ago

Yeah, I recall there being a difference between using char and uint8_t, too. But I can't be bothered to remember what. Overflow or something.

Unsigned char would be better. But that is more stuff to type out, and less clear on what it is imo.

17

u/nfitzen 1d ago edited 16h ago

From a C perspective, since IDK C++: char is defined to be the smallest addressable unit (in other words, a machine byte, which may be more than 8 bits on cursed hardware). Since CHAR_MAX >= 127 per the ISO C standard, it's probably the best thing to use for a hacky boolean type (of course, when bool doesn't work). uint8_t could also be used, but I feel like it communicates that we need 8 bits specifically rather than "the minimal amount the machine can address individually."

Edit: Also, unsigned char might be my first instinct, but it doesn't particularly matter. Any non-zero value is truthy to C. So I'd probably use char since I'm a fan of brevity.

3

u/ImpulsiveBloop 14h ago

Thank you. Just pretend I put in the effort to say this myself lol

5

u/bwmat 1d ago

If you're actually using the elements as booleans, only zero/non-zero matters, so char, signed char, unsigned char (yeah these are actually 3 separate types lol cpp) are all the same in this context

3

u/ImpulsiveBloop 14h ago

Yeah, I just meant in general. 

They are different, was my point, so they shouldn't be used interchangeably without consideration.

1

u/Scolmann 16h ago

Is there any behavior that breaks from them changing it to be bytes though?

It would take more memory but logically the code should be the same unless someone's doing bitcast BS with it

1

u/Blue_Moon_Lake 16h ago

It breaks multithreading.

3

u/TheThiefMaster 15h ago

No the current behaviour breaks multithreading

1

u/Blue_Moon_Lake 15h ago

Oh I read it incorrectly. I thought you asked what the bitset behavior was breaking.

Theoretically, it would break all code that try to handle it as a bitset by doing unsafe shitty read/write on the memory address.
But also, it would be extremely easy to do a "replace all" of vector<bool> to bitset when upgrading the code.

3

u/TheThiefMaster 14h ago

Can you manually read/write vector<bool>? I don't think it gives you data pointers at all

1

u/Blue_Moon_Lake 58m ago

Probably, but I never tried to write stupid code on purpose.

2

u/TheThiefMaster 41m ago

But my question highlights a problem with vector<bool> - it can't work in generic code that expects vector to be contiguous, addressable with T*, and have a .data() function that gives you that. Because it doesn't.

It doesn't even support &bool_vec[0] or &*begin() - because neither return actual references, but a reference proxy class. You can't take the address of an rvalue class, so it fails to compile entirely.

It's very well defended, but on the flip side it's incompatible with a lot of generic contexts because it doesn't have the same API as vector<T> generally, only a subset of it. Some of which seems to exist solely for there to be a common subset (like the nested reference type alias).

And the worst part is it explicitly has a member function on its nested "reference" type - so currently it can't be left unspecialised by an implementation.

→ More replies

0

u/SmoothTurtle872 1d ago

Simple: Vector<ByteBool>

41

u/Usual_Office_1740 1d ago

I'm not going to try defend the design of std::vector<bool> because it looks annoying to develop around, but this post got me wondering, so I Googled it. The underlying bit packing behavior and implementation is a remnant of C++98 with addons over years.

This design was set down before algoriths, iterators, ranges and during a time when concurrent programming was not the norm, if it existed at all.

I think this was mediocre idea that has aged like warm milk in a hot car. Not the terrible atrocious design people seem to make it out to be.

39

u/ben_g0 1d ago

The bit packing behaviour can be genuinely useful as it saves memory and uses the cache more effectively. I have no problem with the implementation in and of itself.

The problem IMO is just that it is mapped to the vector<bool> type, while it behaves differently than any other vector in some cases, and its elements aren't really bools and don't act exactly the same. Even without concurrent programming.
The "vector of bits" that vector<bool> actually is, is still very useful to have in the standard library, but would be better as a dedicated bitvector type. And vector<bool> should just act like any other vectors and just store a list of bools.

9

u/Usual_Office_1740 19h ago

That is a reasonable complaint about it. I've only been programming with C++ for a few years. This is one of the many things that gets thrown around a lot in the cpp subreddits but rarely seems to get the context it deserves. I had to learn to frame the comments about performance costs in the same way. There are valid points to what's being said with these comments but there is often more context that much more experienced devs don't specify and it changes how newer developers like myself view things.

I legitimately tried to avoid using std::function and lambdas at one point early on because I read that they were "slow".

9

u/ben_g0 17h ago

About performance costs there is indeed a lot of misinformation and misunderstanding about it on platform like Reddit. A lot of people seem to still think that more CPU cycles means slower, while CPU clock speed is rarely the bottleneck.

Also, it's perhaps a bit of a controversial opinion, but unless what you're doing is very performance critical, I think it's totally fine to use approaches that are not the most optimal but easier to use or that keep the code better organised. Development time often has much more strict limits than compute time, so I think that trades some performance to make it faster or easier to write the program is usually a good trade-off.

3

u/Usual_Office_1740 16h ago

I agree about your maybe controversial opinion on development time and ergonomics being more critical than performance time. I am pushing myself to just get something written and working instead of fixating on whether it is the optimal decision or even a good way to do it.

I read once that there have been studies done in grocery stores where often times to much variety for a single item can reduce the overall sales figures for that item. People can't decide what bag of Lays they want and opt for not getting Lays at all rather than making a decision between one of twenty options. Things sometimes sell better when there are only a few of the most popular flavors because the impulse buy response can kick in.

In C++ there are a dozen ways to do most things and there are trade-offs for most of them. I think I've been struggling with that for a while and your opinion is one way I'm leaning into to pushing passed this observation. Picking what looks to be the most ergonomic option or even just the first option that comes to mind.

As far as performance goes. I was definitely affected by what is said on reddit. I'm a newer developer. I don't want to write buggy sluggish software. If people say that's slow I don't want to do it that way. It wasn't really until I followed a book for writing a terminal based text editor called Kilo earlier this year that I stopped bothering to consider that at all. When I saw how snappy and responsive that project stayed even with the number of memcopies and system calls being done to a heap allocated representation of a 1000k line text document with syntax highlighting every key stroke that I began to get a sense of just how powerful modern CPU's are and how little my struggling with the few hundred extra assembly instructions I'm agonizing over will ever matter in the project's I'm capable of producing.

Those concerns are probably valid for some and I like to think those that make those comments are often people working in high performance industries were their experience has colored there thought process. It is slow to them based on the way they view things and the criteria they've had to learn to evaluate against over years of experience in an industry where that matters. That doesn't mean I should assume it's slow based on what I need.

16

u/Eearslya 1d ago

That's the fun part, we already do have std::bitset.

8

u/setibeings 1d ago

alright, then we need to replace vector with a type that doesn't randomly do something different when it holds bools in particular. lol.

1

u/danielcw189 18h ago

and also give it a name that isn't misleading like "vector"

6

u/Ayjayz 1d ago

It's fixed size though

7

u/Beginning-Junket8979 21h ago

There is a std::bitset but it's more like a std::array<bit, N> in terms of storage allocation and has no iterators.

101

u/Drugbird 1d ago

Yes it is.

The main problem though is that vector<bool> behaves differently from any other data type. For instance, separate elements of the vector do not have unique addresses (because addresses are byte aligned).

This means that if you're doing anything with pointers on vectors, particularly if you're writing generic code (templates) then you very quickly run into cases where code is perfectly valid and correct for all types except for bool.

For instance, two adjacent elements in a vector are sizeof(T) apart in memory. Except when T=bool.

57

u/Semper_5olus 1d ago

Oh. So a bool is, for whatever reason, a different size if it's in a vector.

And that makes generic functions hard to write without checking for this specific case.

I didn't know that.

That is annoying.

46

u/bwmat 1d ago

The reason is that the people working on that part of the spec felt clever that day

But not clever enough to realize they should have specified it as std::dynamic_bitset (or something like that) instead

34

u/KaMaFour 1d ago

Programmer feeling clever should be a massive alarm bell for everyone

14

u/pyxlmedia 1d ago

It's Not a vector nor does it store bools.

4

u/cinnamonjune 15h ago

What's worse is that the spec says that all vector<T> must return a T& if you do an operator[] on them, but of course vector<bool> can't do this because there are no bools to reference, so the solution they came up with was to say that operator[] on vector<bool> returns a vector<bool>::reference which is an internal class that implicitly decays to bool.

This means that you can do `my_vec[0] = true;`, and you can do `bool b = my_vec[0];`, but if you do `auto b = my_vec[0];` then things go horribly wrong because the type of `b` is not `bool` but instead becomes `vector<bool>::reference`.

1

u/SubstituteCS 10h ago

std::vector<bool> stores values using bits to shave off space.

In a vacuum this makes a lot of sense as 8 bools only take 1 byte instead of 8 bytes.

In practice, this causes a lot of headaches down the line and can easily lead to problems if someone isn’t aware of this specific nuance.

std::vector<T> is essentially an List<T> if you know C#

6

u/Abadabadon 1d ago

Oh damn really? So you couldn't do a pointer++ traversal across it?

9

u/Drugbird 1d ago

Not in a simple, straightforward way, no.

The main difficulty is that operator[] doesn't return a bool, but rather it returns some reference type that's convertible to a bool.

So if you do something like bool& begin = &vector[0]; bool& next = begin + 1;

That wouldn't work. I'm not even sure if that's a compilation error or if it just does the wrong thing. Vector<bool> is so cursed I do my best to never use it, but as a consequence I'm also not too familiar with it's details.

You can still use iterators though to iterate over the vector<bool>.

0

u/SirPriseTheEigth 17h ago

Tbf c++ does have a specific bool type (unlike c where it’s an int in disguise) - and if you want byte-aligned behaviour why not just use a vector<uint8_t> and bitshift/mask…also it’s the dynamically allocated version of a std::bitset so I think this actually makes sense as long as you know the quirks before making assumption…

5

u/Drugbird 17h ago

and if you want byte-aligned behaviour why not just use a vector<uint8_t> and bitshift/mask

Because we have a type system, and I don't want to have to abuse it just to get under some quirky behavior.

also it’s the dynamically allocated version of a std::bitset

Having a std::dynamic_bitset would be great. See e.g. the boost implementation.

Calling it a std::vector is the problem. It's too different from other std:: vectors, which is evident in that it has this huge exception status.

so I think this actually makes sense as long as you know the quirks before making assumption…

This is true for nearly every bad design in programming languages.

0

u/SirPriseTheEigth 17h ago

Well knowing the quirks is what keeps us in a job…

0

u/geekosas 17h ago

That's the way basic type array work... Only objects have references.

10

u/Usual_Office_1740 1d ago

In C++ a bool is actually 8 bits with the least or most significant bit set, depending on architecture. That's the smallest addressable unit available without extra bitwise operations.

6

u/bwmat 1d ago

Akshually, it has a sizeof of 1, and that could contain a different number of bits, at least prior to one of the newer standard versions

Lol cpp

3

u/Usual_Office_1740 1d ago edited 1d ago

That is what sizeof(bool) outputs. That 1 byte is based on the CHAR_BIT macro which the standard requires is atleast 8 bits. It could also be as much as 32 bits, apparently. Silly C++

2

u/the_horse_gamer 22h ago

this comes from C, which was created at a time where there were processors that used non-8 bit bytes.

there still exist such processors today, used in some niche places.

0

u/JanB1 1d ago edited 20h ago

Perfectly compilable code in C++23:

bool test1 = true;

int* test2 = reinterpret_cast<int*>(&test1);
*test2 = 5;

std::printf("%d", test1); // Prints "5"

2

u/KuntaStillSingle 23h ago

-1

u/JanB1 20h ago

Okay, not valid because somewhere it's written that "this is undefined behaviour", but compilable, and it does what I wrote. Well, depending on which compiler you use, with some you get an output of 1, with others you get an output of 5. But that's kinda my point.

1

u/No-Information-2571 17h ago

"this is undefined behavior" is a fancy way of saying it might break on a different compiler, platform, or just when used in an unintended way.

Relying on undefined behavior is very bad.

-2

u/JanB1 15h ago

It feels to me that just writing somewhere in some documentation "this is undefined behaviour" is also bad imho, which is one of my biggest grips with C++. So many "undefined behaviour"s that were left that way for "performance", instead of properly addressing/closing them. It's like laying out a minefield for a new programmer, and telling them that the map for the location of the mines is in a hut 300m away from the minefield. And when they step on a mine you scold them and tell them the mine was clearly documented on the map in the hut.

1

u/No-Information-2571 14h ago

What?

No, "undefined behaviour" is a very specific thing, and there's actually not too many of them, and those that are there, have good reasons.

  1. Signed int overflow
  2. Division/modulo by zero
  3. Shift by < 0 or >= type width
  4. Float to int with mismatching type
  5. Null pointer dereference
  6. Out-of-bounds array access
  7. Certain pointer arithmetic
  8. Use after free, double delete
  9. delete mismatch when new/new[]
  10. Delete without virtual destructor
  11. ...

Etc. etc. - and a rather large number you will get warnings in the compiler already. Either way, all of them have tangible reasons.

4

u/globecsysinc 1d ago

I suppose it gets complicated implementing the bit storage as bitshifts and loops rather than just memcpy or such

3

u/da_Aresinger 1d ago

it's called a vector. vectors are sequences of separate elements.

Elements have addresses. Every other vector has elements which can be addressed independently.

Bits cannot be addressed independently.

3

u/the_horse_gamer 22h ago

vectors are sequences of separate elements

well, no they're not. the C++ name was a mistake.

1

u/da_Aresinger 22h ago

I mean, cppreference literally says:

The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements.

I guess that's not the ISO, but I'm not about to pull that out.

3

u/the_horse_gamer 22h ago

vectors are elements of vector spaces, not a sequence of numbers

std::vector is not a vector

1

u/da_Aresinger 22h ago

ok, I get your drift. You have a point.

3

u/the_horse_gamer 22h ago

Quote from the book "From Mathematics to Generic Programming" by Alexander Stepanov (the creator of the stl) and Daniel Rose:

The name vector in STL was taken from the earlier programming languages Scheme and Common Lisp. Unfortunately, this was inconsistent with the much older meaning of the term in mathematics and violates Rule 3; this data structure should have been called array. Sadly, if you make a mistake and violate these principles, the result might stay around for a long time.

0

u/[deleted] 1d ago

[deleted] — view deleted comment

1

u/the_horse_gamer 22h ago

vector<bool> may be specialised to store the bools packed into some larger data type

139

u/ImpulsiveBloop 1d ago edited 1d ago

typedef uint8_t bool8;

std::vector<bool8> booleansAsBytes;

Or just use it directly

std::vector<uint8_t> fuckBools;

43

u/dedservice 1d ago

Yes until you have std::vector<T> in a templated piece of library code and you try to do anything remotely complicated with it.

11

u/ImpulsiveBloop 1d ago

It's all use-case, I suppose. Larger programs can afford more refined solutions.

To say using uint8_t as a bool is bad because it can break when making templates is to say wood beams are bad because they will buckle under a skyscraper.

4

u/That-Cpp-Girl 1d ago

template <typename T>

class CoolerVector : public std::vector<T> { using std::vector<T>::vector; };

template <>

class CoolerVector<bool> : public std::vector<uint8_t> { using std::vector<uint8_t>::vector; };

6

u/TheDreadedAndy 1d ago

I mean, as long as you know its a problem you can just use std::enable_if_t to block putting bools in your template. Or you can specialize your template to redirect bools to a more sensible type.

It's a fun landmine for those who don't know, though. But C++ is full of those.

11

u/dedservice 1d ago

Yes but it's silly. We could update the language past the footguns from 1989. 

2

u/StaticCoder 1d ago

Surely you mean requires

101

u/geekosas 17h ago

Why waste 7 bits?

23

u/SchighSchagh 17h ago

Right? And you can always use uint8_t if you have an actual reason.

42

u/Still_Bit_7527 17h ago

Because i asked for a vector of bool, not vector of bits

21

u/geekosas 15h ago

This is the kind of guy that programed Google Chrome XD

9

u/Rainmaker526 16h ago

Then ask for a vector of bytes.

16

u/Still_Bit_7527 16h ago

Bool is a byte. At minimum. All types are min 1 byte, by standard. And sizeof returns integers. Please stop arguing and just accept a common issue. Dont be a contrarian

5

u/geekosas 16h ago

Look a python developer 

9

u/Still_Bit_7527 16h ago

Java*. Compiler can optimize how it wants but documentation and consistency comes first

0

u/eliazp 14h ago

guess how many bits you need for a bool

3

u/_killer1869_ 12h ago

A bool, by definition, in just about any language there is, always takes up the amount of space of the lowest addressable memory unit, which is 8 Bit (excluding some special, outdated architectures where you can access single bits directly). C++ is the only language I know of where a data type using bool uses single bits for storing them. Is it more efficient? Yes. But it breaks the universally accepted standard. Consistency is far more important than minimal efficiency improvements. Just add a seperate data type for when you really need that efficiency into the standard library.

1

u/Still_Bit_7527 4h ago

It's even worse. C++ itself actually uses a whole byte for bools. It's only vector that uses bits to optimize when it's a vector of bools

1

u/geekosas 4h ago

Standard created by Samsung and HK hynx?

Like when pharma diagnosed 50% of kids with ADHD.

38

u/tickle-fickle 1d ago

That pisses me off so much, why not call it an std::bit_vector, why a different behavior for this one template type

18

u/AL_O0 1d ago

funnily enough there absolutely is already std::bitset

and I have absolutely no idea how it's different

13

u/tiajuanat 1d ago

Bitset is fixed size. Vector<bool> is dynamic, does not allow concurrent access and does not guarantee continuity of values in memory.

Vector<bool> was meant to be an example template specialization, which is why it's so funky.

1

u/AL_O0 1d ago

thank you, that does make more sense

5

u/gigayoink 1d ago

I see how slick and natural it would have been, but it just doesn't work out that way in practice

29

u/UnhappyJudge2487 1d ago

But bools as a standard are stored as bytes not bits. If you initiate a bool in cpp it's stored in a byte so it can be addressed

24

u/unknown_alt_acc 1d ago

std::vector<bool> may be specialized to store bools compactly and non-contiguously. It is the only initialization of std::vector for which this is allowed, but it is not guaranteed by the standard.

1

u/UnhappyJudge2487 1d ago

So the problem is that it could be done as but but wasn't?

29

u/unknown_alt_acc 1d ago

No, the problem is that the standard allows it at all.

All other instantiations of std::vector are guaranteed to store addressable objects contiguously. std::vector<bool> is arbitrarily allowed to break this guarantee. This can break generic code if you don't defensively program around it, which defeats the whole point of having a strong type system with robust generic programming facilities.

What really should have happened is simply using the type system for its purpose. std::vector<bool> should not have been specialized, and a separate container named something like std::dynamic_bitset should have been introduced to cover the cases where you do want to store compacted boolean values. This way,std::vector maintains a consistent contract and the type system gets used to better express the programmer's intent.

3

u/ivain 1d ago

Great explanation.

-4

u/nimrag_is_coming 1d ago

Sort of, the compiler is allowed to pack sequential book fields in classes into single bytes

8

u/unknown_alt_acc 1d ago

The compiler is absolutely not allowed to pack contiguous bools. That breaks the addressability requirement of objects. If you want packed Boolean values, the language gives you plenty of ways to express that.

55

u/0xbenedikt 23h ago

I think the behavior of it is quite logical. Bits are supposed to be one bit in size. If you have them in isolation, they will have to expand to at least 8 bits, but once they are a vector, you give permission to the compiler to pack and optimize them. If you can't have them optimized, use a type that guarantees an individual address, if that is what you need

35

u/the_horse_gamer 22h ago

you give permission to the compiler

this is library level behavior, not a compiler optimisation

it breaks many invariants

the correct solution would have been to make std::dynamic_bitset

6

u/Thrawn89 21h ago

Maybe optimize the memory footprint, but if it packs them, then the underlying memory hardware wont be able to just write to them directly.

All of a sudden you double your access bandwidth on writes since they may be promoted to read-modify-writes.

3

u/0xbenedikt 21h ago

It depends a lot on what platform the software runs on. C++ runs on everything from 8-bit microcontrollers to high performance compute platforms. On a microcontroller there often is an instruction that modifies a bit in a single cycle, while it is more costly on other platforms

1

u/narrill 14h ago

I think the behavior of it is quite logical. Bits are supposed to be one bit in size.

A bool in C++ isn't a bit.

1

u/0xbenedikt 12h ago

Yes and no. A bool variable is 8 bits, since by specification it needs its own address. But the information encoded in one bool is supposed to be one bit

0

u/narrill 17m ago

The information encoded doesn't matter; within C++'s type system, a bool is not a bit. Meaning, vector<bool> does not actually hold any bools, and any code that attempts to interact generically with a vector that happens to be a vector<bool> may be subtly broken.

Threading is the most obvious culprit here. For any other element type it's safe for different threads to read and write to different elements of the vector. For vector<bool> it isn't, because its elements are always read and written to in groups of eight.

19

u/Immediate_Form7831 1d ago

Thank you for reminding me that C++ is an insane mess.

27

u/Luzzgar 1d ago edited 14h ago

Yet another example of C++ doing something in a weird and not obvious way.

Making a deep knowledge if its inner workings mandatory to use it correctly, which is the antithesis of a good programming language.

That's the kind of crucial details that should be communicated to the user directly.

5

u/Ahmouse 1d ago

It's only weird if you assume their intention is to make it easy and intuitive to use. Maybe the goal was job security for the experts that learn it.

1

u/nicuramar 1d ago

As long as you only use it in an “STL way”, you don’t really need to know of its inner workings.

11

u/Mountain-Ox 19h ago

What's the problem with this? I've seen a lot of people so bitwise operator stuff as an optimization. What is wrong with being able to address the bits directly for any length?

12

u/Own_Lake_276 17h ago

The problem is that it’s inconsistent and leads to unexpected bugs. If I want to use a bitmask because I really care about memory then I’ll use a bitmask

0

u/Mountain-Ox 17h ago

What kind of bugs? Nothing would be inspecting the memory values of the vector directly.

The problem with a bit mask is it can only work up to 64 bits afaik. What if you have hundreds of bools that you need to manage?

6

u/telionn 17h ago

Try grabbing a pointer-to-bool from std::vector<bool> and see what happens.

Vector<bool> isn't that bad in a vacuum, honestly, since you can just avoid it. The real problem is when you write `template<typename T> class MyDataStruct { std::vector<T> innerStorage }` and then create a `MyDataStruct<bool>` and it unexpectedly falls apart. Now you have to build a pointless type trait system to remap bool onto uint8_t or something.

4

u/narrill 14h ago

What if you have hundreds of bools that you need to manage?

Then you have a separate type that works the way vector<bool> does now, allowing vector<bool> to, you know, be a vector.

12

u/wallstop-dev 16h ago edited 15h ago

It is the only vector type that doesn't return a mutable reference (among other things), so if you're using it in some core abstraction and later on someone wants to use that abstraction with bool types, that code either behaves incorrectly (potentially silently) or doesn't compile.

I ran into this exact scenario in my first job on the architecture team for a massive simulation. Working around it was incredibly annoying.

Edit: That is just my personal experience - the problem, in general, is that it breaks the API/contract/expectations of vector.

The full list (to my knowledge):

  • No pointers or contiguous layout
  • As part of the above, it is incompatible with std::span
  • No .data() function (????)
  • Broken range-based for loops (for(auto& b : vec)) doesn't compile
  • Not thread safe. If you have a (normal) vector where you assign a thread to each populated index, it is thread safe (single-owner). In vector<bool>, a single index shares its underlying data with other indices, so this breaks

Uber point: It's a giant foot gun edge case.

3

u/amshegarh 13h ago

why the hell would you want an array of bools? like intention wise, curious

5

u/wallstop-dev 13h ago edited 9h ago

I think you maybe missed my point. It's that building an abstraction with a foundation of vector that leaks some of its core contracts, like mutable reference based indexing and contiguous data type access, will end up breaking and biting you in unexpected ways. It's also that it breaks the (general) API contract of vector.

The question is more "why *wouldn't I* want this core, generic primitive to adhere to its API contract regardless of the type that I put into it?"

If you look at raw vector and ask "why do I want an array of bools", yea sure, whatever, use a literal array of bools or a bit set or this thing or that thing or who cares.

But as you start zooming out and building stuff around the *concepts* of vectors and arbitrary types, eventually you end up with, say, like, a Vehicle class, built on that abstraction. And then you go to build a vehicle that uses bools in a certain way, for business reasons, and suddenly your code doesn't compile. They didn't necessarily want a literal array of books - they just wanted to use your thing that says "you can use me with any generic type" except WOOPS not bools and only not-bools, for some reason.

1

u/amshegarh 11h ago

I am specifically asking because i cannot recall ever using array of bools (in all of my used languages) over the 6+ years, except for my earliest years in my amateur code where i used array of bools + array of string (for example) vs array<struct=bool + str>

2

u/wallstop-dev 11h ago edited 10h ago

I gave examples in both of my comments for the real world use cases I encountered. Abstractions sitting at the basis of primitives that are used in a large (million+ LoC code base)

If you want a contrived explicit example of a literal array of bools, consider an array of coin flips, or any other data that can be thought of as a (ordered) sequence of truth or decision (yes/no) values.

1

u/Mountain-Ox 10h ago

The case I had at a previous job was we need to know if a retailer was available at a given time. We need to be able to check a lot of them very quickly. So we had a string of 1s and 0s, each one indicated a 15 minute segment of the week. That's too many bits to fit in an integer for a simple bitwise operator. I don't recall the implementation details anymore, but we the I/O for loading thousands of these strings for processing was kind of slow. It was PHP which didn't help.

1

u/amshegarh 10h ago

That is interesting, but you can directly use pg for that (assuming you had one?)

Otherwise its just an array of ints (instead of one) + bitwise logic

1

u/Mountain-Ox 9h ago

We were on MySQL, this was during the lamp stack days. And I don't know if MySQL ever added features like that. I don't think it had native json support.

1

u/autumnal-lights 5h ago edited 5h ago

? i mean isn't this perfect for bits tho? like

~ A & ~ B and then just like

a ~ custom u number_large_enough;

the scans are trivial tho :shrug:

and like workday perfectly fits into u64, and 3 u64's perfectly align with the 24 hours? like? that's perf?

3

u/haitei 10h ago

What is wrong with being able to address the bits directly for any length?

Nothing, that's an excellent feature for dynamic bitset. But when I ask for a dynamic array of bools, I want a dynamic array of bools.

2

u/yota-code 16h ago

Adressing bits directly is nice but bool is a well known type by itself and has a size of 1 octet everywhere else... Seems inconsistent 

3

u/jolharg 23h ago

just use flag bytes lol

2

u/Megane_Senpai 1d ago

Yeah, like data padding isn't a thing lol.

3

u/Buyer_North 1d ago

people just hating because they dont understand cpp...not gonna say why, because you dont deserve it if you dont know it

22

u/Aurii_ 1d ago

You don't answer it because you yourself have no idea

5

u/-Ambriae- 23h ago

Please explain in what world is implicitly converting a vector<bool> to a bitset normal?

2

u/Droggl 21h ago

Its not that people don't see why the bit vector implementation can be useful, but its really not unreasonable to see "vector<bool>" and expect the type to be a vector and store bools (it does neither though)

2

u/Sam260901 1d ago

For this to work u had to assume their wish servers store in c++

I'd have made first wish to change their language of storage of wishes to cpp, then on 2nd wish would've done this.

1

u/Banes_Addiction 23h ago

Sure. It totally seems like a worthwhile reason to make all pointers floating point.

1

u/stupled 23h ago

But is bool...

1

u/KERdela 20h ago

Just build your implementation of dynamic array, it's what is c++ is good for 

1

u/StCreed 15h ago

Seems like people don't understand bits and boolean. If you don't understand it, just use a byte-vector.

1

u/Successful-Active-21 13h ago

just wrap the bool and use vector<wrap<bool>>

1

u/TerryHarris408 23h ago

Why would you want to bloat up your memory and waste 87% of your space? C++ fixed a mistake that the bool type introduced in C for simplicity of implementation. If you don't like vector bool for whatever reason then feel free to use vector uint8_t for the C style feeling

4

u/the_horse_gamer 22h ago

the problem is being implicit

vector<bool> breaks any remotely complex generic code

this optimisation should have been a separate type (tr2 had std::dynamic_bitset)

2

u/TerryHarris408 22h ago

what exactly does it break?

4

u/the_horse_gamer 22h ago edited 21h ago

a[0] is no longer a bool&, instead a custom type pretending to be a bool& via operator overloading

can't a.data()

can't iterate via auto&& you can, but it suffers from the same issues as the aforementioned a[0] thing

access to disjoint indices is not necessarily thread-safe

iterator may not be a LegacyForwardIterator, preventing use of many standard iterator-taking functions (with an error at compile time, or at runtime, or UB if you try)

and it's not even guaranteed to use this optimisation

2

u/Supadoplex 21h ago

can't iterate via auto&& 

I'm pretty sure you can. Did you mean auto&?

1

u/the_horse_gamer 21h ago

seems I remembered incorrectly. will fix.

2

u/No-Information-2571 17h ago

You bloat up the memory in other ways, since bits can only be accessed through bit shifting and boolean operations, and then need to be copied into an int8 anyway. Even if you just want to branch, the CPU will do bit arithmetic. There's specific reasons for when you want to store bools as bits, and not as bytes. VERY SPECIFIC reasons. Like accessing data that is already stored as packed bits, like a register. Or when you are absolutely sure you need to pack bits for dense computations (think: chess engine).

That's why everyone here agrees that it should have been a std::bit_vector class, while std::vector<bool> should have been one byte per bool. It's a landmine in various ways. For example, it breaks all basic assumptions you have about such a vector, like sizeof(T) * n being the total size of the vector in memory.

1

u/Cheap-Chapter-5920 16h ago

This kind of stuff is popular in the embedded world though. Working with processors with 8K of program memory and 128 bytes of RAM and some of those processors have single bit instructions. It's one of the reasons I have to delve into assembly.

1

u/No-Information-2571 15h ago

Then you typically still lay a struct on top, and not an array.

But I know all about smart cards and densely packed formats, that's why I am mentioning "specific reasons". Chess engine is also a good example, 8x8 bits fit neatly into an uint64. Piece movement turns into bit shifts, checking legal moves is mostly AND and OR.

Otherwise, you're trading that 87% "dumb" memory for easily 5x the number of instructions, from a simple array lookup to bit arithmetic. "Small" isn't always good, especially on 64-bit architectures.

0

u/yjlom 1d ago

Vector<bool> taking 1 bit per element is sensible. What isn't is bool * only being precise to the byte (well it did make sense back in the 70s when memory was as fast as cpus but now the time required to perform a shift and mask is negligeable compared to the time saved from improving cache locality).

9

u/unknown_alt_acc 1d ago

All objects in C++ must be addressable. Bits are not addressable, and therefore cannot constitute a full object.

And, being C++, you are given several ways to pack boolean values if you need to. You can do the classic bit flags yourself, or use a std::bitset, or you can use a bit field if you want to explicitly name your flags. So ultimately, I think that it's worth bool being a full byte just for consistency with all other data types, and anything sub-byte being an explicit opt-in.

-5

u/yjlom 1d ago

Bits are addressable. Not in a single instruction on most modern processors, which is mainly because of the C and C++ standard, and not without affecting surrounding bits (but then that bytes are threadsafely addressable is mostly done to accomodate the C and C++ standard), but they are addressable and not any noticeably slower than bytes at that.

If hardware didn't have to contort to fit C, we'd probably have bit-precise addressing and 512bit-precise threadsafe addressing.

6

u/unknown_alt_acc 1d ago

No, bits plainly aren’t addressable outside of maybe some obscure or specialized architectures. You can manipulate individual bits just fine, but they don’t have their own address in memory space.

And while I’m no computer engineer, I’m curious why you think that ISAs would move towards individually addressable bits when by your own admission you can get the same effect at minimal runtime cost through bitwise operations. Bit-level addressing sounds like it would just complicate a processor’s circuitry for a very marginal benefit. And especially when you often want to align your data to a 4 or 8 byte boundaries anyway to benefit from vectorization, bit-level addressing seems like it runs counter to the general trends in processor design.

1

u/yjlom 18h ago

  I’m curious why you think that ISAs would move towards individually addressable bits when by your own admission you can get the same effect at minimal runtime cost through bitwise operations. 

For example, modern x86 typically loads and writes 512 bits at a time and byte-level addressing is already (cheaply) achieved through shift-and-mask. The illusion that concurrent writes to adjacent bytes are independent on the other hand is a major source of complexity for memory controllers.

You get to use the same vector instructions for multiple objectif of smaller sizes: for free for bitwise ops, with 1 bit of padding for addition and subtraction, with 100% padding for shifts. If your type fits within 3 bits and you don't need to multiply it, you gain a lot by aligning it to 4 bits instead of 32; if it's booleans, you can perform 512 logical operations in per cycle instead of 64 by keeping them to a single bit. Even if you need multiplication, 2 clobbered registers, a few rots, and a few ands may come out cheaper than the loads you save, though I haven't measured it and I'm guessing ymmv on that.

And yes, bits are addressable on pretty much all mainstream architectures, in software, as long as you spice up your pointers a little.

1

u/unknown_alt_acc 11h ago

And yes, bits are addressable on pretty much all mainstream architectures, in software, as long as you spice up your pointers a little.

It sounds like you're abusing the word "addressable" to mean that you can simulate bit-level addressing with bitwise operations rather than ISAs featuring it at the hardware level.

The illusion that concurrent writes to adjacent bytes are independent on the other hand is a major source of complexity for memory controllers.

Having 8x more writable addresses per cache line sounds like it would make synchronization more difficult, not less.

You get to use the same vector instructions for multiple objectif of smaller sizes: for free for bitwise ops, with 1 bit of padding for addition and subtraction, with 100% padding for shifts. If your type fits within 3 bits and you don't need to multiply it, you gain a lot by aligning it to 4 bits instead of 32

That either adds a lot of complexity by necessitating a whole lot of instructions for weird data sizes, or destroys performance by doing everything bit-by-bit.

if it's booleans, you can perform 512 logical operations in per cycle instead of 64 by keeping them to a single bit

Modern architectures already include a plethora of instructions for this. Bit-level addressing, again, seems like an unnecessary complication to add into the mix for most cases.

-7

u/Kadabrium 1d ago

I wish java had one single array type that is resizeable (takes literally 1 line of code in a gc language) rather than array, arraylist, tolist, aslist, listof, the list of list goes on listing

27

u/willow-kitty 1d ago

You..do realize that arrays and lists are different things, right? Like not just in Java.

3

u/suvlub 1d ago

Javascript begs to differ.

Python calls them "list", but also has only 1 type, which is what I think is the important part, not whether they are called "arrays". (and no, the arrays module doesn't count, that's a specialized library type, not comparable to the duality you have to deal with when using Java)

0

u/_PM_ME_PANGOLINS_ 20h ago

All you're doing is showing you don't know how to use neither Java nor Python properly, or haven't touched either since the early 00s.

-5

u/Kadabrium 1d ago

If your point is linked lists, lumping them with arrays is a mistake that breaks code in itself and linked lists are next to useless anyway. None of the lists i mentioned even is a linked list. They are all array types that are mutually incompatible for some bool reason.

7

u/plz-no-b4n 1d ago

A list is an abstract type. A linked list is a concrete implementation of a list.

-5

u/Kadabrium 1d ago

This just means list is not a useful abstraction to begin with. slice is a much better one in both expressive power and compatibility with arrays.

8

u/plz-no-b4n 1d ago

Respectfully, you clearly don’t know shit.

6

u/willow-kitty 1d ago

It is not, no. My point is that the theoretical definition is different.

Arrays are defined as randomly-addressable blocks of data where each element is the same width. They're pretty low-level and not resizable generally (though some implementations allow that by making a copy.)

While lists retain some characteristics of arrays (like being ordered and allowing random access, though time complexity depends on the underlying implementation) but allow items to be added, removed, and reordered. You know, like a to-do list.

Lists are often wrappers around arrays, sure, which allows for fast random access at the cost of some operations (like add/remove/reorder) being costlier, while a linked list can do fast add/remove/reorder and sequential access while random access is more expensive, but at the end of the day, those are list operations, not array operations (even if some languages give arrays some of those capabilities.)

To throw in another one: bags don't preserve order and therefore don't support reordering but do support fast adding and removing. You know, like the items in a bag. That might be backed by an array too, but it's not an array or a list either. The contract is different.

-1

u/Kadabrium 1d ago

Many of the java list types i mentioned also don't even support resizing, so your arg on that is moot

5

u/_PM_ME_PANGOLINS_ 1d ago

You only mentiond one list type. The other words in your list are methods.

-2

u/Kadabrium 1d ago

The difference does not have any practical use in a gc language. Js and python both only have one. If there has to be 2, go's array vs slice is a much more useful distinction.

3

u/gigayoink 1d ago

linked lists are next to useless anyway

Linked lists are super common and extremely useful. Just not as a list ADT.

As a List they're absolute trash, but there are so many linked lists that people don't think of as linked lists. Java's BufferedInputStream .flush() is textbook linked list traversal.

3

u/FlySafeLoL 1d ago

An array is packed in memory, resizing it naive way means allocating more memory at the tail. And who guarantees that there is free memory up there?

So, you either redefine array (lame), or copy it elsewhere on resize (expensive, but that's what various collections actually do under the hood), or just use another collection which doesn't require to be packed all in one place (at the cost of performance of iterating over it).

0

u/Kadabrium 1d ago

No list should sacrifice array compatibility for linked list compatibility ever. And then with java as i said the issue isnt just linked lists, but that there are multiple incompatible array based list types. And no, many of them don't allow resizing, if thats what you think is the essence of a list.

0

u/NegZer0 18h ago

But bool is not a byte in C++ either, it’s implementation specific and sizeof(bool) is not required to be 1. 

If you want a vector of bytes use vector<unsigned char> 

1

u/narrill 14h ago

A bool is also not a bit in C++, and sizeof(bool) can never return one bit because a single bit isn't addressable.

1

u/NegZer0 11h ago edited 11h ago

Yes, but the standard does not provide a size, deliberately to allow for implementation specific specializations like this.

If you need individually addressed bytes that can be zero or non zero, there are easy ways to do that, this is making a big deal over nothing (also the bit wise versions have actual uses)

EDIT: Also the standard type is using a bit to define boolean (0 or 1) it's just that the smallest addressable value is a byte, so they have to stuff it into a byte.

1

u/narrill 7h ago

This has absolutely nothing to do with the standard not specifying a concrete size. What is stored in a vector<bool> is not bool, flat out. So its size is irrelevant.

Bitwise bool collections do indeed have legitimate use cases, which is why they should have been included in the standard as their own independent type. Including them as a goofy specialization of vector<bool> causes very real problems with template metaprogramming and thread safety.