C++中vector可以作为map的键值实例代码

前言

先澄清题面：这里的"键值"指的是键（key），即std::map<std::vector<int>, T>这种把std::vector放在第一个模板参数的位置。同时说明，vector作为value当然也可以，那是另一回事，本文主要讲它作为键。

std::map的第三个模板参数是比较器，默认是std::less<Key>，要求Key支持<。std::vector恰好提供了按字典序比较的operator<，所以std::map<std::vector<int>, std::string>可以直接编译，不需要写任何自定义比较器。这一点经常被误解为"必须自己写比较函数"，其实不必。

但"能编译"不等于"适合"。用vector作键有几个必须知道的语义：比较是逐元素的字典序，长度参与比较；每次插入都会复制整个vector；std::unordered_map需要额外的哈希函数，标准库没有为vector提供std::hash特化。本文围绕这几点展开，代码以 C++17 为基准。

一、为什么map能直接接受vector作键

std::map<Key, T, Compare>只要求Compare是一个满足严格弱序的二元谓词。默认的std::less<Key>调用operator<。std::vector的operator<按字典序比较：从头开始逐元素比较，第一个不相等的元素决定大小；若一方是另一方的前缀，则较短的更小。

// 适用于 C++17
#include <map>
#include <string>
#include <vector>

using Path = std::vector<int>;

std::map<Path, std::string> routes;

routes[Path{1, 2, 3}] = "alpha";
routes[Path{1, 2}] = "beta";
routes[Path{2}] = "gamma";

三个键在map中的顺序是{1,2}、{1,2,3}、{2}：{1,2}是{1,2,3}的前缀，所以更小；{2}的首元素 2 大于 1，所以排最后。注意长度不是第一比较项——{9}会排在{1,2,3}之后，因为首元素 9 更大。

C++20 起，vector的比较改由三路比较operator<=>生成，但operator<的语义不变，std::map的写法也不用改。需要 C++20 及以上才谈得上这个变化，C++17 下就是普通的operator<。

二、作为键的语义约束

键在容器内部是常量：map的元素类型是std::pair<const Key, T>，迭代器解引用得到的first是const Key&。因此不存在"插入后修改键"的操作，想改只能删旧插新。这反而消除了"键被改坏导致树结构失效"的风险。

需要留意的是相等与等价的区别。map判断两个键是否相同，用的是" neither is less than the other"，即!(a<b) && !(b<a)。对vector<int>来说，这等价于逐元素相等且长度相同，和operator==一致。但如果自定义了比较器（例如忽略顺序），等价关系就会与==不同，查找时要用同一套比较规则。

另一个约束是键必须可拷贝：map插入时会复制键。对vector来说，复制意味着一次堆分配加元素拷贝。键越长、插入越频繁，这部分开销越明显。

三、完整示例：用路径作键

下面用"节点编号序列"作为键，映射到路径名称。插入、查找、遍历都覆盖到。

// 适用于 C++17
#include <iostream>
#include <map>
#include <string>
#include <vector>

using Path = std::vector<int>;

int main() {
std::map<Path, std::string> routes;

routes[Path{1, 2, 3}] = "alpha";
routes[Path{1, 2}] = "beta";
routes[Path{2}] = "gamma";

// 查找：不要用 operator[]，它会插入不存在的键
auto it = routes.find(Path{1, 2, 3});
if (it != routes.end()) {
std::cout << it->second << '\n'; // alpha
}

// 插入：insert 返回 pair<iterator, bool>
auto result = routes.insert({Path{4, 5}, "delta"});
if (!result.second) {
std::cout << "already exists\n";
}

// 遍历：按键的字典序输出
for (const auto& kv : routes) {
std::cout << kv.first.size() << ": " << kv.second << '\n';
}

// 删除
routes.erase(Path{2});
return 0;
}

routes[Path{1, 2, 3}]这种写法用operator[]，键不存在时会先插入一个空字符串再赋值。如果T没有默认构造函数，operator[]不可用，应改用insert或emplace。只读访问用find或at（C++11 起），后者在键不存在时抛std::out_of_range。

四、性能与替代方案

map的每次比较是 O(k)（k 为向量长度），查找是 O(k log n)。键很长时，比较成本会超过树的层数带来的收益。几种常见替代：

把vector编码成字符串是常见做法，例如用分隔符连接："1,2,3"。风险是分隔符冲突——如果元素本身可能包含分隔符，编码就不再唯一。更稳的是长度前缀编码或定长二进制表示。

unordered_map需要自己提供哈希。标准库只为内置类型和部分标准类型特化了std::hash，std::vector不在其中，直接写std::unordered_map<std::vector<int>, std::string>会编译失败。一个可用的组合哈希如下：

// 适用于 C++17
#include <cstddef>
#include <functional>
#include <unordered_map>
#include <vector>

struct VectorHash {
std::size_t operator()(const std::vector<int>& v) const noexcept {
std::size_t seed = v.size();
for (int x : v) {
seed ^= std::hash<int>{}(x) + 0x9e3779b9u
+ (seed << 6) + (seed >> 2);
}
return seed;
}
};

std::unordered_map<std::vector<int>, std::string, VectorHash> fast_routes;

unordered_map还需要键支持==，vector的逐元素相等正好满足。哈希函数的选取会影响冲突率，但标准不保证任何具体的性能数字，实际效果要在目标数据上测量。

如果键的语义是"集合"而非"序列"（顺序无关），应当先把向量排序再作为键，或者在插入前统一规范化，否则{1,2}与{2,1}会被当成两个不同的键。

常见坑点

1. 直接把vector塞进unordered_map

// ❌ 编译错误：std::hash<std::vector<int>> 不存在
std::unordered_map<std::vector<int>, int> m;
// ✅ 提供自定义哈希
std::unordered_map<std::vector<int>, int, VectorHash> m;

2. 用operator[]做只读查找

// ❌ 键不存在时插入一个默认值，容器变大
if (m[key] == "x") { /* ... */ }
// ✅ 用 find 或 at
auto it = m.find(key);
if (it != m.end() && it->second == "x") { /* ... */ }

3. 以为比较只看第一个元素

// ❌ 只比首元素，{1,9} 与 {1,2} 会被误判为同一个键
bool same = (a.front() == b.front());
// ✅ 交给 vector 的字典序比较，逐元素判等价
bool same = !(a < b) && !(b < a);

4. 插入后试图修改键

// ❌ 键是 const，编译错误
it->first.push_back(4);
// ✅ 删旧插新
auto value = it->second;
m.erase(it);
m[Path{1, 2, 3, 4}] = value;

5. 顺序无关的语义却没有规范化

// ❌ {1,2} 与 {2,1} 被当成两个键
m[Path{1, 2}] = "a";
m[Path{2, 1}] = "b";
// ✅ 插入与查找前都先排序
Path key{2, 1};
std::sort(key.begin(), key.end());
m[key] = "a";

6. 用浮点元素作键

// ❌ 0.1+0.2 与 0.3 不相等，查找失败
std::map<std::vector<double>, int> m;
// ✅ 改用整数（放大到最小单位）或定点表示
std::map<std::vector<long long>, int> m;

7. 自定义比较器不满足严格弱序

// ❌ 用 <= 比较，破坏不可自反性
return a.size() <= b.size();
// ✅ 只用严格小于，并保证可传递
return a.size() < b.size();

8. 忽略键的复制成本

// ❌ 每次插入都复制一个长向量
m[very_long_vector] = value;
// ✅ 用 emplace 原地构造，或改用哈希/编码方案
m.emplace(std::move(very_long_vector), value);

总结

vector作键的可用性来自一个简单的巧合：map要的只是"严格弱序"，而vector的operator<正好提供了字典序。理解这一点后，剩下的判断就都是工程取舍：键有多长、插入多频繁、语义是序列还是集合、要不要哈希。把这几个问题答清楚，选map还是编码成字符串、要不要自定义哈希，自然就有答案。