Безопасное идиоматическое уничтожение и сжатие в фиксированном, неупорядоченном массиве-владельце - PullRequest
Новая
       29

Безопасное идиоматическое уничтожение и сжатие в фиксированном, неупорядоченном массиве-владельце

0 голосов
/ 22 февраля 2019

Рассмотрим структуру данных, содержащую буфер фиксированного размера, который владеет на месте членами некоторого произвольного нетривиального типа.Буфер неупорядочен, но его содержимое хранится непрерывно, используя фиксированный массив и значение счетчика.Каков современный идиоматический способ C ++ уничтожить элемент в этом массиве и заменить его слот последним элементом массива, чтобы сохранить непрерывность?Я особенно обеспокоен тем, чтобы убедиться, что элемент должным образом разрушен, а замена правильно и эффективно перемещена.К сожалению, std::vector здесь не вариант.

Вот что я могу придумать от руки: 

void destroy_replace(
    std::array<arbitrary, 20>& arr, 
    size_t& count,
    size_t index)
{
    SOME_ASSERT_MACRO(index < count);
    std::destroy_at(std::addressof(arr.at(index)));
    arr[index] = std::move(arr.at(count - 1));
    --count;
}

Это правильно?Особенно std::destroy_at?

Нужен ли ход?Могу ли я сделать это как конструктор перемещения с новым размещением?

Правильный ли порядок операций в отношении гарантий исключений?

Ответы [ 3 ]

0 голосов
/ 22 февраля 2019

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

0 голосов
/ 22 февраля 2019

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

template<class T, std::size_t N>
struct pseudo_array {
  using raw = std::aligned_storage_t<sizeof(T), alignof(T)>;
  std::array<raw, N> data;
  std::size_t highwater = 0;
  void erase( std::size_t i ) {
    std::launder( (T*)(data.data()+i) )->~T();
    --highwater;
    if (i != highwater) {
       auto* ptr_last = std::launder(  (T*)(data.data()+highwater) );
       ::new( (void*)(data.data()+i) ) T( std::move(*ptr_last ) );
       ptr_last->~T();
    }
  }
  // add const version
  T& operator[](std::size_t i) {
    return *std::launder( (T*)(data.data()+i) );
  }
  std::size_t size() const { return highwater; }
  template<class...Args>
  T& emplace( Args&&...args ) {
    void* where = (void*)(data.data()+highwater);
    T* ptr_elem = ::new(where) T(std::forward<Args>(args)...);
    ++highwater;
    return *ptr_elem;
  }
  // Care taken to keep invariants true while we destroy
  ~pseudo_array() {
    while(highwater > 0) {
      --highwater;
      std::launder( (T*)(data.data()+highwater) )->~T();
    }
  }
};

альтернативное стирание: 

 void erase( std::size_t i ) {
   auto* ptr_last = std::launder(  (T*)(data.data()+highwater-1) );
   auto* ptr_target = std::launder( (T*)(data.data()+i) );
   if (ptr_last!=ptr_target) {
     *ptr_target = std::move(*ptr_last);
   }
   --highwater; // this goes before dtor, in case dtor throws
   ptr_last->~T();
 }
0 голосов
/ 22 февраля 2019

Вы должны использовать новый конструктор перемещения, так как оператор присваивания разрушенного объекта не определен.Если у вас нет такого конструктора, вы можете прибегнуть к конструктору по умолчанию, а затем к вашему назначению перемещения, но должен быть создан объект после std::destroy_at.

Перемещение необходимо для приведения к ссылке на rvalue, как .at результат - ссылка на lvalue.

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

...