C++：向矢量中的非连续索引赋值？

Question

如果我想声明一个未知大小的向量，则按顺序将值分配给索引5，索引10，索引1，索引100。它在矢量中很容易实现吗？

看来没有简单的方法。原因是如果我初始化一个没有大小的向量，那么如果没有先调用resize（）或者push_back（）来为它分配内存，我就无法访问索引5。但调整大小会清除以前存储在矢量中的值。我可以通过给它一个大小来构建矢量，但我不知道矢量应该有多大。

那么我怎么能不必声明一个固定大小，并仍然访问向量中的非连续索引？

（我怀疑数组会更容易执行此任务）。

Answer 1

调整大小不会清除向量。您可以轻松地做一些事情，如：

if (v.size() <= n) 
     v.resize(n+1); 
    v[n] = 42; 

这样会保留所有的值在向量和使指数n可以访问时加入足够的默认初始化值。

这就是说，如果你不需要所有的索引或连续的内存，你可能会考虑一个不同的数据结构。

Answer 2

整数键和值之间的std :: map不是一个更简单的解决方案吗？向量将需要连续分配内存，所以如果你只使用偶尔的索引，就会“浪费”大量的内存。

Answer 3

resize()不清除以前存储在矢量中的值。
看到this documentation

我还要说，如果这是你需要做那么它可能什么vector可能不是容器为您服务。你有没有考虑使用map也许？

Answer 4

不包含连续值集合的数据结构被称为稀疏或压缩数据结构。看来，这是你正在寻找的。

如果是这种情况，你想要一个稀疏矢量。有一个在boost中实现，请参阅link text

稀疏结构通常用于节省内存。从你的问题描述中可以得知，你实际上并不关心内存的使用，而是关于寻址那些还不存在的元素（你想要一个自动调整大小的容器）。在这种情况下，没有外部依赖关系的简单解决方案如下：

创建一个模板类，该类包含一个向量并将所有向量方法转发给它。如果索引超出范围，请更改您的运算符[]以调整矢量大小。

// A vector that resizes on dereference if the index is out of bounds. 
template<typename T> 
struct resize_vector 
{ 
    typedef typename std::vector<T>::size_type size_type; 
    // ... Repeat for iterator/value_type typedefs etc 

    size_type size() const { return m_impl.size() } 
    // ... Repeat for all other vector methods you want 

    value_type& operator[](size_type i) 
    { 
     if (i >= size()) 
      resize(i + 1); // Resize 
     return m_impl[i]; 
    } 
    // You may want a const overload of operator[] that throws 
    // instead of resizing (or make m_impl mutable, but thats ugly). 

private: 
    std::vector<T> m_impl; 
}; 

正如在其他答案中指出的那样，当矢量调整大小时，元素不会被清除。相反，当通过调整大小添加新元素时，会调用其默认构造函数。因此，您需要知道何时使用此类operator[]可能会返回给您一个默认的构造对象引用。因此，<T>的默认构造函数应该将该对象设置为适合此目的的合理值。例如，如果您需要知道该元素是否先前已被赋值，则可以使用一个定点值。

建议使用std::map<size_t, T>作为解决方案也有其优点，前提是您不介意额外的内存使用，非连续的元素存储和O（logN）查找，而不是O（1）。这一切都归结为您是否想要稀疏表示或自动调整大小;希望这个答案涵盖两个。