将映射的值转换为多重映射

Question

我使用一个Map存储了一些键值对，现在需要按照值来排序，我考虑使用以下方式：

#include <iostream>
#include <map>
#include <string>

int main ()
{
    std::map<std::string, int> map1;
    std::multimap<int, std::string> multimap2;

    map1.insert ( std::pair<std::string, int>( "one", 4) );
    map1.insert ( std::pair<std::string, int>( "two", 2) );
    map1.insert ( std::pair<std::string, int>( "three", 2) );
    map1.insert ( std::pair<std::string, int>( "four", 1) );

    for (auto it = map1.begin(); it != map1.end(); ){
        multimap2.insert(std::pair<int, std::string>( it->second, it->first));
        map1.erase(it++);
    }

   for (auto it = multimap2.rbegin(); it != multimap2.rend(); ++it)
   std::cout << it->first << " --- " << it->second << '\n';

   return 0;
}

这给了我：

4 --- 一个 2 --- 两个 2 --- 三个 1 --- 四个

虽然我需要这样的结果，但是否有更聪明、更高效的方法获得相同的结果呢？ 它将需要处理一个相当大的数据集...

感谢您的时间 :)

- Xarylem

Answer 1

另一个选择是将它们存储在一个向量中并进行排序：

typedef std::pair<std::string, int> pair;
std::vector<pair> v;
v.reserve(map1.size());
std::copy(map1.begin(), map1.end(), std::back_inserter(v));
std::sort(v.begin(), v.end(), 
    [](pair const & a, pair const & b) {
        return a.second < b.second;
    });

这可能比插入到multimap中更快，因为它只需要一次内存分配。

- Mike Seymour

---

更好的做法是将指向pair的const指针放入向量中并对其进行排序。这样可以避免复制它们并减少在排序时在向量中交换它们的成本。注意：存储在映射中的pair将是类型为std::pair<const std::string, int>的对象。 - Frederic Lachasse

@FredericLachasse：是的，如果您不需要自包含的结果，那么这是另一种尝试的方法。它不一定会更快，因为额外的间接引用会有成本；您需要测量两种替代方案。 - Mike Seymour

谢谢！那么，复制时删除地图元素的部分怎么样？在我看来，这对于减少内存需求非常有用... - Xarylem

@Xarylem：你需要一个类似于你的循环而不是std::copy。虽然可能会慢一些。 - Mike Seymour

Answer 2

您可能希望构建一个双向映射的抽象类（基本上您已经在使用这种技术）。如果您需要任意的get_by_key/get_by_value查询，这种类可能会很有用。

template <typename K, typename V>
class bi_map
{
private:
    std::map<K, V>      key_to_value_;
    std::multimap<V, K> value_to_key_;

public:
    typedef typename std::multimap<typename V, typename K>::iterator by_value_iterator;
    typedef typename std::map<K, V>::iterator  by_key_iterator;
    const V& value(const K& key) {
        return key_to_value_[key];
    }

    std::pair<by_value_iterator, by_value_iterator> keys(const V& value) {
        return value_to_key_.equal_range(value);
    }

    void set(const K& key, const V& value) {
        by_key_iterator it = key_to_value_.find(key);
        if (key_to_value_.end() != it) {
            std::pair<by_value_iterator, by_value_iterator> it_pair = value_to_key_.equal_range(key_to_value_[key]);
            while (it_pair.first != it_pair.second)
                if (it_pair.first->first == it->second) {
                    value_to_key_.erase(it_pair.first);
                    break;
                } else ++it_pair.first;
        }
        key_to_value_[key] = value;
        value_to_key_.insert(std::make_pair(value, key));
    }
};

- Nikita