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是合适的，因为它可能专门用于琐碎的类型：

在实践中，std::copy避免多次赋值并使用批量复制功能的实现，例如std::memcpy如果值类型是 TriviallyCopyable

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它本身是 a会发生什么vector。

现在你有两个指向同一个缓冲区的向量，它们都会删除缓冲区......坏主意。

（好吧，从技术上讲，你的那一刻是未定义的行为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 回答