3

我想设计一个元素 E 的容器 C。

E 有 2 个属性（优先级、名称），容器中的所有元素都有唯一的“名称”

我想尽可能有效地支持对这个容器 C 的以下操作。

  1. insert:- 将 element1(name1, priority1) 插入容器： C.insert(element(name1, priority1))
  2. update :- 更新元素的优先级 name=name1 作为 priorityNew1: C[name1] = priorityNew1
  3. delete:-删除name=name1的元素：C.delete(name1)
  4. 获取和删除具有最高优先级的元素：C.pop()
  5. 获取具有最高优先级的元素：C.peek()

基本上我想要地图和堆的组合。映射在元素的“名称”上，并堆在元素的“优先级”上。最理想的情况是，我希望每个操作都为 O(1)。否则插入、更新、删除为 O(log N) 和 pop 和 peek 为 O(1) 也可以。

我可以想到以下两种方法

1) 使用元素的哈希映射，对名称进行哈希处理。所以插入更新删除是 O(1) pop 和 peek 是 O(N)，我们在整个容器中搜索最高优先级。

2) 将 SQLite 与具有两列“名称”和“优先级”的表“元素”一起使用。运行时间将基于 SQLite 实现。

我有兴趣了解有关此问题的更多想法，我正面临与此相关的现实世界问题。感谢您的投入。

4

2 回答 2

2

如果O(logN)对于每个操作都是可以接受的，显然boost::bimap就足够了。这就像一个双面的 std::map. std::map您可以通过将两者保持在一起或编写自己的包装器来获得几乎相同的效果（但为什么要这样做呢？）。具有自平衡的二叉搜索树具有O(logN)最小检索，其效率略低于堆。

如果效率真的那么重要，您应该使用堆和哈希映射实现自己的容器。name然后，当您在堆中交换时，在哈希映射中的堆数组中维护从到订阅的映射。这给出了插入、删除、重新分配优先级 aO(logN)和 中的最小/最大优先级元素O(1)。（这不是小菜一碟，但也不乏味）

于 2013-02-28T16:27:59.150 回答
2

我不知道 Boost 是否适合您，但我会查看 Boost Mutli Index。 http://www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

您可以保留一个 in 优先级索引，以便您快速获取这些索引以及插入元素。对于 MRU/LRU 情况，我类似地使用了 boost mutli 索引。 

#include <iostream>
#include <string>
#include <algorithm>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/optional.hpp>

struct bypriority{};
struct byseq{};

struct MyElement{
    typedef int priority_type;
    typedef std::string name_type;

    name_type name;
    priority_type priority;

    MyElement(const name_type& name, const priority_type& priority):name(name),priority(priority){};
};

std::ostream& operator<<(std::ostream& os, const MyElement& e){
    os << "Name: " << e.name << " Priority: " << e.priority;
    return os;
}

using namespace boost;
using namespace boost::multi_index;

template<typename Element>
struct Container{
    typedef multi_index_container<
        Element,
        indexed_by<
            //sequenced
            sequenced<tag<byseq> >,
            //ordered by priority
            ordered_non_unique<tag<bypriority>,member<Element,typename Element::priority_type,&Element::priority>, std::greater<typename Element::priority_type>  >
        >
    > Elements;


    void insert(const Element& e){
        typename Elements::template index<byseq>::type& list_view = elements.get<byseq>();
        list_view.push_back(e);
    }

    boost::optional<Element> peek() const{  
        boost::optional<Element> res;
        typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
        if(it != elements.get<bypriority>().end()){
            res.reset(*it);
        }
        return res;
    }

    boost::optional<Element> pop() {
        boost::optional<Element> res;
        typename Elements::template index<bypriority>::type& priority_index = elements.get<bypriority>();
        typename Elements::template index<bypriority>::type::iterator it = elements.get<bypriority>().begin();
        if(it != elements.get<bypriority>().end()){
            res.reset(*it);
            priority_index.erase(it);
        }

        return res;
    }

    void print_in_order(std::ostream& os) const{
        typedef  typename Elements::template index<byseq>::type elements_by_sequence;
        for(typename elements_by_sequence::iterator it = elements.get<0>().begin(); it != elements.get<0>().end(); it++){
            os << *it << std::endl;
        }
    }

    protected:
    Elements elements;
};



using namespace std;
int main(int argc, char *argv[]) {

    Container<MyElement> c;

    c.insert(MyElement("Bob",10));
    c.insert(MyElement("Alice",100));
    c.insert(MyElement("Fred",20));


    c.print_in_order(std::cout);

    cout << endl << "Highest Priority is " << endl << *c.peek() << endl;

    boost::optional<MyElement> alice = c.pop();
    if(alice){
        cout << "Popped results are " << *alice << endl;
    }


    cout << endl << "Now the contents are" << endl;
    c.print_in_order(std::cout);

}

将输出：

Name: Bob Priority: 10
Name: Alice Priority: 100
Name: Fred Priority: 20

Highest Priority is 
Name: Alice Priority: 100
Popped results are Name: Alice Priority: 100

Now the contents are
Name: Bob Priority: 10
Name: Fred Priority: 20
于 2013-02-28T16:04:36.777 回答