二维矢量和矢量地图有什么区别？

Question

假设我已经声明

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

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

Answer 1

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

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

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

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

地图的优点是不必密集填充，即您可以在索引 0 和 12902 处拥有某些东西，而无需介于两者之间的所有东西，而且它是经过排序的。如果您不需要排序的属性并且可以使用 c++11，请考虑 std::unordered_map。向量总是密集填充，即大小为 10000，元素 0-9999 存在。

Answer 2

相似的是你访问数据的方式，可以是相同的语法：

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

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

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

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

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

g2[-10].resize(10);

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

Answer 3

举个例子就能明白其中的区别。假设 vector<int> 存储人员的唯一 ID，而 map 将各自的密码存储为密钥。

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

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

二维矢量和矢量地图有什么区别？

What's the difference between 2d vector and map of vector?

c++

dictionary

vector

stdmap

2d-vector