c++ - 二维向量和向量图有什么区别？

Question

假设我已经宣布

map< int , vector<int> > g1;
vector< vector<int> > g2;

这两者之间有什么相同点和不同点？

Answer 1

相似之处在于您访问数据的方式，它可以是相同的语法：

std::cout << g1[3][2] << std::endl;
std::cout << g2[3][2] << std::endl;

主要区别如下：向量的映射不必包含所有索引。然后，例如，您的地图中只有 3 个向量可以使用键 '17'、'1234' 和 访问13579：

g2[17].resize(10);
g2[1234].resize(5);
g2[13579].resize(100);

如果您想要与向量向量相同的语法，则您的主向量中至少需要有 13579 个向量（包括 13576 个空向量）。但这会占用内存中大量未使用的空间。

此外，在您的地图中，您还可以使用否定键访问您的向量（这在向量的向量中是不可能的）：

g2[-10].resize(10);

在这个明显的高差异之后，数据的存储是不同的。向量分配连续的内存，而映射存储为树。向量中的访问复杂度是O(1)，而它O(log(n))在地图中。我邀请您学习一些有关 C++ 容器的教程，以了解所有差异以及使用它们的常用方法。

Answer 2

它们是根本不同的。虽然您可以同时执行g2[0]和g1[0]，但行为却大不相同。假设索引 0 处没有任何内容，则std::map默认构造一个新的 value_type，在本例中为向量，并返回一个引用，而std::vector具有未定义的行为，但通常是 segfaults 或返回垃圾。

它们在内存布局方面也完全不同。虽然std::map由红黑树支持，但std::vector在内存中是连续的。因此，插入映射总是会导致内存中某处的动态分配，而向量将被调整大小以防超出其当前容量。但是请注意，向量的向量在内存中是不连续的。第一个向量，它本身在内存中是连续的，由向量组成，这些向量在数据方面大致如下所示：

struct vector 
{
    T* data;
    size_t capacity;
    size_t size;
};

其中每个向量在 处拥有其动态内存分配data。

该地图的优点是不必人口稠密，即您可以在索引 0 和 12902 处有一些东西，而没有介于两者之间的所有东西，而且它是排序的。如果您不需要 sorted 属性并且可以使用 c++11 考虑std::unordered_map. 该向量始终是密集填充的，即在大小为 10000 时，存在 0-9999 个元素。

Answer 3

通过示例，您可以了解其中的区别。假设vector<int>存储人员的唯一 ID，并将map相应的密码存储为密钥。

map< int , vector<int> > listOfPeopleAtRespectivePinCode;
vector< vector<int> > bunchOfGroupsOfPeople;

显然，map能够关联键和值（这里是值列表），同时vector可以有效地存储一堆数据。