소계가 아닌 술어가없는 정렬 된 순서 유지

Question

정렬 된 대기열을 유지하려는 경우 가장 낮은 값 (비트가 std::priority_queue 인 항목)을 팝업 할 수 있기를 원합니다. 항목 값은 연속적이며 계속 증가합니다. 그러나 항목의 비교가 정의 된 것보다 작지 않으며 is-previous 및 is-next 술어 (A is-previous B ==) 만 있고 ++ 또는 --도 지원합니다.

이러한 술어를 기반으로 (부분적으로) 값을 정렬하는 알고리즘이 있는지 궁금합니다. 또는 대기열을 추적하는 더 좋은 방법이 있습니까?

이 문제는 모듈로 산술로 작업 할 때 발생합니다. 즉, 항목이 정수로 지정되었지만 모듈로 인해 의미가 작아지고 더 이상 중요하므로 더 이상 정렬 할 수 없습니다.

선택 언어는 C++이지만 대부분의 합리적인 언어를 포팅 할 수 있습니다.

편집 예제 코드를 작성하면서 답변을 위해 노력하는 모든 사람들에게

Appologies, 나는 원래의 질문이 잘못 형성 깨달았다. 정말로 embarasing하고 있습니다 만, 나는 당신의 시간이 낭비되지 않았 음을 강조하고 싶습니다. 제가 한 시간 동안 땀을 흘렸을 때, 그리고 나서 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 술어를 사용하여 더 빨리 만들 수있는 방법이 있습니까?

Answer 1

제 문제는 Pop()이 O (N)을 사용한다는 것입니다. is-prev와 is-next 술어를 사용하여 더 빨리 만들 수있는 방법이 있습니까?

키의 실제 모듈화 정수 표현 (예 : Integer(x))을 얻는 방법을 제공해야합니다. 그런 다음 Push 및 Pop 둘 다 일정 시간 내에 수행 할 수 있습니다.

당신은 정수와 계수 M이있는 경우, 큰

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

M 경우로 queues[Integer(x)].push_back(x)으로 Push(x) 및 Pop을 구현, 이중 연결리스트 (std::list<T> queues[M])의 배열을 사용하고 대부분의 기대 대기열이 대부분 비어 있으면 std::unordered_map<size_t, std::list<T>>을 사용하여 동일한 복잡성을 얻지 만 공간을 절약 할 수 있습니다.

std::deque도 사용될 수있다. 두 작업에 대해 상각 된 일정 시간 만 제공하지만 실제로는 훨씬 빨라질 수 있습니다.

Answer 2

C++에서 형식을 정렬하거나 연관 컨테이너로 사용하기 위해 operator<을 정의 할 필요가 없습니다. A 테이너와 알고리즘은 비교를 수행하는 술어를 사용할 수 있습니다.

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 인 관계가 엄격한 약한 순서 여야한다는 것입니다.