Реализация битового массива

Я сделал небольшую реализацию массива, которую можно увидеть ниже:

unsigned int uint_size();

class Bitarray1D {
private:
    unsigned int * array_;
    int elements_;
    int bits_;

public:
    Bitarray1D(int bits);

    ~Bitarray1D();

    void size(int& bits) const;

    unsigned int count() const;

    void setAll(int value);

    void set(int index, int value);

    int test(int index) const;

    unsigned int operator [](int index) const;

    void flip(int index);

    std::string to_string() const;

private:
    void init();

};

и некоторые из функций:

void Bitarray1D::init(){
        if (bits_ == 0) throw std::invalid_argument("Can't initialize zero size array");

        int number_of_elements = bits_;
        std::cout << "unsigned int size: " << uint_size() << " bytes" << std::endl;

        elements_ = std::ceil((bits_*1.0)/(uint_size()*1.0));
        array_ = new unsigned int[elements_];
}

int Bitarray1D::test(int index) const {
        if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

        int element = index / uint_size();
        int bit = index % uint_size();

        unsigned int temp_element = array_[element];
        temp_element = temp_element >> bit;

        unsigned int mul = 1;
        temp_element = temp_element & mul;
        return temp_element;
}

unsigned int Bitarray1D::operator [] (int index) const {
        if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

        return test(index);
}

uint_size() - это функция, которая возвращает размер unsigned int в байтах.

Пока это хорошо работает, я хочу реализовать назначение в стиле массива, а именно: bitarray[i] = 1;

В текущей реализации это невозможно. Для этого я понял, что оператор [] в Bitarray должен возвращать «бит-объект» с соответствующими операторами, как показано ниже:

class Bit{
  private:
        unsigned int& element_;
        unsigned int index_;

    int getValue() const{
        // get value of bit
    }
public:
    Bit(unsigned int& element, unsigned int index): element_(element), index_(index){}

    Bit& operator [] (int value){
        return *this;
    }

    Bit& operator = (int value){
          //assign value to the bit
    }

    friend std::ostream& operator<<(std::ostream& os, const Bit& bit){
        os << bit.getValue();
        return os;
    }
};

Эта реализация работает, но имеет две основные проблемы:

  1. Утечка памяти. Для оператора [] в Bitarray чтобы вернуть ссылку на объект Bit, я должен вернуть следующее:

    Bit& Bitarray1D::operator [] (int index) const {
         return *(new Bit(..., ... ));
    }
    
  2. Я мог бы изменить array_ битаррея для хранения массива класса Bit, но тогда вся точка кода Bitarray теряется, что меньше памяти след.

11 голосов | спросил k_kaz 2 J0000006Europe/Moscow 2017, 13:11:16

2 ответа


14

Не записывайте функцию для возврата константы

Вам не нужно uint_size(), так как возвращаемое значение никогда не изменяется (для данной целевой платформы). Вы можете заменить его на

#include <climits>
static const std::size_t uint_bits = CHAR_BIT * sizeof (unsigned int);

Не требуется вызов init()

Конструктор должен полностью инициализировать объект; просто переместите тело init() там.

Использовать целочисленные операции с целыми числами

Вместо того, чтобы использовать std::ceil, чтобы округлить деление, мы можем сделать это в целочисленной арифметике, добавив один меньше делителя до деления:

    elements_ = (bits + uint_bits - 1) / uint_bits;

Учитывая, что мы знаем количество бит, мы всегда можем вычислить количество элементов, когда оно нам нужно; вы можете рассмотреть компромисс между хранением и вычислением elements_.

Соблюдать правило пяти (или правило нуля)

Вы выделяете память в конструкторе, но не предоставляете конструкторы копирования /перемещения, а также оператор присваивания, поэтому вы рискуете двойным delete[]. Самым простым решением является использование стандартного контейнера в качестве хранилища; вы также можете использовать интеллектуальный указатель на хранилище. В крайнем случае вы могли бы управлять своей памятью, но я бы посоветовал это сделать.

Использовать неподписанный тип для индексирования

Вы можете избежать необходимости проверять отрицательные значения индекса, приняв в методе целое число без знака. Я рекомендую std::size_t как обычно используемый для этого стандартный тип.

Возвращаемое значение по возможности

void size(int& bits) const;

лучше писать как

std::size_t size() const;

Моя версия

Рабочий код замены:

#include <climits>
#include <stdexcept>
#include <vector>

class Bitarray1D {
    using Element = unsigned int;

    class Bit {
        Element& element;
        const Element mask;
    public:
        Bit(Element& element, Element mask) : element{element}, mask{mask} {}
        Bit(const Bit& other) : Bit{other.element, other.mask} {}
        operator bool() const { return element & mask; }
        Bit& operator=(bool b) { element = b ? element | mask : element & ~mask; return *this; }
        Bit& operator=(const Bit& other) { return this->operator=(bool(other)); }
    };

    static const std::size_t element_bits = CHAR_BIT * sizeof (Element);

    std::size_t bits;
    std::vector<Element> array;

public:
    Bitarray1D(std::size_t bits);
    ~Bitarray1D() = default;

    std::size_t size() const;

    Bit operator[](std::size_t index);

};

Bitarray1D::Bitarray1D(std::size_t bits)
    : bits{bits},
      array{}
{
    // rounded-up division
    array.resize((bits + element_bits - 1) / element_bits);
}

Bitarray1D::Bit Bitarray1D::operator[](std::size_t index) {
        if (index >= bits)
            throw std::out_of_range("Index out of range");
        return Bit(array[index / element_bits], 1u << (index % element_bits));
}


int main()
{
    Bitarray1D bits{15};
    bits[0] = 0;
    bits[2] = bits[1] = 1;
    return bits[0] + bits[1] + bits[2] != 2;
}
ответил Toby Speight 2 J0000006Europe/Moscow 2017, 13:58:39
8

У меня есть несколько комментариев, поэтому я просто их разбрызгиваю.


Использование ссылочного типа прокси является сложным и может привести к некоторым интересным проблемам. Например, класс, предоставляющий ссылки на прокси-серверы (например, vector<bool>, не может соответствовать требованиям стандарта для контейнера (см. http://www.gotw.ca/publications/mill09.htm ), а также использует auto опасно:

Bitarray1D arr(1);
arr.set(0, 0);
const auto this_isnt_really_a_bool = arr[0];
arr.set(0, 1);
assert(!this_isnt_really_a_bool);  // fails

Однако, если вы планируете использовать ссылку на прокси-сервер, вы должны вернуть его значение , а не по ссылке:

Bit Bittarray1D::operator[](int index) const {
    return Bit(array_[element(index)], offset(index)]);
}

Это устраняет утечку памяти.


Почему вы используете int как тип бит? Что бы вы сделали, если кто-то назвал set с помощью value == 2? Вы случайно установили следующий более высокий бит (и имели неопределенное поведение, если бы это был самый старший бит в элементе)? C ++ имеет тип, который принимает те же значения, что и бит: bool.

Аналогично, вы используете несколько типов для представления размера (вы передаете конструктору int и как bits_ и elements_, вы возвращаете unsigned int из count). Используйте std::size_t; он предназначен для этой цели.


uint_size - не такая хорошая идея. Компиляторы, вероятно, опускают оптимизацию, и опыт читателей будет смущен использованием функции. Вместо этого определите константу:

constexpr std::size_t uint_size = sizeof(unsigned) * CHAR_BITS;

(некоторые люди назовут это kUintSize или UINT_SIZE или аналогичный. В любом случае это не обязательно указывать в заголовке.

Постепенно я не стал бы обязывать использовать unsigned как ваш тип представления. Если вы используете typedef, вы можете настроить профиль, чтобы определить, какой тип максимизирует производительность.

using Repr = unsigned;
// using Repr = std::uint64_t;
// using Repr = unsigned char;

Предположительно, у каждой функции-члена есть следующие строки, которые принимают аргумент index:

    if (index < 0 || index >= bits_) throw std::out_of_range("Index out of range");

    int element = index / uint_size();
    int bit = index % uint_size();

Почему бы не добавить пару частных функций, которые позаботятся об этом:

std::size_t element(std::size_t index) const {
    if (index >= bits_) throw std::out_of_range("Index out of range");
    return index / REPR_BITS;
}
std::size_t offset(std::size_t index) const {
    return index % REPR_BITS;
}

Вы сохраняете как elements_, так и bits_, но вы не разрешаете пользователям изменять размер массива, а elements_, похоже, нигде не используется. Omit elements_.


Почему существует init? У вас есть только один конструктор, и даже если вы добавили другие, вы могли бы делегат .

Я рекомендовал исключить elements_, но если вы этого не сделаете, пожалуйста, инициализируйте его по-другому. Использование плавающей запятой таким образом опасно. Вместо этого инициализируйте его так:

elements_ = (bits_ + REPR_BITS - 1) / REPR_BITS;

Вот как выглядит ваш конструктор.

Bitarray1D::Bitarray1D(std::size_t bits) 
    : array_(new Repr[(bits + REPR_BITS - 1) / REPR_BITS]()),
      bits_(bits) {}

Обратите внимание, что мой код, в отличие от вашего, инициализирует массив значением 0 (new int[5]() value-initializes, new int[5]).


В вашей реализации test многое происходит; вот более простая реализация:

bool Bitarray1D::test(std::size_t index) const {
    return (array_[element(index)] >> offset(index)) & 1u;
}
ответил ruds 2 J0000006Europe/Moscow 2017, 14:12:21

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132