1

In a class, I want to have a member representing a table which contains a list of binary data for each character in the ASCII table, so the number of rows in the table is fixed. All rows will have the same size, but the size is a variable given as a parameter. So I decided to use a two-dimensional bool array.

I have read somewhere that it's better in C++ to use a 2D bool vector in this situation to save some space, so I tried it, but when I tested my program I found that it was much slower than the 2D bool array.

This is how I initialize my table in the initialization list of the class constructor:

bits(ALPHABET_SIZE,std::vector<bool>(M))

This will fill the table with zeros (as I want), and I'm manipulating the table later in the constructor just like I did with the 2D array, so there are no other differences in the 2D bool vector implementation that can make it slower.

Is this the correct way to do this? Or is there a better way?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Hadi Rifaii
  • 23
  • 3
  • 2
    [`std::vector`](https://en.cppreference.com/w/cpp/container/vector_bool) is ... *special* ... Precisely because of its extra processing to compress bits, it doesn't act like a normal `vector` for other element types. – Remy Lebeau May 11 '22 at 23:13
  • If you know at compile time what size container you need, `std::array` has some advantages over `std::vector` in that its contents can have automatic storage duration, i.e. in practice it can place all its stored variables in the stack instead of on the heap. Beyond that, `vector` is a specialization of `vector` that uses one bit per `bool` instead of one byte per `bool`, a tradeoff that sacrifices speed for space savings. – Nathan Pierson May 11 '22 at 23:14
  • My opinion is that the `std::vector` is compressing the data. For example instead of 16 separate integers or uint8_t, it is packing the bits into a single `uint16_t`. The slowness would come from masking the bit (shifting as needed), for testing or insertion. Packing consumes extra time than direct access. – Thomas Matthews May 11 '22 at 23:17
  • 2
    Since the number of rows is fixed, you might consider using `std::array, ALPHABET_SIZE>` instead. And if the `vector` specialization proves to be too slow for you, you can always replace `bool` with `(unsigned) char` or `(u)int8_t` instead. – Remy Lebeau May 11 '22 at 23:20
  • 2
    *"to save some space"* -- Keep in mind that the [space-time tradeoff](https://en.wikipedia.org/wiki/Space–time_tradeoff) is a long-standing design concern in comp sci. ;) – JaMiT May 11 '22 at 23:25
  • 1
    *"Is this the correct way to do this? Or is there a better way?"* -- these questions set up something of a false dichotomy, as they assume that there is a single correct (and best) way to do something. Often, there are multiple correct approaches to accomplish a goal, and the choice between them might depend on how you define "better". You might want to edit your question to ask if this is **a** correct way (instead of **the** correct way) and to add your personal definition of "better". *Or perhaps, would you want to ask **why** the vector is slower?* – JaMiT May 11 '22 at 23:36
  • @OP *but when I tested my program I found that it was much slower* -- This observation is incomplete. Are you running a release, optimized build, or a non-optimized "debug" build? If it's a non-optimized, debug build, then your observation of the code being "slow" is not valid. Any question about the speed of a C++ program must always be accompanied by the compiler options you used to build the program. Too many times, when a questioner turns on the optimizations, all of the concern of the speed of the program is gone, and the question either gets removed, or becomes moot. – PaulMcKenzie May 12 '22 at 06:29

0 Answers0