如何高效地按值排序地图？

Question

考虑一个std:：map<K，V>。 我想通过使用适当的容器std::C<V*>或者std::C<V&>来通过值重新排序映射表，以一种不需要复制值以存储元素到C中的方式。 此外，C中的元素必须根据应用于每个元素的int f(V&)的结果进行排序。 尽管我努力寻找适当的C和足够高效的构建方法，但我没有找到。 您有任何解决方案吗？ 如果有小例子将会更好。

- Martin

---

这个不太清楚。你想让你的新容器包含一个指向映射值的指针集，并且按顺序排序吗？ - Oliver Charlesworth

目标容器是序列容器还是关联容器？（vector vs map） - Mooing Duck

Answer 1

似乎很简单。

std::map<K,V> src;
int f(V&) {return 0;}

V* get_second(std::pair<const K,V> &r) {return &(r.second);} //transformation
bool pred(V* l, V* r) { return f(*l)<f(*r); }   //sorting predicate

std::vector<V*> dest(src.size());  //make destination big enough
std::transform(src.begin(), src.end(), dest.begin(), get_second); //transformcopy
std::sort(dest.begin(), dest.end(), pred); //sort

除非你的意思是 C 应该是另一张地图：

std::pair<K,V*> shallow_pair(std::pair<const K,V> &r) 
{return std::pair<K,V*>(r.first, &(r.second));}

std::map<K, V*> dest2;
std::transform(src.begin(), src.end(), 
               std::inserter(dest2,dest2.end()), shallow_pair);

这需要先前的映射在作用域内保持比 dest 更长时间，并且在 dest 被销毁之前不删除任何键值对。否则 src 将需要持有某种智能指针。

http://ideone.com/bBoXq

- Mooing Duck

---

+1：看起来正确。你能否使用std::transform和std::back_inserter代替显式循环？ - Oliver Charlesworth

可能吧，但我觉得它们并没有太多的用处。如果标准库已经有了get_pair_first和get_pair_second一元函数，那么我可能会使用它们。 - Mooing Duck

加油，你已经在使用c++11了：[](pair<K,V> &v) { return &v.second } :-) - znkr

在您的意见中，vector 和 map 哪个更快？ - Martin

@Martin：这取决于你对它的使用方式。 - Mooing Duck

@krynr：MSVC不支持lambda表达式，所以我避免使用它们。除此之外，已完成。 - Mooing Duck

Answer 2

您可以使用 std::reference_wrapper，如下所示：

#include <map>
#include <string>
#include <algorithm>
#include <functional>

#include <prettyprint.hpp>
#include <iostream>

template <typename T>
std::ostream & operator<<(std::ostream & o, std::reference_wrapper<T> const & rw)
{
  return o << rw.get();
}

int main()
{
  std::map<int, std::string> m { { 1, "hello"}, { 2, "aardvark" } };
  std::cout << m << std::endl;

  std::vector<std::reference_wrapper<std::string>> v;
  for (auto & p : m) v.emplace_back(p.second);
  std::cout << v << std::endl;

  std::sort(v.begin(), v.end(), std::less<std::string>); // or your own predicate
  std::cout << v << std::endl;

  v.front().get() = "world";
  std::cout << m << std::endl;
}

这将打印：

[(1, hello), (2, aardvark)]
[hello, aardvark]
[aardvark, hello]
[(1, hello), (2, world)]

- Kerrek SB

---

使用非标准库？我猜这也算公平。 - Mooing Duck

我不熟悉 refcomp，那不是自定义的东西吗？ - Mooing Duck

@MooingDuck：我已经移除了那个可怕的东西，感谢在另一个问题中提供的帮助。 - Kerrek SB

一个显式的 std::less<std::string> 对于解决问题是个好主意，但他希望按照 int f(V&) 的结果进行排序。 - Mooing Duck

@MooingDuck：哦，好的，我没看到那个。那么你无论如何都需要谓词。我会添加一个注释。 - Kerrek SB

Answer 3

听起来你正在使用多个容器来表示同一数据集的多个视图。这种方法的问题在于保持容器同步并避免悬空指针问题。Boost.MultiIndex 就是为了解决这个问题而设计的。一个boost::multi_index容器仅存储每个元素的一个副本，但允许您通过多个索引访问元素。

例：

#include <iterator>
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/global_fun.hpp>
#include <boost/multi_index/member.hpp>

typedef std::string Key;
typedef int Value;

struct Record
{
    Record(const Key& key, Value value) : key(key), value(value) {}
    Key key;
    Value value;
};

inline std::ostream& operator<<(std::ostream& os, const Record& rec)
{
    os << rec.key << " " << rec.value << "\n";
    return os;
}

inline int sortFunc(const Record& rec) {return -rec.value;}

struct ByNumber{}; // tag

namespace bmi = boost::multi_index;
typedef bmi::multi_index_container<
  Record,
  bmi::indexed_by<
    // sort by key like a std::map
    bmi::ordered_unique< bmi::member<Record, Key, &Record::key> >,

    // sort by less<int> on free function sortFunc(const Record&)
    bmi::ordered_non_unique<bmi::tag<ByNumber>, 
                            bmi::global_fun<const Record&, int, &sortFunc> >
  > 
> RecordSet;

typedef RecordSet::index<ByNumber>::type RecordsByNumber;

int main()
{
    RecordSet rs;
    rs.insert(Record("alpha", -1));
    rs.insert(Record("charlie", -2));
    rs.insert(Record("bravo", -3));

    RecordsByNumber& byNum = rs.get<ByNumber>();

    std::ostream_iterator<Record> osit(std::cout);

    std::cout << "Records sorted by key:\n";
    std::copy(rs.begin(), rs.end(), osit);

    std::cout << "\nRecords sorted by sortFunc(const Record&):\n";
    std::copy(byNum.begin(), byNum.end(), osit);
}

结果：

按键排序的记录：
alpha -1
bravo -3
charlie -2
按sortFunc(const Record&)排序的记录：
alpha -1
charlie -2
bravo -3

- Emile Cormier

Answer 4

我会从以下几个方面开始：

• 查看Boost::bimap
• 通过比较函数对象创建从V到K的排序，该函数对象按照您建议的方式评估f(V&)。（例如，如在std::map<K,V,C>中，其中C是比较器类）

- Jason S

Answer 5

这样如何，

std::set<boost::shared_ptr<V>, compfunc>

其中compfunc是一个函数对象，它接受两个shared_ptr对象并应用您的函数中的逻辑？

抱歉格式不好，我在手机上。

- Nim

Answer 6

这样的代码怎么样（未经测试的伪代码）：

V* g(pair<K,V> &v) { return &v.second; }
bool cmp(V* a, V* b) { return f(*a) < f(*b); }

map<K,V> map;
vector<V*> vec;
vec.reserve(map.size());
transform(map.begin(), map.end(), back_inserter(vec), g);
sort(vec.begin(), vec.end(), cmp);

- znkr