map 效率问题

    技术2022-05-20  30

    当关乎效率时应该在map::operator[]和map-insert之间仔细选择

    class Widget {

    public:

    Widget();

    Widget(double weight);

    Widget& operator=(double weight);

    ...

    }

    map<int, Widget> m;

    m[1] = 1.50;

     

    表达式m[1]是m.operator[](1)的简化,所以这是一个map::operator[]的调用。那个函数必须返回一个Widget的

    引用,因为m 的映射类型是Widget。在这里,m里面还没有任何东西,所以键1在map里没有入口。因此

    operator[]默认构造一个Widget来作为关联到1的值,然后返回到那个Widget的引用。最后,Widget成为赋值目

    标:被赋值的值是1.50。

    换句话说,这个语句

    m[1] = 1.50;

    功能上等价于这个:

    typedef map<int, Widget> IntWidgetMap; // 方便的

    // typedef

    pair<IntWidgetMap::iterator, bool> result = // 用键1建立新

    m.insert(IntWidgetMap::value_type(1, Widget())); // 映射入口

    // 和一个默认构造的

    // 值对象;

    // 看下面对于

    // value_type的

    // 注释

    result.first->second = 1.50; // 赋值给

    // 新构造的

    条款24:当关乎效率时应该在map::operator[]和map-insert之间仔细选择

    // 值类型

    现在已经很清楚为什么这种方法可能降低性能了。我们先默认构造一个Widget,然后我们立即赋给它新值。

    如果用想要的值构造Widget比默认构造Widget然后进行赋值显然更高效,我们就应该用直截了当的insert调用

    来替换operator[]的使用(包括它的构造加赋值):

    m.insert(IntWidgetMap::value_type(1, 1.50));

    这与上面的那些代码有相同的最终效果,除了它通常节省了三次函数调用:一个建立临时的默认构造Widget

    对象,一个销毁那个临时的对象和一个对Widget的赋值操作。那些函数调用越昂贵,你通过使用map-insert代

    替map::operator[]就能节省越多。

    上面的代码利用了每个标准容器都提供的value_type typedef。这typedef没有什么特别重要的,但对于map和

    multimap(以及非标准容器的hash_map和hash_multimap——参见条款25),记住它是很重要的,容器元素的

    类型总是某种pair。

    我早先谈及的operator[]被设计为简化“添加或更新”功能,而且现在我们理解了当“增加”被执行时,insert

    比operator[]更高效。当我们做更新时,情形正好相反,也就是,当一个等价的键(参见条款19)这已经在

    map里时。为了看出为什么情况是这样,看看我们的更新选项:

    m[k] = v; // 使用operator[]

    // 来把k的值

    // 更新为v

    m.insert(

    IntWidgetMap::value_type(k, v)).first->second = v; // 使用insert

    // 来把k的值

    // 更新为v

    语法本身也许会让你信服地支持operator[],但在这里我们关注于效率,所以我们将忽略它。insert的调用需要

    IntWidgetMap::value_type类型的实参(即pair<int, Widget>),所以当我们调用insert时,我们必须构造和析构

    一个那种类型的对象。那耗费了一对构造函数和析构函数,也会造成一个Widget的构造和析构,因为

    pair<int, Widget>本身包含了一个Widget对象,operator[]没有使用pair对象,所以没有构造和析构pair和

    Widget。

    因此出于对效率的考虑,当给map添加一个元素时,我们断定insert比operator[]好;而从效率和美学考虑,当

    更新已经在map里的元素值时operator[]更好。如果STL提供一个两全其美的函数,即,在句法上吸引人的包

    中的高效的“添加或更新”功能。


    最新回复(0)