如何在std::multimap中为指定key的同键序列实现emplace_front头部插入

以下两种方案均可实现需求，无需删除原有节点后重插：

• 方案1：使用带位置提示的insert重载（无需修改现有数据结构）
  你可以通过lower_bound获取指定键对应序列的首个元素迭代器，将其作为插入位置提示传入insert接口，元素会被插入到该迭代器指向的元素之前，刚好成为同键序列的第一个元素。当插入位置提示正确时，该操作的时间复杂度为均摊O(1) + 单次lower_bound的O(log n)，远优于删除重插的O(k + log n)（k为指定键的元素总数）。
  代码示例：

  #include <multimap>
  #include <string>
  
  int main() {
      std::multimap<int, std::string> mm;
      // 预先插入几个测试元素
      mm.insert({1, "val1"});
      mm.insert({1, "val2"});
  
      // 向key=1的序列头部插入新值
      int target_key = 1;
      auto first_pos = mm.lower_bound(target_key);
      mm.insert(first_pos, {target_key, "new_head_val"});
      return 0;
  }
  

• 方案2：改用map<Key, std::list<Value>>存储结构（适合频繁操作同键序列的场景）
  如果你的业务中经常需要对同键的元素做头部插入、遍历、范围删除等操作，可以直接将multimap替换为键对应存储列表的map，直接调用列表的push_front接口即可完成头部插入，时间复杂度为严格O(1)，且完全自主可控同键元素的顺序，灵活性更高。
  代码示例：

  #include <map>
  #include <list>
  #include <string>
  
  int main() {
      std::map<int, std::list<std::string>> mm;
      // 向key=1的序列头部插入新值
      mm[1].push_front("new_head_val");
      return 0;
  }
  

内容的提问来源于stack exchange，提问作者Touloudou