Multimap or other ?

[ferrant]

Hi,

I need to create a stack with a key and for each key one or more instances of a data structure associated. A multi map seems to be best suited for this.

However, I don't know how I could extract an element with the maximum key value whithout knowing that max value. Is that possible with a multi-map ? Is there a special iterator for this ?

thanks for your help !!

matt-

[Narue]

It sounds like you want a priority_queue.

[ferrant]

Well, the thing is that I need the association with another data structure for a given key, but the key being needed for sorting. Practically, I have a distance measurement, and an x,y,z coordinate associated to it. several x,y,z points can have the same distance measurement, but I need the sorting only on the key.

Is there a thing like a multi-priority-queue ?

[Narue]

>Is there a thing like a multi-priority-queue ?
That's what a priority_queue is. It's an adapter around a sequence container such as vector or deque that implements a heap. Duplicate keys are allowed, and you can do what the map does and use a pair as the value. For example, if you need to extract the largest of a collection keyed on the distance measurement, but the distance measurement is independent from the coordinates, you could set up your priority_queue like this:

#include <cstdlib>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

struct coord {
  int x, y, z;

  coord ( int ix, int iy, int iz )
    : x ( ix ), y ( iy ), z ( iz )
  {}
};

ostream& operator<< ( ostream& out, const coord& c )
{
  return out<<'('<< c.x <<','<< c.y <<','<< c.z <<')';
}

bool operator< ( const pair<int, coord>& a,
  const pair<int, coord>& b )
{
  return a.first < b.first;
}

int main()
{
  priority_queue<pair<int, coord> > pq;

  for ( int i = 0; i < 10; i++ )
    pq.push ( make_pair ( rand() % 10, coord ( i + 1, i + 2, i + 3 ) ) );

  while ( !pq.empty() ) {
    std::cout<< pq.top().first <<" -- "<< pq.top().second <<'\n';
    pq.pop();
  }
}

[ferrant]

well ... looks like you coded my problem !

Thanks alot !!!

Now, one more question : is there an easy way to avoid duplicate insertions ? i.e. same key (distance value) and x,y,z coordinates ? The thing is an x,y,z coordinate should be unique.

i was a bit confused by the title lol :lol:

look at www.multimap.com!

heh heh heh...

[Narue]

>The thing is an x,y,z coordinate should be unique.
That's more difficult. If you need that kind of flexibility while still having priority queue semantics, you can eschew the adapter entirely and go manual with the make_heap, push_heap, pop_heap functions, and your desired scheme for removing duplicates. But a smarter solution would use two data structures, one for your priority queue and one for checking duplicates, such as a set:

#include <cstdlib>
#include <iostream>
#include <set>
#include <queue>
#include <utility>

using namespace std;

struct coord {
  int x, y, z;

  coord ( int ix, int iy, int iz )
    : x ( ix ), y ( iy ), z ( iz )
  {}
};

ostream& operator<< ( ostream& out, const coord& c )
{
  return out<<'('<< c.x <<','<< c.y <<','<< c.z <<')';
}

bool operator< ( const coord& a, const coord& b )
{
  return a.x < b.x && a.y < b.y && a.z < b.z;
}

bool operator< ( const pair<int, coord>& a,
  const pair<int, coord>& b )
{
  return a.first < b.first;
}

int main()
{
  priority_queue<pair<int, coord> > pq;
  set<coord> dup;
  int j = 0;

  for ( int i = 0; i < 10; i++ ) {
    coord save ( j, j + 1, j + 2 );

    if ( dup.find ( save ) == dup.end() ) {
      pq.push ( make_pair ( rand() % 10, save ) );
      dup.insert ( save );
    }

    if ( i % 3 == 0 )
      ++j;
  }

  while ( !pq.empty() ) {
    std::cout<< pq.top().first <<" -- "<< pq.top().second <<'\n';
    pq.pop();
  }
}

Naturally, this can be improved, just like everything I write in a few minutes. ;)