如何在使用 Boost.bimap 时避免密钥复制

Question

我正在使用Boost.bimap来实现LRU缓存，其中包含一些包含字符串的复杂键。

问题是每次我调用 find（） 时都会复制密钥。我想避免这种不必要的副本（一般来说：尽可能少地复制字符串，也许通过模板？

一个最小的测试用例（带有要点版本）：

#include <string>
#include <iostream>
#include <boost/bimap.hpp>
#include <boost/bimap/list_of.hpp>
#include <boost/bimap/set_of.hpp>
class Test
{
public:
    struct ComplexKey
    {
        std::string text;
        int dummy;
        ComplexKey(const std::string &text, int dummy) : text(text), dummy(dummy) {}
        ~ComplexKey()
        {
            std::cout << "~ComplexKey " << (void*)this << " " << text << std::endl;
        }
        bool operator<(const ComplexKey &rhs) const
        {
            return tie(text, dummy) < tie(rhs.text, rhs.dummy);
        }
    };
    typedef boost::bimaps::bimap<
    boost::bimaps::set_of<ComplexKey>,
    boost::bimaps::list_of<std::string>
    > container_type;
    container_type cache;
    void run()
    {
        getValue("foo", 123); // 3 COPIES OF text
        getValue("bar", 456); // 3 COPIES OF text
        getValue("foo", 123); // 2 COPIES OF text
    }
    std::string getValue(const std::string &text, int dummy)
    {
        const ComplexKey key(text, dummy); // COPY #1 OF text
        auto it = cache.left.find(key); // COPY #2 OF text (BECAUSE key IS COPIED)
        if (it != cache.left.end())
        {
            return it->second;
        }
        else
        {
            auto value = std::to_string(text.size()) + "." + std::to_string(dummy); // WHATEVER...
            cache.insert(typename container_type::value_type(key, value)); // COPY #3 OF text
            return value;
        }
    }
};

Answer 1

Bimap 没有直接使用 std:map（我这么说是因为您使用的是 set_of ），而是通过不同的容器适配器创建视图，并在此过程中复制密钥。不可能像您在问题中定义 bimap 的方式那样显着提高性能。

为了从 bimap 获得相对于 ComplexKey 的更好性能，您将不得不存储指向 ComplexKey 的指针（最好是原始的;没有 bimap 隐含的键的所有权）并提供您自己的排序器。指针复制起来很便宜，缺点是您必须与映射并行管理密钥生存期。

做一些类似的事情，

std::vector<unique_ptr<ComplexKey>> ComplexKeyOwningContainer;
typedef boost::bimaps::bimap<
    boost::bimaps::set_of<ComplexKey*, ComplexKeyPtrSorter>,
    boost::bimaps::list_of<std::string>
    > container_type;

请注意，如果您追求性能，您还需要注意std::string这是您的 bimap 的另一侧。它们可能非常昂贵，临时性很频繁，并且它们会遇到与 ComplexKey 键相同的问题。