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

前言先澄清题面这里的键值指的是键key即std::mapstd::vectorint, T这种把std::vector放在第一个模板参数的位置。同时说明vector作为value当然也可以那是另一回事本文主要讲它作为键。std::map的第三个模板参数是比较器默认是std::lessKey要求Key支持。std::vector恰好提供了按字典序比较的operator所以std::mapstd::vectorint, std::string可以直接编译不需要写任何自定义比较器。这一点经常被误解为必须自己写比较函数其实不必。但能编译不等于适合。用vector作键有几个必须知道的语义比较是逐元素的字典序长度参与比较每次插入都会复制整个vectorstd::unordered_map需要额外的哈希函数标准库没有为vector提供std::hash特化。本文围绕这几点展开代码以 C17 为基准。一、为什么map能直接接受vector作键std::mapKey, T, Compare只要求Compare是一个满足严格弱序的二元谓词。默认的std::lessKey调用operator。std::vector的operator按字典序比较从头开始逐元素比较第一个不相等的元素决定大小若一方是另一方的前缀则较短的更小。// 适用于 C17#include map#include string#include vectorusing Path std::vectorint;std::mapPath, 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 更大。C20 起vector的比较改由三路比较operator生成但operator的语义不变std::map的写法也不用改。需要 C20 及以上才谈得上这个变化C17 下就是普通的operator。二、作为键的语义约束键在容器内部是常量map的元素类型是std::pairconst Key, T迭代器解引用得到的first是const Key。因此不存在插入后修改键的操作想改只能删旧插新。这反而消除了键被改坏导致树结构失效的风险。需要留意的是相等与等价的区别。map判断两个键是否相同用的是 neither is less than the other即!(ab) !(ba)。对vectorint来说这等价于逐元素相等且长度相同和operator一致。但如果自定义了比较器例如忽略顺序等价关系就会与不同查找时要用同一套比较规则。另一个约束是键必须可拷贝map插入时会复制键。对vector来说复制意味着一次堆分配加元素拷贝。键越长、插入越频繁这部分开销越明显。三、完整示例用路径作键下面用节点编号序列作为键映射到路径名称。插入、查找、遍历都覆盖到。// 适用于 C17#include iostream#include map#include string#include vectorusing Path std::vectorint;int main() {std::mapPath, 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 返回 pairiterator, boolauto 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或atC11 起后者在键不存在时抛std::out_of_range。四、性能与替代方案map的每次比较是 O(k)k 为向量长度查找是 O(k log n)。键很长时比较成本会超过树的层数带来的收益。几种常见替代方案是否可用比较成本说明mapvectorint, T直接可用O(k) 每次比较无需自定义代码maparrayint,N, T直接可用O(N)编译期定长长度固定时更省mapstring, T编码后直接可用O(编码长度)需保证编码无歧义maptuple..., T直接可用逐元素元素个数固定unordered_mapvectorint, T需自定义哈希平均 O(k)标准库无std::hashvector把vector编码成字符串是常见做法例如用分隔符连接1,2,3。风险是分隔符冲突——如果元素本身可能包含分隔符编码就不再唯一。更稳的是长度前缀编码或定长二进制表示。unordered_map需要自己提供哈希。标准库只为内置类型和部分标准类型特化了std::hashstd::vector不在其中直接写std::unordered_mapstd::vectorint, std::string会编译失败。一个可用的组合哈希如下// 适用于 C17#include cstddef#include functional#include unordered_map#include vectorstruct VectorHash {std::size_t operator()(const std::vectorint v) const noexcept {std::size_t seed v.size();for (int x : v) {seed ^ std::hashint{}(x) 0x9e3779b9u (seed 6) (seed 2);}return seed;}};std::unordered_mapstd::vectorint, std::string, VectorHash fast_routes;unordered_map还需要键支持vector的逐元素相等正好满足。哈希函数的选取会影响冲突率但标准不保证任何具体的性能数字实际效果要在目标数据上测量。如果键的语义是集合而非序列顺序无关应当先把向量排序再作为键或者在插入前统一规范化否则{1,2}与{2,1}会被当成两个不同的键。常见坑点1. 直接把vector塞进unordered_map// ❌ 编译错误std::hashstd::vectorint 不存在std::unordered_mapstd::vectorint, int m;// ✅ 提供自定义哈希std::unordered_mapstd::vectorint, int, VectorHash m;2. 用operator[]做只读查找// ❌ 键不存在时插入一个默认值容器变大if (m[key] x) { /* ... */ }// ✅ 用 find 或 atauto 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.10.2 与 0.3 不相等查找失败std::mapstd::vectordouble, int m;// ✅ 改用整数放大到最小单位或定点表示std::mapstd::vectorlong 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);总结问题结论map能否直接用vector作键能vector有字典序operator比较规则逐元素字典序前缀更小长度参与键能否修改不能键是const只能删旧插新unordered_map能否直接用不能缺少std::hash特化顺序无关的键先排序规范化否则顺序不同即不同键主要成本每次比较 O(k)插入复制整个向量vector作键的可用性来自一个简单的巧合map要的只是严格弱序而vector的operator正好提供了字典序。理解这一点后剩下的判断就都是工程取舍键有多长、插入多频繁、语义是序列还是集合、要不要哈希。把这几个问题答清楚选map还是编码成字符串、要不要自定义哈希自然就有答案。