致电订单查询

Question

现在我有std::map<std::string, Object> myMap。类Object有funcions：int getPriority()和void Work()。现在我浏览地图，并且由于对象的优先级而想要拨打Work。

我写了很疯狂的想法：该地图的克隆，但在关键的它的优先级存储，例如：

myMap["3_key1"] = Object(); 
myMap["6_key2"] = Object(); 
myMap["0_key3"] = Object(); 

它排序，并呼吁是正确的队列：0_key3; 3_key1; 6_key2。

但我认为这很慢。而且我想用提升替换std::map与unordered_map，因为它快很多。并没有按键排序。

那么，有什么想法？

Answer 1

使用Boost.MultiIndex：

// your class 
#include <iostream> 
#include <string> 

class foo 
{ 
public: 
    foo(std::string name, unsigned priority, std::string msg) : 
    mPriority(priority) 
    { 
     mName.swap(name); // primitive std::move :) 
     mMsg.swap(msg); // (default-construct & swap) 
    } 

    const std::string& name() const 
    { 
     return mName; 
    } 

    unsigned priority() const 
    { 
     return mPriority; 
    } 

    void work() const 
    { 
     std::cout << mMsg << std::endl; 
    } 

private: 
    std::string mName; 

    unsigned mPriority; 
    std::string mMsg; 
}; 

// your container 
#include <boost/multi_index_container.hpp> 
#include <boost/multi_index/mem_fun.hpp> 
#include <boost/multi_index/ordered_index.hpp> 
#include <boost/multi_index/sequenced_index.hpp> 

namespace bmi = boost::multi_index; 

typedef boost::multi_index_container<foo, 
      bmi::indexed_by< 
       // order by name (std::map) 
       bmi::ordered_unique< 
        bmi::const_mem_fun<foo, const std::string&, &foo::name> 
         >, 

       // order by priority (std::multi_map) 
       bmi:: ordered_non_unique< 
        bmi::const_mem_fun<foo, unsigned ,&foo::priority> 
         > 
       > 
      > foo_set; 

// test 
#include <boost/foreach.hpp> 

int main() 
{ 
    foo_set fooSet; 
    fooSet.insert(foo("a", 4, "this is a, priority 4")); 
    fooSet.insert(foo("b", 3, "this is b, priority 3")); 
    fooSet.insert(foo("c", 7, "this is c, priority 7")); 
    fooSet.insert(foo("d", 1, "this is c, priority 1")); 

    // view as map from name to value 
    foo_set::nth_index<0>::type& nameView = fooSet.get<0>(); 

    nameView.find("a")->work(); // find "a", print its message 
    if (nameView.find("e") == nameView.end()) 
     std::cerr << "e not found" << std::endl; 

    std::cout << std::endl; 

    // view as multi_map from priority to value 
    foo_set::nth_index<1>::type& priorityView = fooSet.get<1>(); 

    BOOST_FOREACH(const foo& f, priorityView) 
     f.work(); // work, in order of priority 
} 

我没有它的任何性能测试，但它肯定更好的表达你的意图，而这往往表明改进的性能呢。

Answer 2

我觉得最简单的方法是两个容器。您当前的键 - >值映射，以及按对象的优先级排序的第二批键（可能只是使用priority_queue作为您的堆实现）。这将有困难的优先事项可以即时改变。

Answer 3

如果你使用std :: set或std :: priority_queue代替std :: map，你可以定义一个函子，或者简单地为你的类实现运算符<，这样std :: set就会按优先级顺序排列对象为你。

#include <iostream> 
#include <set> 

class Object { 
    public: 
    int m_priority; 

    Object(int p) : m_priority(p) { } 

    int getPriority() const { return m_priority; } 

    void Work() const { std::cout << m_priority << std::endl; } 
}; 

bool operator<(const Object & lhs, const Object & rhs) 
{ 
    return lhs.getPriority() < rhs.getPriority(); 
} 

int main() 
{ 
    std::set<Object> container; 

    container.insert(Object(1)); 
    container.insert(Object(9)); 
    container.insert(Object(5)); 
    container.insert(Object(8)); 
    container.insert(Object(3)); 

    for (std::set<Object>::iterator I = container.begin(); 
     I != container.end(); 
     ++I) { 
     I->Work(); 
    } 
}