CODEWITHSUNDEEP
c++c++11containers
Maravedis
Maravedis

Reputation: 23

Ordering a container on something else than the key

I am currently trying to implement a A* algorithm and I've come to a problem :

I want to keep a set of distinct objects, identified by a hash (I've used boost::hash and family, but can use anything else) and ordered by a public int value, member of those objects.

The goal is being able to retrieve the smaller object based on the int value in O(1) and guarantee uniqueness in the most efficient manner (hash seemed a good way to achieve that, but i'm open to alternatives). I don't need to iterate over the container if those two conditions are met.

Is there any already present implementation that answer those specifications ? Am I mistaken in my assumptions ? Should I just extend any existing container ?

EDIT :

Apparently unclear on what "smaller based on int value" means. I mean that my object has a public attribute (lets say score). For two objects a and b, a < b if and only if a.score < b.score.

I want a and b to be in a container, ordered by score. And if I try to insert c with c.hash == a.hash, I want the insertion to fail.

Upvotes: 2

Views: 179

Answers (3)

Toby Speight
Toby Speight

Reputation: 30831

Although std::priority_queue is an adapter, its Container template parameter has to satisfy SequenceContainer, so you can't build one backed by a std::set.

It looks like your best option is to maintain both a set and a priority queue, and use the former to control insertion into the latter. It may be a good idea to encapsulate that into a container-concept class, but you might get away with a couple of methods if your use of it is quite localised.

Upvotes: 1

lezebulon
lezebulon

Reputation: 7994

use a custom comparator and a std::set :

#include <set>
#include <string>

struct Object
{
  int value;
  long hash;

  std::string data;

  Object(int value, std::string  data) :
    value(value), data(data)
  {

  }

  bool operator<(const Object& other) const
  {
    return data < other.data;
  }

};

struct ObjComp1
{

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

};

struct ObjComp2
{

  bool operator()(const Object& lhs, const Object& rhs) const
  {
    if (lhs.value != rhs.value)
    {
      return lhs.value < rhs.value;
    }

    return lhs < rhs;
  }

};

int main()
{

  Object o1(5, "a");
  Object o2(1, "b");
  Object o3(1, "c");
  Object o4(1, "c");

  std::set<Object, ObjComp1> set;
  set.insert(o1);
  set.insert(o2);
  set.insert(o3);
  set.insert(o4);

  std::set<Object, ObjComp2> set2;
  set2.insert(o1);
  set2.insert(o2);
  set2.insert(o3);
  set2.insert(o4);

    return 0;
}

First variant will allow you to only insert o1 and o2, second variant will allow you to insert o1, o2 and o3, as it's not really clear which one you need. The only downside is that you need to code your own operator< for the Object type.

alternatively if you don't want to create a custom operator< for you data type, you can wrap a std::map > but this is less straightforward

Upvotes: 0

lrleon
lrleon

Reputation: 2648

You could use the stl type priority_queue. If your elements are integers then you could do:

priority_queue<int> q;

Priority queues are internally implemented with heaps, a complete binary tree whose root always is the minimum element of the set. So, you could consult in O(1) by invoking top().

However, as you algorithm progress, you will need extract the items with pop(). Since is a binary tree, the extraction takes O(log N), which it is not O(1), but is a very good time and it is guaranteed, by contrast with a expected time, which would be the case for an imperfect hash table .

I do not know a way for maintaining a set and extracting the minimum in O(1).

Upvotes: 0

Related Questions