无法使用boost::multiindex时，双键场景下优选何种数据结构？

首先得先指出你当前方案的潜在问题：如果用std::map<Key1, Record>（其中Record包含Key2和其他数据），那同一个Key1只能存储一条记录——但你的需求里允许同一Key1对应多个不同Key2的记录（毕竟Key1+Key2组合才是唯一的），所以这个结构根本存不下多Key2的情况，这是第一个要修正的点。

接下来针对你的三个查询需求（按Key1查所有、按Key2查所有、按Key1+Key2查单条），给你几个更优的方案：

方案1：手动维护多容器索引（无第三方依赖） #

如果不想引入额外库，可以用一个主容器+两个辅助索引容器的组合：

• 主容器：std::map<std::pair<Key1, Key2>, Record>（主键是Key1+Key2的组合，保证唯一性）
• 辅助索引1：std::multimap<Key1, std::pair<Key1, Key2>>——用来快速映射Key1到对应的所有主键对
• 辅助索引2：std::multimap<Key2, std::pair<Key1, Key2>>——用来快速映射Key2到对应的所有主键对

查询逻辑： #

• 按Key1+Key2查单条：直接调用主map的find(std::make_pair(k1, k2))，时间复杂度O(logN)
• 按Key1查所有：用辅助索引1的equal_range(k1)拿到所有对应的主键对，再逐个去主map中取出完整记录，时间复杂度O(logN + K)（K是该Key1对应的记录数）
• 按Key2查所有：同理，用辅助索引2的equal_range(k2)，时间复杂度O(logN + K)

注意点： #

增、删、改记录时，必须同步更新三个容器，否则会出现数据不一致的情况——比如新增一条记录时，要同时插入主容器和两个辅助索引，这部分逻辑需要自己封装成函数，避免手动操作出错。

方案2：用Boost.MultiIndex容器（最省心的选择） #

如果你能引入Boost库，那multi_index_container就是为这种多维度查询场景量身定做的，它允许你在同一个容器上定义多个不同的索引，不需要手动维护一致性。

示例代码： #

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

// 假设你的Record结构是这样的
struct Record {
    Key1 key1;
    Key2 key2;
    std::string extra_data; // 其他数据字段
};

// 定义多索引容器
using RecordStore = boost::multi_index::multi_index_container<
    Record,
    boost::multi_index::indexed_by<
        // 索引1：主键索引（Key1+Key2唯一）
        boost::multi_index::ordered_unique<
            boost::multi_index::composite_key<
                Record,
                boost::multi_index::member<Record, Key1, &Record::key1>,
                boost::multi_index::member<Record, Key2, &Record::key2>
            >
        >,
        // 索引2：按Key1的非唯一索引
        boost::multi_index::ordered_non_unique<
            boost::multi_index::member<Record, Key1, &Record::key1>
        >,
        // 索引3：按Key2的非唯一索引
        boost::multi_index::ordered_non_unique<
            boost::multi_index::member<Record, Key2, &Record::key2>
        >
    >
>;

查询逻辑： #

• 按Key1+Key2查单条：通过主键索引的find方法直接定位，O(logN)
• 按Key1查所有：获取第二个索引（按Key1排序的索引），调用equal_range(k1)拿到该Key1对应的所有记录区间，遍历即可，O(logN + K)
• 按Key2查所有：同理，用第三个索引的equal_range(k2)，O(logN + K)

优势： #

所有索引的一致性由Boost库自动维护，增删改操作只需要操作这个容器就行，不需要手动同步多个结构，代码更简洁可靠，出错概率极低。

方案3：无序容器版本（追求平均查询速度） #

如果你的查询性能要求更高，且Key1、Key2可以提供哈希函数，可以把上面的有序容器换成无序版本：

• 主容器：std::unordered_map<std::pair<Key1, Key2>, Record>（需要自定义std::pair<Key1, Key2>的哈希函数）
• 辅助索引：std::unordered_multimap<Key1, std::pair<Key1, Key2>>和std::unordered_multimap<Key2, std::pair<Key1, Key2>>

特点： #

平均查询时间复杂度是O(1)，比有序容器更快，但最坏情况下可能退化到O(N)，而且需要处理哈希冲突，适合对查询速度敏感且数据分布比较均匀的场景。

总结建议 #

• 如果不能引入第三方库：选方案1，记得封装好增删改的同步逻辑
• 如果可以用Boost：优先选方案2，省心又可靠
• 追求极致查询速度且能处理哈希：选方案3

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