3

次の push_back コードがあるとします。

template <typename T>
void Vector<T>::push_back(const T& item) {

if (_size == _capacity) {
    _capacity = _capacity + (_capacity > 1 ? (_capacity / 2) : 1);
    T* newVec = new T[_capacity];
    memcpy(newVec, _ptr, _size*(sizeof(T)));
    delete [] _ptr;
    _ptr = newVec;
}
_ptr[_size++] = item;
}

ベクターのクラスには次のメンバーが含まれています。

T*  _ptr;
size_t _size;
size_t _capacity;

その実装は安全ですか..？T が多相型であっても、memcpy は正しく機能しますか?

実装を改善する方法についていくつかの提案を聞きたいです。

4

4 に答える 4

8

使用しないでくださいstd::memcpy

std::memcpy単純にコピー可能なオブジェクトでのみ使用できます。それ以外の場合は、未定義の動作です。

ただし、すべての要素を手動でコピーすることはできます。std::copy自明な型に特化している可能性があるため、適切です。

実際には、 の実装では複数の代入を避け、値の型が TriviallyCopyable の場合std::copyなどに一括コピー関数を使用しますstd::memcpy

template <typename T>
void Vector<T>::push_back(const T& item) {
  if (_size == _capacity) {
      size_t new_cap = _capacity > 0 ? 2 * _capacity : 2;    
      T * newVec = new T[new_cap];
      std::copy(_ptr, _ptr + _size, newVec);
      std::swap(_capacity, new_cap);
      std::swap(_ptr, newVec);
      delete[] newVec;
  }
  _ptr[_size++] = item;
}

ベクトルが小さすぎる場合、元の実装では容量が分割されることに注意してください。

その他の改善

（または互換性のあるクラス）を使用するstd::allocatorと、少し簡単になります。を使用.allocateして、メモリを取得.construct(pointer, value)し、実際にオブジェクトを構築.destroyし、それらのデストラクタを呼び出し、.deallocate以前に で作成されたメモリを削除し.allocateます。したがって、単に使用したい場合は、デフォルトの構築可能なオブジェクトは必要ありません.push_back()。

次のコードは、簡単な最小限のスケッチです。reserve()コンストラクターがスローした場合、割り当てられたメモリをtmpクリーンアップする必要があるため、例外セーフではないなど、いくつかの問題があることに注意してください。

template <typename T, class Allocator = std::allocator<T> >
class Vector{
public:
  typedef typename Allocator::pointer pointer;
  typedef typename Allocator::size_type size_type;

  Vector() : _ptr(0), _capacity(0), _size(0){}
  ~Vector() {
    if(_capacity == 0)
      return;
    while(_size > 0)
      pop_back();
    _alloc.deallocate(_ptr, _capacity);
  }

  void reserve(size_type new_cap){
    if(new_cap <= _capacity)
      return;

    // allocate memory
    T * tmp = _alloc.allocate(new_cap);

    // construct objects
    for(unsigned int i = 0; i < _size; ++i){
      _alloc.construct(tmp + i, _ptr[i]); // or std::move(_ptr[i])
    }

    // finished construction, save to delete old values
    for(unsigned int i = 0; i < _size; ++i){
      _alloc.destroy(_ptr + i);
    }

    // deallocate old memory
    _alloc.deallocate(_ptr, _capacity);
    _ptr = tmp;
    _capacity = new_cap;
  }

  void push_back(const T& val){
    if(_size == _capacity)
      reserve(_capacity > 0 ? 2 * _capacity : 1);    
    _alloc.construct(_ptr + _size, val);
    _size++; // since T::T(..) might throw
  }

  void pop_back(){
    _alloc.destroy(_ptr + _size - 1);
    _size--;    
  }

  T& operator[](size_type index){
    return _ptr[index];
  }

private:
  pointer _ptr;
  size_type _capacity;
  size_type _size;
  Allocator _alloc;
};
于 2013-10-26T08:04:03.233 に答える
3

これは安全ではありません。たとえば、これTを行っている場合:

struct T
{
    T* myself;
    T() : myself(this) {}
    void foo() { myself->bar(); }
    void bar() { ... }
};

コンストラクター/デストラクタを呼び出さずにメモリを移動するだけでオブジェクトのメモリ位置を移動したため、myself更新されず、foo後で呼び出すbarと、無効なthisポインタで呼び出されます。

于 2013-10-26T08:06:17.637 に答える
1

Tそれ自体が だったらどうなるか想像してみてくださいvector。

これで、同じバッファーを指す 2 つのベクトルがあり、どちらもバッファーを削除します... 悪い考えです。

（まあ、技術的には、あなたがmemcpy.

于 2013-10-26T08:04:31.477 に答える
0

一般的には安全ではありませんが、C++11 では以下が提供されますstd::is_trivially_copyable。

#include <type_traits>
...
if (std::is_trivially_copyable<T>::value)
    // *can* use memcpy...
于 2013-10-26T08:05:28.097 に答える