Using multiset with classes.

[QuasiChameleon]

Hello all,

I'm trying to use multiset with a user defined class "edge". I'm trying to use the multiset as a priority queue, and I've created a "less<edge>" via operator<() overloading.

For some reason, I cannot insert edges into the multiset.

I understand that I might also have to create an "allocator". I got some ideas for creating it at http://stackoverflow.com/questions/8220032/how-to-use-remove-if-with-erase, but still don't know how to define size_type and difference_type.

Attached is my skeleton code, running on Windows 7 (32-bit), under Netbeans IDE, using Cygwin g++ 4.7.3.

How can I get this to work? What is important is that I get a priority queue working with my edges, prioritized by the weight.

#include <iostream>
#include <set>     // for multiset

using namespace std; // assume std libraries (i.e. std::XXX)

class edge { // node, weight pair
public:
  int get_node_value() { // returns the value associated with the node.
    return id;
  }
  
  void set_node_value(const int &a) { // sets the value associated with the node to a.
    id = a;
  }
  
  double get_edge_value() { // returns the value associated to the edge.
    return weight;
  }
  
  void set_edge_value(const double &v) { // sets the value associated to the edge to v.
    weight = v;
  }
  
  edge(void):id(0),weight(1.0) {} // constructor
    
  edge(const int a):id(a),weight(1.0) { // constructor
    id = a;
    weight = 1.0;
  }
  
  edge(const int a, const double v):id(a),weight(v) { // constructor
    id = a;
    weight = v;
  }
  
  edge(const edge &e) { // copy constructor
    id = e.id;
    weight = e.weight;
  }
  
  edge& operator=(const edge &e) { //assignment constructor
    id = e.id;
    weight = e.weight;
  }
  
  bool operator<(const edge &e) { // less operator
    return weight < e.weight;
  }
  
private:
  int id; // destination node
  double weight; // edge weight
};


int main() {
  edge e(1, 5.0);
  multiset<edge> pq; // priority queue
  pq.insert(e);
}

[JLBorges]

The predicate needs to be const correct.

  // bool operator<(const edge &e) { // less operator
  bool operator<(const edge &e) const { // const-correct less operator
    return weight < e.weight;
  }

Just write one user-defined constructor; and let the other foundation operations be implicit.

  // edge(void):id(0),weight(1.0) {} // constructor
  
  /*  
  edge(const int a):id(a),weight(1.0) { // constructor
    id = a;
    weight = 1.0;
  }
  */

  edge( /*const*/ int a = 0, /*const*/ double v = 1.0 ) : id(a), weight(v) { // constructor
    id = a;
    weight = v;
  }
  
  /*
  edge(const edge &e) { // copy constructor
    id = e.id;
    weight = e.weight;
  }
  
  edge& operator=(const edge &e) { //assignment constructor
    id = e.id;
    weight = e.weight;
  }
  */

If you really want a priority queue, use a priority queue.

#include <queue>

int main() {
  edge e(1, 5.0);
  std::priority_queue<edge> pq; // priority queue
  pq.push(e);
}

[QuasiChameleon]

Thanks! That did the trick!

I reduced my constructors down to only 1, and added the const to the less operator.

Mine works fine now.

I used multiset over priority_queue based on a recommendation.

The reasoning might have been that the multiset was faster. They said that "its implementation is typically a red-black tree, so additional/removal/lookup is O(ln N)."

Since the priority_queue uses a vector container, it might be a little slower.

[JLBorges]

> Since the priority_queue uses a vector container, it might be a little slower.

It ought to be somewhat faster (insertion is still logarithmic, but better locality of reference).
http://en.cppreference.com/w/cpp/container/priority_queue