C++中存储0-9数字序列，如何选择内存浪费最少的数据结构？

Great question! Let's break this down—since digits 0-9 only need 4 bits each (2⁴=16 covers all values from 0 to 15, which is more than enough), your goal is to pack these 4-bit chunks as tightly as possible to eliminate the memory waste from your original vector<bitset<4>> approach (where each 4-bit bitset gets padded to 1 full byte, same as a char).

Here are the most efficient approaches, ordered by practicality and memory efficiency:

1. Manual Packing into Fixed-Size Primitives (Best Balance of Memory & Control) #

The simplest way to cut memory usage in half is to pack two 4-bit digits into a single 8-bit byte (using uint8_t from <cstdint>). This way, each byte stores two digits, reducing total memory to ~50% of a string or your original vector<Digit>.

You'll need helper functions to pack and unpack the digits, but this gives you full control with minimal overhead:

#include <vector>
#include <cstdint>
#include <stdexcept>

// Pack a list of 0-9 digits into a vector of uint8_t (2 digits per byte)
void pack_digits(const std::vector<int>& digits, std::vector<uint8_t>& packed_out) {
    packed_out.clear();
    packed_out.reserve((digits.size() + 1) / 2); // Preallocate space

    for (size_t i = 0; i < digits.size(); i += 2) {
        uint8_t byte = 0;
        // Validate input (ensure digits are 0-9)
        if (digits[i] < 0 || digits[i] > 9) {
            throw std::invalid_argument("Digits must be between 0 and 9");
        }
        // Store first digit in the high 4 bits
        byte |= static_cast<uint8_t>(digits[i]) << 4;

        // If there's a second digit, store it in the low 4 bits
        if (i + 1 < digits.size()) {
            if (digits[i+1] < 0 || digits[i+1] > 9) {
                throw std::invalid_argument("Digits must be between 0 and 9");
            }
            byte |= static_cast<uint8_t>(digits[i+1]);
        }

        packed_out.push_back(byte);
    }
}

// Unpack a vector of uint8_t back into a list of digits
void unpack_digits(const std::vector<uint8_t>& packed, size_t original_digit_count, std::vector<int>& digits_out) {
    digits_out.clear();
    digits_out.reserve(original_digit_count);

    for (size_t i = 0; i < packed.size(); ++i) {
        uint8_t byte = packed[i];
        // Extract high 4 bits (first digit)
        digits_out.push_back(static_cast<int>((byte >> 4) & 0x0F));
        
        // Extract low 4 bits only if we haven't reached the original count
        if (digits_out.size() < original_digit_count) {
            digits_out.push_back(static_cast<int>(byte & 0x0F));
        }
    }
}

Why this works: #

• A uint8_t is exactly 1 byte, so no padding or wasted space per digit pair.
• For N digits, total memory is ceil(N / 2) bytes—half the size of a string (which uses 1 byte per digit).

If you want even tighter packing (e.g., 16 digits per 64-bit word), you can use uint64_t instead of uint8_t—this reduces the number of elements in the vector, which can help with cache performance, but adds a tiny bit of complexity to the packing logic.

2. Use std::vector<bool> (Extreme Memory Efficiency, But Caveats) #

std::vector<bool> is a special container that stores bits instead of bytes—each element is 1 bit. To store a 4-bit digit, you'll use 4 consecutive bits per digit. This gives the same memory usage as the manual packing approach (ceil(N*4/8) = ceil(N/2) bytes), but you don't have to write packing logic.

However, there are trade-offs:

• vector<bool> uses a bitwise storage model, so accessing individual digits requires calculating bit positions, which is slower than direct byte access.
• Its iterators are not standard (they act as proxies), which can cause compatibility issues with some algorithms.

Example usage:

#include <vector>
#include <stdexcept>

void pack_to_vector_bool(const std::vector<int>& digits, std::vector<bool>& bits_out) {
    bits_out.clear();
    bits_out.reserve(digits.size() * 4);

    for (int digit : digits) {
        if (digit < 0 || digit > 9) {
            throw std::invalid_argument("Digits must be between 0 and 9");
        }
        // Store the digit's 4 bits (MSB first)
        bits_out.push_back((digit >> 3) & 1);
        bits_out.push_back((digit >> 2) & 1);
        bits_out.push_back((digit >> 1) & 1);
        bits_out.push_back(digit & 1);
    }
}

void unpack_from_vector_bool(const std::vector<bool>& bits, std::vector<int>& digits_out) {
    digits_out.clear();
    digits_out.reserve(bits.size() / 4);

    for (size_t i = 0; i < bits.size(); i += 4) {
        int digit = 0;
        digit |= bits[i] << 3;
        digit |= bits[i+1] << 2;
        digit |= bits[i+2] << 1;
        digit |= bits[i+3];
        digits_out.push_back(digit);
    }
}

3. boost::dynamic_bitset (Better Than vector<bool>, But Requires Boost) #

If you're able to use the Boost library, boost::dynamic_bitset is a more robust alternative to std::vector<bool>. It provides a cleaner API for bitwise operations, standard iterators, and avoids some of the quirks of vector<bool>.

Example:

#include <boost/dynamic_bitset.hpp>
#include <vector>
#include <stdexcept>

boost::dynamic_bitset<> pack_with_boost(const std::vector<int>& digits) {
    boost::dynamic_bitset<> bits(digits.size() * 4);

    for (size_t i = 0; i < digits.size(); ++i) {
        int digit = digits[i];
        if (digit < 0 || digit > 9) {
            throw std::invalid_argument("Digits must be between 0 and 9");
        }
        // Set each of the 4 bits for the digit
        for (int j = 0; j < 4; ++j) {
            bits.set(i*4 + (3-j), (digit >> j) & 1);
        }
    }
    return bits;
}

std::vector<int> unpack_with_boost(const boost::dynamic_bitset<>& bits) {
    std::vector<int> digits(bits.size() / 4);

    for (size_t i = 0; i < digits.size(); ++i) {
        int digit = 0;
        for (int j = 0; j < 4; ++j) {
            digit |= bits[i*4 + (3-j)] << j;
        }
        digits[i] = digit;
    }
    return digits;
}

Why Your Original bitset<4> Approach Is Less Efficient #

std::bitset<4> is a fixed-size template, and compilers will pad it to the smallest addressable unit (usually 1 byte) for alignment. This means each bitset<4> takes up 1 full byte—wasting 4 bits per digit. A vector<bitset<4>> for N digits uses N bytes, which is the same as a string (where each character is 1 byte). The packing approaches above cut this in half.

内容的提问来源于stack exchange，提问作者Muhammad Magdi