保留已排序的序列而没有小于谓词

我想保留一个排序的项目队列，我希望能够弹出具有最低值的项目（有点像std::priority_queue）。项目值是连续的并且不断增加。但是，这些项目没有定义少于比较的对象，它们只有is-previous和is-next谓词（其中A is-previous B == B is-next A），它们也支持++或--。保留已排序的序列而没有小于谓词

我不知道是否有任何算法（部分）根据这些谓词排序值？或者，有没有更好的方法来跟踪这样的队列？

在模运算中工作时出现此问题 - 项由整数指定，但由于模，小于和大于，失去其含义，不能用于排序了。

选择的语言是C++，但我想我可以移植大部分合理的语言。

编辑

Appologies所有的人试图回答，一边写代码示例，我意识到是病态的原题。这真是令人尴尬，但我想强调，你的时间并没有浪费，因为我汗流one背了一个小时，然后在10分钟内我意识到这是错误的。无论如何，这是行为我想：

template <class T> 
class OrderedQueue { 
    std::vector<T> storage; 
    T next; 

public: 
    OrderedQueue(T lowest_value = T()) 
     :next(lowest_value) 
    {} 

    void Push(T t) 
    { 
     storage.push_back(t); 
    } 

    T Pop() 
    { 
     std::vector<T>::iterator it = std::find(storage.begin(), storage.end(), next); 
     if(it == storage.end()) 
      throw std::runtime_error("no such element"); 
     T value = *it; 
     storage.erase(it); 
     ++ next; 
     return value; 
    } 
};

我的问题是Pop()需要O(N)。有没有办法让它更快，使用is-prev和is-next谓词？

来源

2014-09-20 the swine

为什么你需要对它们进行排序？你不能在中间添加任何东西！ – Basilevs 2014-09-20 17:54:46

@Basilevs我想对它们进行排序，因为保持排序的数组通常比未排序的数组快。无论如何，我无法使用'std :: priority_queue'，因为它需要一个比谓词少的谓词。我会使用'std :: vector'来存储这些值，并且在那里你可以很容易'vector.insert（where，1，what）'。 – 2014-09-20 18:03:32

换行，并禁止除开始和结束之外的任何插入操作。 – Basilevs 2014-09-20 18:04:28

我的问题是Pop（）需要O（N）。有没有办法让它更快，使用is-prev和is-next谓词？

您需要提供一种方法来获取密钥的实际模块化整数表示，如Integer(x)。然后Push和Pop都可以在恒定时间执行。

如果你有整数和模量M，使用双向链表（std::list<T> queues[M]）的阵列，实现Push(x)为queues[Integer(x)].push_back(x)和Pop作为

size_t i = Integer(next); 
// check for existence, raise if necessary 
T r = queues[i].front(); 
queues[i].pop_front(); 
return r;

如果M大，你预期大部分的队列在大部分时间都是空的，那么你可以使用std::unordered_map<size_t, std::list<T>>来获得相同的复杂度，但节省空间。

也可以使用std::deque;它只为两种操作提供分摊的恒定时间，但在实践中可能会快很多。

来源

2014-09-20 23:21:11

这并不总是每个队列最多存储一个整数（假设它们不重复，但会稳步增加 - 对于您的实现来说最差的情况）？我同意这会起作用，但这会非常低效！如果'M = 2^32'怎么办？如果我能得到整数表示，我可以使用'std :: set'或'std :: map'并且同时使用Push（）和Pop（）对数时间。 – 2014-09-21 08:23:42

@theswine如果M很大，则使用'unordered_map >'来获得持续时间的推送和弹出。查看更新的答案。 – 2014-09-21 12:21:57

这确实是最快的解决方案，虽然不是很大。在问题中描述的“OrderedQueue”中插入100k元素比使用“std :: unordered_map”慢100毫秒。这可以通过更好的编译器或更好的STL实现来改善。 – 2014-09-22 14:05:16

在C++中，您的类型不需要将operator<定义为排序或将用于关联容器中。容器和算法可以执行比较的谓词。

std::sort(v.begin(), v.end(), is_pred);

如果没有，你可以写自己的仿函数适配器或拉姆达：例如，要使用is_pred作谓语（假设它已经是一个函数对象或纯函数）排序向量

std::sort(v.begin(), v.end(), [](T const& lhs, T const& rhs) { 
      return apply_is_pred_predicate(lhs,rhs) 
      });

这里的要求是，关系是-prev必须是严格的弱顺序。

来源

2014-09-20 18:29:05

是的，这是行不通的，因为所描述的谓词不是“严格的弱排序”。但是，谢谢。 – 2014-09-20 18:30:21

是的，is_previous显然没有定义严格的弱顺序。 – 2014-09-20 18:31:35

保留已排序的序列而没有小于谓词

回答

相关问题