CODEWITHSUNDEEP
c++algorithmsortingdata-structures
the swine
the swine

Reputation: 11031

Keeping sorted sequence without a less-than predicate

I want to keep a sorted queue of items, where I want to be able to pop the item with the lowest value (a bit like std::priority_queue). The item values are contiguous and ever increasing. However, the items do not have less-than comparison defined, they only have is-previous and is-next predicates (where A is-previous B == B is-next A), they also support ++ or --.

I wonder if there is any algorithm to (partially) sort values, based on such predicates? Alternately, is there a better way to keep track of such a queue?

This problem occurs when working in modulo arithmetic - the items are designated by integers, but thanks to the modulo, less than and greater than lose their meaning, and cannot be used for sorting anymore.

The language of choice is C++, but I guess I can port most of the reasonable languages.

EDIT

Appologies to all the people trying to answer, while writing the example code, I realized the original question was ill-formed. It is really embarasing, but I would like to emphasize that your time was not wasted, as I was sweating over it for one hour, and then in 10 minutes I realized how it is wrong. Anyway, this is the behavior I want:

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

My problem is that Pop() takes O(N). Is there a way to make it faster, using the is-prev and is-next predicates?

Upvotes: 1

Views: 166

Answers (2)

Fred Foo
Fred Foo

Reputation: 363858

My problem is that Pop() takes O(N). Is there a way to make it faster, using the is-prev and is-next predicates?

You need to provide a way to get to the actual modular integer representation of the key, say Integer(x). Then Push and Pop can both be performed in constant time.

If you have the integers and the modulus M, use an array of doubly-linked lists (std::list<T> queues[M]), implement Push(x) as queues[Integer(x)].push_back(x) and Pop as

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

If M is large and you expect most of the queues to be empty most of the time, then you can use a std::unordered_map<size_t, std::list<T>> to get the same complexity but save space.

An std::deque can also be used; that provides only amortized constant-time for both operations, but may well be a lot faster in practice.

Upvotes: 1

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208476

In C++ your type does not need to have operator< defined to be sorted or to be used in an associative container. The containers and algorithms can take predicates that perform the comparison. For example, to sort a vector using is_pred as the predicate (assuming that it is already a function object or a plain function):

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

If not, you can write your own functor adapter or a lambda:

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

The requirements here are that the relationship is-prev has to be a strict weak order.

Upvotes: 0

Related Questions