如何实现对象的双键高效搜索并避免内存冗余？

你的思路完全正确：在两个std::set中存储对象指针是避免内存冗余的最佳选择之一。因为指针仅占用少量内存（通常4/8字节），两个set只会保存指向同一对象的指针，不会复制庞大的对象本体（比如Person的额外字段或A类的大数组x）。但要注意，默认的指针排序是按内存地址，必须给每个set指定自定义比较器来实现按目标键排序。

具体实现（以Person类为例） #

定义比较器与set #

#include <set>
#include <string>

class Person {
public:
    std::string name;
    std::string address;
    // 其他字段...
};

// 按姓名排序的比较器
struct CompareByName {
    bool operator()(const Person* a, const Person* b) const {
        return a->name < b->name;
    }
};

// 按地址排序的比较器
struct CompareByAddress {
    bool operator()(const Person* a, const Person* b) const {
        return a->address < b->address;
    }
};

// 两个分别按姓名、地址排序的set，存储Person指针
std::set<Person*, CompareByName> name_sorted_set;
std::set<Person*, CompareByAddress> addr_sorted_set;

插入与查找示例 #

int main() {
    // 创建对象（建议用智能指针管理内存，避免泄漏）
    Person* alice = new Person{"Alice", "123 Main St"};
    Person* bob = new Person{"Bob", "456 Oak Ave"};

    // 同时插入两个set
    name_sorted_set.insert(alice);
    addr_sorted_set.insert(alice);
    name_sorted_set.insert(bob);
    addr_sorted_set.insert(bob);

    // 按姓名O(logn)查找
    std::string target_name = "Alice";
    Person temp_person;
    temp_person.name = target_name;
    auto name_iter = name_sorted_set.lower_bound(&temp_person);
    if (name_iter != name_sorted_set.end() && (*name_iter)->name == target_name) {
        // 找到目标Person对象：*name_iter
    }

    // 按地址O(logn)查找
    std::string target_addr = "456 Oak Ave";
    temp_person.address = target_addr;
    auto addr_iter = addr_sorted_set.lower_bound(&temp_person);
    if (addr_iter != addr_sorted_set.end() && (*addr_iter)->address == target_addr) {
        // 找到目标Person对象：*addr_iter
    }

    // 内存清理（用智能指针可省略这步）
    delete alice;
    delete bob;
    name_sorted_set.clear();
    addr_sorted_set.clear();
    return 0;
}

优化与替代方案 #

• 用智能指针替代裸指针：如果担心内存泄漏，改用std::shared_ptr<Person>存储在set中，无需手动管理内存：

  std::set<std::shared_ptr<Person>, CompareByName> name_sorted_set;
  

• 专用多索引容器：如果使用C++17及以上，或允许使用Boost库，boost::multi_index_container是更专业的选择——它能在单个容器中维护多个排序索引，无需手动管理多个set，代码更简洁且不易出错。

关键注意事项 #

• 确保对象生命周期长于两个set，避免悬垂指针（裸指针场景）。
• 若对象的键值（如name/address）需要修改，必须先从两个set中删除对象，修改后重新插入，否则set的排序结构会失效，导致查找错误。
• 自定义比较器必须满足严格弱排序规则，否则set的行为会未定义。

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