如何在multiset中按Rect的name查找并删除已存在元素？

现有一个基于自定义比较器LessArea排序的std::multiset<Rect, LessArea>，需求是在插入新Rect对象前，删除集合中所有与新对象同名（仅匹配name字段，忽略其他属性）的元素。尝试过使用lower_bound和重载==运算符配合find方法，但均无法实现预期效果，该如何解决？

基础实现代码 #

// implementation of multiset
#include <condition_variable> // std::condition_variale
#include <iostream>
#include <iterator>
#include <set>
#include <thread>
#include <algorithm>
#include <mutex>

using namespace std;

class Rect{
public:
        double height;
        double width;
        double area;
        string name;

        friend ostream& operator<<(ostream& os, const Rect& r);
};

ostream& operator<<(ostream& os, const Rect& r)
{
    os << r.area << " " << r.name;
    return os;
}

struct LessArea
{
    bool operator ()(const Rect& lhs, const Rect& rhs) const
    {
        return lhs.area < rhs.area;
    }
};

std::multiset<Rect, LessArea> rects;

数据生成与插入逻辑 #

produceData()
{
  const string arrayString[4] = {"C", "B", "N", "A"};
  int RandIndex = rand() % 4; //generates a random number between 0 and 3
  string name = arrayString[RandIndex];

  int randomNumber1 = (int)(rand() % 1000);
  int randomNumber2 = (int)(rand() % 1000);
  int randomNumber3 = (int)(rand() % 1000);

  Rect value = {randomNumber1, randomNumber2, randomNumber3, name};

  // 希望删除同名的rect，无论其他字段值如何
  rects.erase(s.lower_bound(value)); // 此方法无效，因为它匹配所有字段

  // 添加新值
  addToMultiSet(value);
}

尝试过的无效方案 #

为Rect重载==运算符后使用find：

class Rect{
public:
        double height;
        double width;
        double area;
        string name;

        bool operator == ( const Rect & rhs ) const { return ( name == rhs.name ); }
        friend ostream& operator<<(ostream& os, const Rect& r);
};

...

multiset<Rect>::iterator ceItr = rects.find( value );

if(ceItr != rects.end())
{
    rects.erase(ceItr);
}

方法1：遍历集合匹配删除 #

由于multiset是按area排序的，name没有索引支持，只能通过遍历整个集合筛选出同名元素并删除：

// 替换produceData中的删除逻辑
std::mutex mtx; // 全局或类内定义互斥锁
std::lock_guard<std::mutex> lock(mtx); // 多线程必须加锁，避免数据竞争
auto it = rects.begin();
while (it != rects.end()) {
    if (it->name == value.name) {
        it = rects.erase(it); // erase会返回下一个有效迭代器，无需手动递增
    } else {
        ++it;
    }
}

注意：多线程环境下必须用互斥锁保护rects的所有读写操作，比如addToMultiSet函数也需要加锁。

方法2：优化数据结构提升效率 #

如果需要频繁按name执行查找删除操作，仅用multiset的效率很低（遍历是O(n)复杂度）。建议额外维护一个哈希表，记录每个name对应的multiset迭代器：

#include <unordered_map>

std::multiset<Rect, LessArea> rects;
std::unordered_map<std::string, std::multiset<Rect, LessArea>::iterator> name_index;
std::mutex mtx;

// 插入新元素时自动处理同名旧元素
void addToMultiSet(const Rect& val) {
    std::lock_guard<std::mutex> lock(mtx);
    // 先删除同名旧元素（如果存在）
    auto map_it = name_index.find(val.name);
    if (map_it != name_index.end()) {
        rects.erase(map_it->second);
        name_index.erase(map_it);
    }
    // 插入新元素并更新索引
    auto set_it = rects.insert(val);
    name_index[val.name] = set_it;
}

这种方案的时间复杂度为O(1)（哈希表查找）+ O(log n)（multiset删除/插入），远优于遍历方案。

原方案无效的原因 #

1. lower_bound不匹配需求：它是基于LessArea比较器工作的，只会按area值查找元素，和name字段完全无关，所以无法定位同名元素。
2. multiset::find不使用==运算符：find判断元素"相等"的逻辑是基于集合的比较器——当!comp(a,b) && !comp(b,a)时认为元素相等，也就是仅当area值相同时才会被找到，和你重载的==运算符没有关系。

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