C++编译报错‘Item’ is not derived from const __gnu_cxx的修复及容器选型问题

1 编译错误修复方法 #

错误原因 #

你调用std::find(lst.begin(), lst.end(), vec[i])时，待查找范围的元素类型是Item，第三个入参是std::string类型，标准库找不到Item和std::string对应的相等比较运算符，模板实例化失败就抛出了你看到的迭代器相关报错，本质是缺少自定义类型的比较规则。

修复方案 #

有两种常用修复方式，二选一即可：

方案1：为Item类重载==运算符

在Item类的public成员中新增和string比较的运算符：

bool operator==(const string& str) const {
    return name == str;
}

修改后的Item类完整定义：

class Item
{
    public:
    int count;
    string name;
    
    Item(){};
    Item(string str, int cnt)
    {
        name = str;
        count = cnt;
    };
    // 新增比较运算符
    bool operator==(const string& str) const {
        return name == str;
    }
};

方案2：改用std::find_if自定义比较逻辑

不需要修改Item类，直接把find调用替换为find_if，传入自定义比较规则：

// 把原来的it = find(...)行替换为下面的代码
it = find_if(lst.begin(), lst.end(), [&](const Item& item) { return item.name == vec[i]; });

两种方案修改后都可以正常编译运行，你的测试用例输出结果为catacana。

2 符合要求的可选容器 #

需要保持元素插入顺序、不自动排序的场景，可选择的容器如下：

• 基础顺序容器：std::vector、std::list、std::deque都完全符合要求，三者严格按照插入顺序存储元素，不会自动排序。其中std::vector的遍历、随机访问效率远高于std::list，普通场景更推荐使用。
• 大数据量优化方案：如果元素数量较多，每次遍历全容器查找的时间成本太高，可以组合使用容器：用std::unordered_map<std::string, int>做O(1)复杂度的计数统计，额外用一个std::vector<std::string>按插入顺序存储首次出现的元素，最后遍历顺序容器读取计数即可，兼顾统计效率和顺序要求。
• C标准库目前没有原生的插入有序哈希表实现，如果你使用C17以上版本，也可以用第三方库的插入有序哈希表实现，无需额外维护顺序容器。

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