如何有效地按價值訂購地圖？

Question

考慮一個std::map<K,V>。我想通過適當的容器std::C<V*>或std::C<V&>通過價值獲利重新排序地圖，其方式是不存在值的副本以將元素存儲在C中。此外，C中的元素必須根據int f(V&)的結果進行排序應用於每個元素。儘管我努力了，但我找不到合適的C和足夠有效的方法來構建它。你有任何解決方案？一個小例子將不勝感激。

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); 

http://ideone.com/bBoXq

這需要以前的地圖留在範圍長比dest，並沒有對中取下直到dest被銷燬。否則src將需要持有某種智能指針。

Answer 2

我開始的地方是：

• 看看Boost::bimap
• 創建從V訂購 - >ķ通過其計算f（V &）你建議的方式比較函數對象。 （例如，如在std::map<K,V,C>其中C是比較器類）

Answer 3

如何，

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

其中compfunc是一個算符采用兩個shared_ptr對象並在函數應用邏輯？

打擾格式化，不好我的手機。

Answer 4

如何像這樣（未經測試的僞代碼）：

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); 

Answer 5

您可以使用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)] 

Answer 6

聽起來像是你正在使用多個容器將多個視圖表示爲相同的數據集。這種方法的問題在於保持容器同步並避免懸掛指針問題。 Boost.MultiIndex就是爲此而製作的。 A 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); 
} 

結果：

 
Records sorted by key: 
alpha -1 
bravo -3 
charlie -2 

Records sorted by sortFunc(const Record&): 
alpha -1 
charlie -2 
bravo -3