About
RSS

Bit Focus


STL set 悲剧指导

    这篇文章谈一个我使用 STL 中 set 容器的负面心得. 是的, 我已经被这丫的杀得超神了, 快来人阻止它吧! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽.

    最坏对数时间插入, 删除, 查询, 迭代遍历, 这些听起来都无比诱人, 它们由 STL 中的 set 容器鼎力支持. 然而, set 的只读制度是非常龌龊的, 简而言之, 只要你敢往这个坑里面放, 你就得接受它们以后再也无法修改的命运. 比如下面这段例子
#include <set>
#include <string>

using std::set;
using std::string;

struct student {
    string name;
    int grade;

    student(string const& name_, int grade_)
        : name(name_)
        , grade(grade_)
    {}

    bool operator<(student const& rhs) const
    {
        return name < rhs.name;
    }

    bool operator==(student const& rhs) const
    {
        return name == rhs.name;
    }
};

int main(void)
{
    set<student> students;
    students.insert(student("Li Lei", 5));
    students.insert(student("Han Meimei", 5));
    students.insert(student("Jim Green", 5));

    for (set<student>::iterator i = students.begin();
         students.end() != i;
         ++i)
    {
        ++(i->grade);
    }
    return 0;
}
    student 类的 key 是 name, 跟 grade 没有关系, 原则上来说, 修改后者并不会破坏 set 的存储结构. 然而, 编译器一棒子打死, 不许改, 除非剩下的成员全部 mutable 修饰.
    只读制度悲剧的根源在于, set 所谓的 key 撑死只是个假象, value_type 这玩意儿就是 key_type 本身.
    伪 key 导致的不仅仅是不能改, 重要的是还不能查! 看看 set::find 函数的参数, 要的又是阴魂不散的 key_type. 这意味着什么? 意味着 Han MM 同学报出她名字的时候, 还查不出她几年级, 而必须要利用她的名字, 伪造一个充气娃娃放进去才能找到! 看到这里我就败了, 这明摆着就是不让我用 set, 让我转投 map 么? 一个也许可行的方案是
#include <map>
#include <string>

using std::map;
using std::string;

struct student_periphery {
    int grade;
};

map<string, student_periphery> students;
这样建模的话也是够狗血的, 如果哪个函数拿着一份 student_periphery 问怎么查出学生姓名, 那就更悲剧了.

Permanent Link: /p/79 Load full text

Post tags:

 set
 C++
 STL


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site