Максимальный размер массива с нормальным интерфейсом STL, похожий на boost :: array - PullRequest
0 голосов
/ 25 марта 2011

Есть ли класс в boost, похожий на массив, который является POD-подобным типом с массивом, но предусматривает переменное количество элементов в контейнере.То есть я хочу сказать, что массив содержит не более 10 элементов, но может содержать от 0 до 10 элементов в любой данный момент.

boost::array, к сожалению, фиксирует size() к константе N, поэтомуэто не может работать как капля в замене вектора.В частности, я бы хотел, чтобы читатели структуры не знали, что это статический массив, они могут использовать begin() и end(), как и любой другой контейнер.

Очевидно, что push_back() придется проходить черезисключение, если оно превысит емкость.

Было бы предпочтительным что-то уже в boost.

ПРИМЕЧАНИЕ: это должно быть POD-подобным тип данных.Для ясности, весь массив, подобный объекту, включая содержимое (которые сами будут POD-подобными типами), должен быть POD-подобным.Это для сериализации / копирования (и для производительности, связанной с этой сериализацией / копированием).

Под POD-подобным я подразумеваю:

  • имеет постоянный размер времени компиляции
  • может быть безопасно memcpy'd

Для тех, кто говорит это не может работать или невозможно .В этом нет ничего гениального.boost::array - это POD-подобный тип.Все, что нужно, это добавить одно дополнительное поле для текущего размера, чтобы превратить его в то, что я хочу.Я ищу реализацию, которая уже существует (и поэтому должным образом протестирована / поддерживается).

Ответы [ 6 ]

2 голосов
/ 25 марта 2011

Проблема (вероятно) в инициализации.Как вы инициализируете размер, если это POD?Как вы применяете инвариантный размер () <= max_size? </p>

Технически было бы легко что-то определить, но будет ли это полезно или безопасно - это другой вопрос.Почему бы вам просто не использовать boost :: array и сохранить текущий размер в качестве отдельной переменной?

- James Kanze

1 голос
/ 25 марта 2011

Более близкая вещь, о которой я знаю, была бы llvm::SmallVector<T,N>, однако она немного сложнее, поскольку она использует динамически выделяемое хранилище, когда размер превышает N (он также копирует существующие элементы, поскольку хранилище гарантированно будет смежным) .

Я не думаю, что такой контейнер будет сложно реализовать, особенно если использовать boost::array в качестве бэкэнда. Достаточно простой обертки, чтобы поддерживать размер и перемещать предметы (например, используя код vector).

1 голос
/ 25 марта 2011

Вы говорите "это должен быть тип данных POD".Ваша коллекция не должна быть POD?

Если тип данных - POD, то std::vector предоставляет необходимую вам функциональность, и многие реализации оптимизируют семантику копирования / перемещения, когда данные являются POD.

Зачем вам нужно заменить вектор?

Чтобы ответить на вопрос напрямую, хотя: я сомневаюсь, что такой класс в boost, как vector (поддержание размера), уже достигает цели, и поэтому они не будут рассматривать реальную необходимостьдля этого.boost::array не имеет концепции другого размера и емкости.

Вы можете легко написать свой собственный класс-оболочку для вектора или Boost :: array для выброса, если он превысил установленную вами емкость.

Теперь, если вы собираетесь реализовать это, наиболее вероятным подходом будет класс, который содержит вектор или массив надстроек или обычный массив, а затем реализует все ваши функции.Я бы сказал, что это интуитивно понятно, но может быть более умное решение перегрузить распределитель, вместо того чтобы внутренне удерживать boost :: array и использовать его для «выделения» вашего вектора.Если ваш распределитель исчерпал емкость (потому что его внутренний массив заполнен), вы бросаете (вероятно, должно быть bad_alloc).Затем пользователи просто используют класс как вектор и могут вызывать все его функции, но вы бросите, если они попытаются увеличить вектор выше его размера.

Из-за природы вектора ваш распределитель не должен работать каккуча, где вы освобождаете определенные объекты.Вы просто будете поддерживать непрерывный буфер.

Что касается проблемы POD или почти POD, то фактические данные в векторе гарантированно являются непрерывным буфером, а внутри вашего распределителя используется boost :: array, так чтоэто будет смежно.Если вы хотите что-то для сериализации, тогда boost :: serialize уже будет правильно работать с векторами.

Вся коллекция, контейнер и содержимое должны быть единым блоком памяти фиксированного размера: определяется при компиляции.время

Ваш распределитель может выглядеть так:

typename< typename T, size_t SIZE >
class Allocator
{
    struct Data
    {
        size_t num_used;
        T[SIZE] data;
    } d;

public:
    // implement allocator's methods
};

Реализация эти

0 голосов
/ 21 марта 2015

Мне нужно что-то подобное, мотивация была производительность, так как локальность кэша явно лучше, чем в динамически размещенном векторе.

Я создал очень простой пользовательский класс, чтобы сделать это для меня.

#pragma once
#include <boost/array.hpp>

template<class T, class IndexType, IndexType MaximumSize>
class StaticVector : public boost::array<T, MaximumSize>
{
  IndexType count;
public:
  StaticVector() : count(0) {}
  inline void add(const T& value)
  {
    if (this->full())
      throw std::runtime_error("Can't add (size = %d)\n", MaximumSize);
    (*this)[this->count] = value;
    this->count++;
  }

  inline void addDirty()
  {
    if (this->full())
      throw std::runtime_error("Can't add, container full.");
    this->count++;
  }

  inline void remove(IndexType index)
  {
    if (this->count > 1)
      (*this)[index] = (*this)[count - 1];
    this->count--;
  }

  inline void clear() { this->count = 0; }
  inline IndexType size() const { return this->count; }
  inline bool empty() const { return this->count == 0; }
  inline bool full() const { return this->count == MaximumSize; }
  inline const T& back() const { return (*this)[this->count - 1]; }
  inline T& back() { return (*this)[this->count - 1]; }

  inline typename boost::array<T, MaximumSize>::iterator  end()       { return this->elems + count; }
  inline typename boost::array<T, MaximumSize>::const_iterator  end() const { return this->elems + count; }
  inline typename boost::array<T, MaximumSize>::const_iterator cend() const { return this->elems + count; }
};
0 голосов
/ 25 марта 2011

Еще одна альтернатива (если вас не беспокоит RYO) - это использовать boost::optional<T> для массива, например:

boost::array<boost::optional<int>, 10>

Преимущество вышеописанного состоит в том, что вы можете протестировать каждую запись, чтобы увидеть, была ли она установлена ​​или нет, вместо использования некоторого состояния значения для неинициализированного. Это по-прежнему должно позволять прямую memcopy объекта (будь то стек или динамически размещается).

0 голосов
/ 25 марта 2011

POD обозначает простые старые данные. «Простая старая структура данных в C ++ - это агрегатный класс, который содержит только PODS в качестве членов, не имеет пользовательского деструктора, пользовательского оператора назначения копирования и нестатических членов типа указатель на член». По определению, все, что может быть изменено во время выполнения, не может быть POD.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...