是否有一个C++容器,具有合理的随机访问,从不调用元素类型的复制构造函数?

我很肯定,这里的答案是相当强调的 “没有” . 根据你的定义, resize()

你可能想研究一下 boost::ptr_vector<T> . 因为您正在插入指针,所以不必担心复制。但这需要动态分配所有对象。

std::vector<T*> ,如果无法复制元素并且在其他位置手动管理其内存。

std::vector< std::shared_ptr<T> > 可能更合适。

另外还有 Boost Pointer Container library ,它为指针的异常安全处理提供容器。

deque :性能良好。

标准上说 当大多数插入和删除发生在序列的开头或结尾时,选择的数据结构”(23.1.1)。在您的例子中,所有的插入和删除都发生在末尾,满足使用的标准 德克 .

http://www.gotw.ca/gotw/054.htm 有一些关于如何度量性能的提示,尽管您可能有一个特定的用例,所以这就是您应该度量的。

德克 事实上不是,“我不知道有多快 德克 德克 “从不复制元素”,但它确实从其他对象复制和构造元素。

template <typename T>
struct C {
    vector<shared_array<T> > blocks;
    vector<T*> elements; // lazy, to avoid needing deque-style iterators through the blocks.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        if (n <= elements.size()) { /* exercise for the reader */ }
        else {
            boost::shared_array<T> newblock(new T[elements.size() - n]);
            blocks.push_back(newblock);
            size_t old = elements.size();
            // currently we "leak" newblock on an exception: see below
            elements.resize(n);
            for (int i = old; j < n; ++i) {
                elements[i] = &newblock[i - old];
            }
    }
    void clear() {
        blocks.clear();
        elements.clear();
    }
};

德克 ,但避免任何需要复制类型T的操作。

编辑:想想看,我的“读者练习”在有人这样做的情况下是不太正确的 resize(10); resize(20); resize(15); . 不能半删除数组。所以如果你想正确复制容器 resize() 语义,立即销毁多余的元素,然后必须单独分配元素(或熟悉新的放置方式):

template <typename T>
struct C {
    deque<shared_ptr<T> > elements; // or boost::ptr_deque, or a vector.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        size_t oldsize = elements.size();
        elements.resize(n);
        if (n > oldsize) {
            try {
                for (size_t i = oldsize; i < n; ++i) {
                    elements[i] = shared_ptr<T>(new T());
                }
            } catch(...) {
                // closest we can get to strong exception guarantee, since
                // by definition we can't do anything copy-and-swap-like
                elements.resize(oldsize);
                throw;
            }
        }
    }
    void clear() {
        elements.clear();
    }
};

更好的代码,不太热衷于内存访问模式(但是,我不清楚性能是否是一个问题,因为您担心 .)

正如您所发现的,所有标准容器都与您的要求不兼容。如果我们可以做一些额外的假设,那么编写自己的容器就不会太难了。

• resize 总是用比以前更多的数字来调用,而不是更少。
• 这对我来说是可以的 调整大小 使容器比要求的大;在容器的末端构造一些未使用的物体是可以接受的。

开始吧。我把许多细节留给你。

class C<T> { 
  C();
  ~C() { clear(); }

  T& operator[](int i) // must have reasonably sane time constant 
  {
      return blocks[i / block_size][i % block_size];
  }

    // expand the container by default constructing elements in place. 
  void resize(int n) // only way anything is added. 
  {
      for (int i = (current_size/block_size)+1; i <= n/block_size;  ++i)
      {
          blocks.push_back(new T[block_size]);
      }
      current_size = n;
  }

  void clear()
  {
      for (vector<T*>::iterator i = blocks.begin();  i != blocks.end();  ++i)
          delete[] *i;
      current_size = 0;
  }

  C<T>::iterator begin(); 
  C<T>::iterator end(); 
private:
  vector<T*> blocks;
  int current_size;
  const int block_size = 1024; // choose a size appropriate to T
} 

另外,如果有人问你为什么要这样做,告诉他们你需要一个数组 std::auto_ptr . 那应该是个好笑话。

所有标准容器都需要可复制的元素。至少是因为push\u back和insert复制了传递给它们的元素。我不认为你能逃脱std::deque,因为即使它的resize方法也需要复制参数来填充元素。

shared_ptr 或者各种各样的 boost pointer containers 可以让它更容易。

intrusive containers ?

否则,如果你认为任何一个都不适合你的需要,那么你可以试着用你自己的容器来做你想做的事情。(或者做更多的调查,看看是否有人做过这样的事。)

您不应该根据容器处理内存的方式来选择容器。例如,deque是一个双端队列,所以您应该只在需要双端队列时使用它。

如果调整大小,几乎每个容器都会分配内存!当然,你可以通过打电话预先改变容量 vector::reserve

显然,如果你超过了你的能力,仍然会有一个分配。

看看 ::boost::array . 它不允许在创建容器后调整容器的大小,但它从不复制任何内容。

两者兼得 resize ::std::deque 因为我想在某些情况下它可以复制。如果你真的需要调整大小,我会编码你自己的deque一样的容器。因为要调整大小而不复制,唯一的方法就是拥有一个像这样的页面系统 *标准::德克 使用。

at ::std::vector 和 它们的连续内存布局,即使它仍然可以相当快。