C++::stl::map::declaration error

Tr!n! · Jan 2, 2004

hey all,

first i should say ive been using java for most of my programming, but now we have to make some kind of a priority heap in C++ and stl for school. I managed to solve all the compile errors but one ..
I think it has a quite simple solution but really cant find it

Code:

template <class P, class D> // P = priority class, D = data class
class PHeap {
 private:
  priority_queue<P> PQueue;  // priority queue with our priorities, not containing the data
  map<P, list<D> >   DMap;    // Map with a list of data for every key 
   
 public:
  PHeap();
  ~PHeap();
  bool isEmpty();
  D getRoot();  
  void removeRoot();
  void insert(P,D);
};

template <class P, class D>
PHeap<P,D>::PHeap(){
  PQueue = *( new priority_queue<P>() );
  
  map<P,D> test;
  
  DMap = *(new map<P,D>() ) ;
}
...

compiler likes initializing of PQueue and test, but throws error on the DMap initialization :

a

Code:

PHeap.h: In constructor `PHeap<P, D>::PHeap() [with P = int, D = int]':
PHTest.cpp:5:   instantiated from here
PHeap.h:43: error: no match for 'operator=' in 'this->PHeap<int, int>::dDMap =
   (operator new(unsigned int)(12), ((true, (<anonymous>->std::map<_Key, _Tp,
   _Compare, _Alloc>::map() [with _Key = int, _Tp = int, _Compare =
   std::less<int>, _Alloc = std::allocator<std::pair<const int, int> >](),
   (<anonymous> <unknown operator> false))), <anonymous>))'
/usr/include/g++/bits/stl_map.h:213: error: candidates are: std::map<_Key, _Tp,
   _Compare, _Alloc>& std::map<_Key, _Tp, _Compare, _Alloc>::operator=(const
   std::map<_Key, _Tp, _Compare, _Alloc>&) [with _Key = int, _Tp =
   std::list<int, std::allocator<int> >, _Compare = std::less<int>, _Alloc =
   std::allocator<std::pair<const int, std::list<int, std::allocator<int> > >
   >]

any ideas?

tnx

Uller · Jan 2, 2004

Type mismatch. DMap is of type map<P, list<D>>, and you're trying to initialize it with a map<P,D>.

BTW, you've got a memory leak in the above. C++ isn't garbage collected like Java is -- in your present code, every time you create the heap, you're spitting a priority queue and a map into memory that will stay there forever until your program quits or your machine runs out of memory. Anything created with the new operator needs to be deleted with the delete operator. C++ doesn't need the new operator to create objects like Java -- if you say, map<int, string> test;, test is fully constructed at that time. new is used to create a new object on the fly and store a pointer to it, in this case of type map<int, string> *, which is deleted later.

If that isn't what you wanted, you can just leave PQueue and DMap uninitialized, and they'll stay alive as long as the PHeap containing them is alive. If you really do want them on the heap/freestore, consider using boost::shared_ptr<T>, which is a reference-counted pointer providing similar abilities to Java with a few caveats.

Uller · Jan 2, 2004

Just to be thorough, examples. I suggest using the non-pointer solution unless you absolutely know you need it.

Non-pointer version (easiest to do, but may be problematic in 1% of possible uses):

Code:

(same definition as above)

template <class P, class D>
PHeap<P,D>::PHeap()
: PQueue(/*pqueue initial value*/), DHeap(/*dheap initial value*/)
{
    /* other various init... */
}

/* no cleanup needed -- PQueue and DHeap are forcibly destroyed when PHeap dies */

pointer version without shared_ptr (lacks problems, but very hard to maintain):

Code:

template <class P, class D> // P = priority class, D = data class
class PHeap {
 private:
  priority_queue<P> * PQueue;  // pointer to priority queue with our priorities, not containing the data
  map<P, list<D> > * DMap;    // pointer to Map with a list of data for every key 
...
};   

template <class P, class D>
PHeap<P,D>::PHeap()
: PQueue(new priority_queue<P>(/*pqueue initial value*/)), DHeap(new map<P, list<D> >(/*dheap initial value*/))
{
    /* other various init... */
}

template <class P, class D>
PHeap<P,D>::~PHeap()
{
    /* have to clean these up after they're new'ed, or memory leaks abound */
    delete PQueue;
    delete DHeap;
}

pointer version with shared_ptr (best of both worlds):

Code:

#include <boost/shared_ptr.hpp>
using namespace boost;

template <class P, class D> // P = priority class, D = data class
class PHeap {
 private:
  shared_ptr<priority_queue<P>> PQueue;  // reference-counted pointer to priority queue with our priorities, not containing the data
  shared_ptr<map<P, list<D> > > DMap;    // reference-counted Map with a list of data for every key 
...
};   

template <class P, class D>
PHeap<P,D>::PHeap()
: PQueue(new priority_queue<P>(/*pqueue initial value*/)), DHeap(new map<P, list<D> >(/*dheap initial value*/))
{
    /* other various init... */
}

/* no cleanup needed -- shared_ptr automatically destroys PQueue and DHeap when nothing's using them... i.e. when PHeap dies */

Tr!n! · Jan 2, 2004

Thanks, shoud really look into that boost thingie .. but only saw your latest post when i was almost ready ..

Right now its compiling and running but something still wrong, in insert function i think.
I know FAQ says i should do my schoolwork myself but i'm sure one little hint should do it ...
Its really frustrating, i know i coud do this in half an hour in java but this C++ is killing me !!!
So as you can see, in the output im getting value 134516083 where i should get 3 5 2 4 1

Code:

#ifndef PHEAP_H_
#define PHEAP_H_

#include <queue>
#include <map>
#include <list>

using namespace std;



template <class P, class D> // P = priority class, D = data class
class PHeap {
 private:
  priority_queue<P>* PQueue;  // priority queue with our priorities, not containing the data
  map<P, list<D> >*  DMap;    // Map with a list of data for every key 
  
   
 public:
  PHeap();
  ~PHeap();
  bool isEmpty();
  D getRoot();  
  void removeRoot();
  void insert(P,D);
};

template <class P, class D>
PHeap<P,D>::PHeap(){
  PQueue = new priority_queue<P>() ;  
  DMap = new map<P,list<D> >() ;
}

template <class P, class D>
PHeap<P,D>::~PHeap(){   
  delete PQueue;
  delete DMap;  
}

template <class P, class D>
bool PHeap<P,D>::isEmpty(){
  return PQueue->empty();
}

template <class P, class D>
D PHeap<P,D>::getRoot(){ 
  D result;
  
  if ( !PQueue->empty() ){
    P key = PQueue->top();
    cout << "key = " << key << endl;
    list<D> l = (*DMap)[ key ]; // is  OK => if map does not conain such object, operator[] inserts the default object data_type()
    if ( !l.empty() ){
      result = *l.begin();
      cout << "**" << endl;
    }
    // should not happen
    else cout << "getRoot::empty queue for list with root ... " << endl;
  }  
  return result;
}

template <class P, class D>
void PHeap<P,D>::removeRoot(){
  if ( !PQueue->empty() ){
    P key = PQueue->top();
    list<D> l = (*DMap)[ key ]; 
    if ( !l.empty() ){
      l.pop_front();
      cout << "list size = " << l.size() << endl;
      if ( l.empty() ){ // list with data with priority = key is now empty => remove from PQueue
	PQueue->pop();  
      }
    }
    else {
      // should not happen
      PQueue->pop();
      cout << "removeRoot::empty queue for list with root ... " << endl;
    }
      
  }
}
    
template <class P, class D>
void PHeap<P,D>::insert(P prior, D data){
  // first look up if this priority is already used or not 
  list<D> l = (*DMap)[ prior ]; 
  if ( !l.empty() ){  // used
    l.push_back( data );
  } 
  else { // not used
    // l is our new list ... 
    //    l = *(new list<D>());
    list<D> l2;
    l2.push_back( data );
    PQueue->push( prior );
    //DMap[ prior ] = data ; ?? not working ...
    DMap->insert( map<P,list<D> >::value_type(prior,l2) ); // aha! 
  }
}

phtest.cpp

Code:

#include <iostream>
#include "PHeap.h"


int main(void){
  PHeap<int,int> PH;
  PH.insert(1,1);
  PH.insert(2,2);
  PH.insert(3,3);
  PH.insert(1,4);
  PH.insert(2,5);


  while ( !PH.isEmpty() ){
    cout << PH.getRoot() << endl;
    PH.removeRoot();
  }

  return 0;
}

output:

Code:

key = 3
getRoot::empty queue for list with root ...
134516083
removeRoot::empty queue for list with root ...
key = 2
getRoot::empty queue for list with root ...
134516083
removeRoot::empty queue for list with root ...
key = 2
getRoot::empty queue for list with root ...
134516083
removeRoot::empty queue for list with root ...
key = 1
getRoot::empty queue for list with root ...
134516083
removeRoot::empty queue for list with root ...
key = 1
getRoot::empty queue for list with root ...
134516083

Thanks alot if anyone could help me

Velox · Jan 2, 2004

It's been a while since I dabbled in C++, but I don't think you're inserting into the map correctly. It looks like insert takes a STD:

air, not a map. Try inserting a pair instead of a map, and see if that fixes things.

tim_m · Jan 3, 2004

not that i know c++ in any way to actually help you, but you may want to disable smilies in posts that may have certain smiley letter combinations like in your original code. no big deal, just noticing

Tr!n! · Jan 3, 2004

phew got it working at last ... seems like the list<D> l = (*DMap)[ key ]; didnt quite worked ok for retrieving map values ... think i desirve a nice cold belgian beer now

ill print here the insert function i case anyone is interested :

Code:

template <class P, class D>
void PHeap<P,D>::insert(P prior, D data){
  // debug
    cout << "inserting: prior = " << prior << ", data = " << data << endl;
  // first look up if this priority is already used or not 
  typename map<P, list<D> >::iterator it; 
  it = DMap->find( prior );
  list<D> l;
  if ( it != DMap->end() ){ // already used ..
    l = (list<D>)((*it).second);
    l.push_back( data );
    DMap->insert( map<P,list<D> >::value_type(prior,l) );
  }
  else { // not used
    l.push_back( data );
    PQueue->push( prior );
    DMap->insert( map<P,list<D> >::value_type(prior,l) );
  }
  //debug
  cout << "prior list contains now : " << endl; 
  for ( typename list<D>::iterator i = l.begin() ; i != l.end() ; i++ ) cout << *i << " " ;
  cout << endl;
  
}

one last question though: is it possible to use templates in a typedef ?
I tried :

Code:

template <class P, class D> 
typedef map<P, list<D> >* datamap ;

wich my compliler didnt quite like ...

@tim : sorry about the smilies, should be disabled by default between code tags tho

grtz!

MonkeyShave · Jan 3, 2004

Re: template typedef

Currently the language does not define a template typedef, byt the next revision of the language standard may. There's a (little-used IME) C++ idiom that approximates the functionality, described here.

MonkeyShave · Jan 3, 2004

Code:

  it = DMap->find( prior );
  list<D> l;
  if ( it != DMap->end() ){ // already used ..
    l = (list<D>)((*it).second);
    l.push_back( data );
    DMap->insert( map<P,list<D> >::value_type(prior,l) );
  }

You may also want to review this chunk of code. If you perform a duplicate insert into a std::map, the second insert() never occurs, the return value from the form of insert you're performing is std:air<iterator, bool>, the bool member indicates whether the insert actually added an element or not. To achieve your goal here, you can modify the element in-place (using it).

You may also want to consider using operator-> for indirect element access, the code (*it).field_name and it->field_name are equivalent, but C++ programmers would be more likely to use the -> idiom.

By all means look at the boost libraries, they are very helpful and contain powerful tools like boost::function and boost::bind. boost::bind can be tricky to use, but it essentially lets you transform functions in useful ways (it returns a functor which will call the original function with some arguments already specified).

Eidt: formatting

Tr!n! · Jan 4, 2004

Thanks for the tips, ill certainly take a look at it

http://www.gotw.ca/ looks interesting also

Must say this has been a nice exercise to fresh up my (minor) C++ skills again

Grtz!

C++::stl::map::declaration error

Tr!n!

Weaksauce

Uller

2[H]4U

Uller

2[H]4U

Tr!n!

Weaksauce

Velox

Gawd

tim_m

i'm so nice

Tr!n!

Weaksauce

MonkeyShave

Limp Gawd

MonkeyShave

Limp Gawd

Tr!n!

Weaksauce