Класс c++ шаблон для массивов переменной длины с максимальным размером для хорошего кэша


Для моей проблемы, увидеть это переполнение стека вопрос: https://stackoverflow.com/questions/49577746/is-there-standard-c-template-class-for-variable-length-arrays-with-maximum-siz

Мне нужен массив, который хранит свои элементы встроенные в язык C++. Массив должен быть переменного размера, но до определенного максимума. Большинство таких массивов небольшие, поэтому он будет тратить на 64-битных архитектурах использовать size_t, так как размер массива везде. Код здесь:

#include <stdexcept>
#include <algorithm>
#include <stdlib.h>

template<class C, class sz_t, sz_t maxsz> class inlinearray {
  private:
    typedef C value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef value_type *iterator;
    typedef const value_type *const_iterator;
    typedef sz_t size_type;
    typedef std::ptrdiff_t difference_type;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    sz_t sz;
    union {
      C realarray[maxsz]; // for correct alignment
      char array[maxsz*sizeof(C)];
    };
  public:
    inlinearray()
    {
      sz = 0;
    }
    ~inlinearray(void)
    {
      clear();
    }
    void clear(void)
    {
      sz_t i;
      for (i = 0; i < sz; i++)
      {
        data()[i].~C();
      }
      sz = 0;
    }
    template<class sz2_t, sz2_t maxsz2> inlinearray(inlinearray<C,sz2_t,maxsz2> that)
    {
      size_t i;
      sz = that.sz;
      for (i = 0; i < sz; i++)
      {
        push_back(that[i]);
      }
    }
    template<class sz2_t, sz2_t maxsz2> void operator=(inlinearray<C,sz2_t, maxsz2> val2)
    {
      swap(val2);
    }
    void fill(const C& val)
    {
      std::fill_n(begin(), size(), val);
    }
    C &operator[](sz_t i) noexcept
    {
      return data()[i];
    }
    constexpr const C &operator[](sz_t i) const noexcept
    {
      return data()[i];
    }
    C at(sz_t i)
    {
      if (i >= sz)
      {
        throw std::out_of_range("inlinerray::at() out of range");
      }
      return data()[i];
    }
    constexpr const C at(sz_t i) const
    {
      if (i >= sz)
      {
        throw std::out_of_range("inlinerray::at() out of range");
      }
      return data()[i];
    }
    void push_back(const C &c)
    {
      if (sz >= maxsz)
      {
        abort();
      }
      new (data()+sz) C(c);
      sz++;
    }
    void pop_back() noexcept
    {
      data()[sz-1].~C();
      sz--;
    }
    template <class sz2_t, sz2_t maxsz2> void swap(inlinearray<C, sz2_t, maxsz2> &that)
    {
      if (that.sz > maxsz)
      {
        abort();
      }
      if (sz > that.maxsz)
      {
        abort();
      }
      std::swap_ranges(begin(), end(), that.begin());
      std::swap(sz, that.sz);
    }
    constexpr sz_t size(void) const noexcept { return sz; }
    constexpr sz_t max_size(void) const noexcept { return maxsz; }
    constexpr bool empty() const noexcept { return sz == 0; }
    C *begin() noexcept { return data(); }
    C &front() noexcept { return data()[0]; }
    C &back() noexcept { return sz == 0 ? data()[0] : data()[sz - 1]; }
    constexpr const C &back() const noexcept { return sz == 0 ? data()[0] : data()[sz - 1]; }
    C *end() noexcept { return data() + sz; }
    C* data() noexcept { return reinterpret_cast<C*>(array); }
    const C* data() const noexcept { return reinterpret_cast<const C*>(array); }
    const C *begin() const noexcept { return data(); }
    const C *end() const noexcept { return data() + sz; }
    const C *cbegin() const noexcept { return data(); }
    const C *cend() const noexcept { return data() + sz; }
    reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
    reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
    const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
};

Теперь, я должен что-то улучшить в этом коде? Одним из очевидных улучшений можно было бы добавить поддержку для более "удаленных" данных, хранящихся через указатель на массив, чтобы сделать максимальный размер неограничен.

Я не очень хорошо знаком с C++ (в основном программистов), так что я может быть не в курсе всех особенностей языка и закидоны.



1288
4
задан 30 марта 2018 в 06:03 Источник Поделиться
Комментарии
2 ответа

Вы можете иметь проблемы с C в союзе, если это не тривиально (т. е. он имеет какие-либо конструкторы/деструкторы/назначение операторов).

От n4727: Статьи 12.3 Союза


если любой не-статической функции-члена профсоюза имеет нетривиальный конструктор по умолчанию (15.1), конструктор копирования (15.8), конструктор перемещения (15.8), копию оператор присваивания (15.8), двигаться оператор присваивания (15.8), или деструктор (15.4), соответствующая функция-член Союза должны быть пользователем, или это будет безоговорочно удаляться (11.4.3) для Союза.

Пример приведен:


Пример: рассмотрим следующую Союза:

 union U {
int i;
float f;
std::string s;
};


Так как СТД::строка (24.3) объявляет нетривиальные версии все специальные функции-члены, У будет безоговорочно удаляться конструктор по умолчанию, копировать/перемещать конструктор копирования/перемещения оператора присваивания и деструктор. Использовать U, некоторые или все эти функции-члены должны быть пользователем. — конец примера

Комментарий Код:

В C и C++ встроенный массив разрушается в обратном порядке. Ваш деструктор вызывает понятно, что уничтожает их в стандартном порядке.

void clear(void)
{
sz_t i;
for (i = 0; i < sz; i++)
{
data()[i].~C();
}
sz = 0;
}

Хотя не технически неправильно (можно определить семантику для вашего класса). Было бы неплохо, если бы поведение было так же, как обычный массив (и std::вектор с std::массив и т. д.).

Это очень длинная строка:

template<class sz2_t, sz2_t maxsz2> inlinearray(inlinearray<C,sz2_t,maxsz2> that)

Обычно люди нарушают эти две строки. Один для шаблона информация и планы развития информационной функции:

template<class sz2_t, sz2_t maxsz2>
inlinearray(inlinearray<C,sz2_t,maxsz2> that)

Теперь, когда она короткая. Я вижу, что вы передаете по значению. Это означает, что вы создаете копию параметра. Лучше, если вы прошли константной.

template<class sz2_t, sz2_t maxsz2>
inlinearray(inlinearray<C,sz2_t,maxsz2> const& that)
// ^^^^^^

Это выглядит как ошибка:

  sz = that.sz;            // You set the size here.
for (i = 0; i < sz; i++)
{
push_back(that[i]); // But does this not increment the size.
} // Looks like the resulting size is 2*this.sz

В для петли, вы можете объявить переменную в строку как часть для.

  size_t i;
for (i = 0; i < sz; i++)

Проще написать так:

  for (size_t i = 0; i < sz; ++i) // Prefer pre-increment

Примечание. Предпочтительнее использовать пре-инкремент, когда это возможно. Это потому, что это обычно самый эффективный вариант увеличения (на не Pod типов). Это позволяет менять тип базового объекта без того, чтобы посмотреть и убедиться, что вы были использованияконтактная правильный шаг.

Например. Цикл переменной может быть целым числом. Но в будущем мейнтейнер может изменить его, чтобы быть итератор. Если вы воспользовались пре-инкремента последовательно, то оно всегда будет самый эффективный вариант. Если вы используете пост инкремент, то теперь вы 'может' иметь некоторое снижение производительности.

Я хотел бы отметить, что вы не реализовали семантику перемещения. Сейчас вы не можете переехать всей конструкции в целом (нет указателей). Но вы могли бы потенциально переместить данные элементы C. Это может быть гораздо более эффективным (вспомните inlinearray<std::vector<int>, int, 12>).

В C++ (в отличие от C) мы на месте & и * рядом с типом.

 C&  operator[](sz_t i) noexcept
^^^^

Это происходит потому, что информация тип имеет гораздо большее значение в C++ и дополнительный символ передает информацию о типе.

Ваш operator[] возвращают ссылки, почему at() функции не возвращают ссылается?

C at(sz_t i)
constexpr const C at(sz_t i) const

Сухой код:

C at(sz_t i)
{
// This following bit of code.
if (i >= sz)
{
throw std::out_of_range("inlinerray::at() out of range");
}
return data()[i];
}
constexpr const C at(sz_t i) const
{
// Looks exactly like this bit of code.
if (i >= sz)
{
throw std::out_of_range("inlinerray::at() out of range");
}
return data()[i];
}

У вас есть стандартный скопировать в массив:

void push_back(const C &c)

Но вы должны также включить семантику перемещения по добавлению ценности.

void push_back(const C& c);        // Copy
void push_back(C&& c); // Move
template<typename... Args>
void emplace_back(Args...&& args); // Build in place using constructor.

Вы можете определить свои методы begin()/end() для С точки зрения итератора.

C *begin() noexcept { return data(); }

Вероятно, следует определить как:

using iterator = C*;

iterator begin() noexcept { return data(); }

Это отделяет реализацию от конкретного типа и позволяет изменить базовый тип в будущем, не беспокоясь о пользователях код изменения кода.

Я, как правило, группы все итератор вызовы вместе. Не соединять их с другими звонками.

5
ответ дан 30 марта 2018 в 06:03 Источник Поделиться

Мартин был достаточно тщательный. У меня есть две вещи, чтобы добавить про синтаксис c++.

Во-первых, предпочитают using за typedef. Это легче читать, и более гибкий. Вместо

typedef C value_type;

ты пишешь

using value_type = C;

Это работает с шаблонами тоже.

Во-вторых, пишите const и другие модификаторы после типа их изменить. Вместо

const value_type *ptr;

ты пишешь

value_type const* ptr;

Есть несколько преимуществ, самое главное все ошибки, которые были у меня с бывшим того, что не появляются в последнем. Например:

using pointer = value_type*;
const pointer ptr;

ptr не const value_type*как бы вы с подмойся, а value_type* const. Таким образом, он сам указатель является константой, а не данные, на которые указывают. С помощью того, я предлагаю, это было бы очевидно:

pointer const ptr;

0
ответ дан 31 марта 2018 в 02:03 Источник Поделиться