c++ - 在 C++ 中使用 <elem> 对函数

Question

我正在写一个项目，用对象 ID 和优先级创建最大堆 优先级是一个要比较的整数。 对象 ID 可以是 int、char 或 string。

我创建了一个堆中必需的比较函数。

class pairpairCompare {
public:
  static bool lt(pair<int,int> x, pair<int,int> y) { return x.second < y.second; }
  static bool eq(pair<int,int> x, pair<int,int> y) { return x.second == y.second; }
  static bool gt(pair<int,int> x, pair<int,int> y) { return x.second > y.second; }
};

它非常适合 pair<int, int>* pairArr=new pair<int, int>[maxArrayRoom];

通过调用

maxheap<pair<int, int>,pairpairCompare> PairTtest(pairArr,0,maxArrayRoom);

现在我想更新 pair<char, int>* pairArr=new pair<int, int>[maxArrayRoom];或 pair<string, int>* pairArr=new pair<int, int>[maxArrayRoom];可以工作

我试过了。

template <class Elem>
class pairpairCompare {
public:
  static bool lt(pair<Elem,int> x, pair<Elem,int> y) { return x.second < y.second; }
  static bool eq(pair<Elem,int> x, pair<Elem,int> y) { return x.second == y.second; }
  static bool gt(pair<Elem,int> x, pair<Elem,int> y) { return x.second > y.second; }
};

它返回错误。我也试过这个。仍然返回错误。

pair<template <class Elem>, int>
class pairpairCompare {
public:
  static bool lt(pair<Elem,int> x, pair<Elem,int> y) { return x.second < y.second; }
  static bool eq(pair<Elem,int> x, pair<Elem,int> y) { return x.second == y.second; }
  static bool gt(pair<Elem,int> x, pair<Elem,int> y) { return x.second > y.second; }
};

我知道这是一个简单的问题。但我来自 c# 背景，在找到上述函数的正确语法时遇到问题，以便我可以在此调用该函数。

maxheap<pair<char, int>,pairpairCompare> PairTtest(pairArr,0,maxArrayRoom); 或者 maxheap<pair<string, int>,pairpairCompare> PairTtest(pairArr,0,maxArrayRoom);

heap.h

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
// Max-heap class
template <class Elem, class Comp> class maxheap {
private:
  Elem* Heap;          // Pointer to the heap array
  int size;            // Maximum size of the heap
  int n;               // Number of elements now in the heap
  void siftdown(int);  // Put element in its correct place
public:
  maxheap(Elem* h, int num, int max)     // Constructor
    { Heap = h;  n = num;  size = max;  buildHeap(); }
  int heapsize() const       // Return current heap size
    { return n; }

  bool isLeaf(int pos) const // TRUE if pos is a leaf
    { return (pos >= n/2) && (pos < n); }
  int leftchild(int pos) const
    { return 2*pos + 1; }    // Return leftchild position
  int rightchild(int pos) const
    { return 2*pos + 2; }    // Return rightchild position
  int parent(int pos) const  // Return parent position
    { return (pos-1)/2; }
  bool insert(const Elem&);  // Insert value into heap
  bool removemax(Elem&);     // Remove maximum value
  bool remove(int, Elem&);   // Remove from given position
  void buildHeap()           // Heapify contents of Heap
    { for (int i=n/2-1; i>=0; i--) siftdown(i); }

  bool enqueue(int ObjID, int priority) 
    // inserting new element. Need the objid, priority, and reference to existing heap
{
    pair<int,int> newPair=make_pair(ObjID,priority);//creating new pair
    return insert(newPair);//calling maxheap->insert function. return success / failed. 
}

bool dequeue()
    //removing the highest priority. (priority)
{
    pair<int,int> removedPair;//create pair to received removed value
    if(removemax(removedPair))// call maxheap->remove max for removed pair
    {
        cout<<"Object ID of max priority: "<<removedPair.first<<endl;//show the removed object ID
        return true;
    }
    else
    {
        cout<<"Nothing to remove"<<endl;
        return false;
    }

}

bool changeweight(int ObjID, int newPriority)
    //changing the priority number of object ID
{
    bool returnBool=false;//set return variable success or fail

    for(int a=0;a<heapsize();a++)//sequential search to find object ID
    {
        if(pairArr[a].first==ObjID)//check whether object ID is the same
        {
            pairArr[a].second=newPriority;//update priority value
            returnBool=true;//update return variable
            break;//break array
        }
    }
    if(returnBool)//if object ID is found
    {
        buildHeap();//need to rebuild the heap coz priority variable is changed.
    }
    return returnBool;//return success or fail

}


};

template <class Elem, class Comp> // Utility function
void maxheap<Elem, Comp>::siftdown(int pos) {
  while (!isLeaf(pos)) {     // Stop if pos is a leaf
    int j = leftchild(pos);  int rc = rightchild(pos);
    if ((rc < n) && Comp::lt(Heap[j], Heap[rc]))
      j = rc;        // Set j to greater child's value
    if (!Comp::lt(Heap[pos], Heap[j])) return; // Done
    swap(Heap, pos, j);
    pos = j;         // Move down
  }
}

template <class Elem, class Comp> // Insert element
bool maxheap<Elem, Comp>::insert(const Elem& val) {
  if (n >= size) return false; // Heap is full
  int curr = n++;
  Heap[curr] = val;            // Start at end of heap
  // Now sift up until curr's parent > curr
  while ((curr!=0) &&
         (Comp::gt(Heap[curr], Heap[parent(curr)]))) {
    swap(Heap, curr, parent(curr));
    curr = parent(curr);
  }
  return true;
}

template <class Elem, class Comp> // Remove max value
bool maxheap<Elem, Comp>::removemax(Elem& it) {
  if (n == 0) return false; // Heap is empty
  swap(Heap, 0, --n);       // Swap max with last value
  if (n != 0) siftdown(0);  // Siftdown new root val
  it = Heap[n];             // Return deleted value
  return true;
}

// Remove value at specified position
template <class Elem, class Comp>
bool maxheap<Elem, Comp>::remove(int pos, Elem& it) {
  if ((pos < 0) || (pos >= n)) return false; // Bad pos
  swap(Heap, pos, --n);           // Swap with last value
  while ((pos != 0) &&
         (Comp::gt(Heap[pos], Heap[parent(pos)])))
    swap(Heap, pos, parent(pos)); // Push up if large key
  siftdown(pos);      // Push down if small key
  it = Heap[n];
  return true;
}
/*
class pairpairCompare {
public:
  static bool lt(pair<int,int> x, pair<int,int> y) { return x.second < y.second; }
  static bool eq(pair<int,int> x, pair<int,int> y) { return x.second == y.second; }
  static bool gt(pair<int,int> x, pair<int,int> y) { return x.second > y.second; }
};
*/

template<class Elem>
class pairpairCompare {
public:
  static bool lt(pair<Elem,int> x, pair<Elem,int> y) { return x.second < y.second; }
  static bool eq(pair<Elem,int> x, pair<Elem,int> y) { return x.second == y.second; }
  static bool gt(pair<Elem,int> x, pair<Elem,int> y) { return x.second > y.second; }
};

template<class Elem>
inline void swap(Elem A[], int i, int j) {
  Elem temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

Heap_Implement.cpp

#include "Heap.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

const int maxArrayRoom=20;// maximum array room. global variable. 
pair<int, int>* pairArr=new pair<int, int>[maxArrayRoom];// creating a pair array with 2 integers

template <class Elem>
//choice 0 => negative values 1 => zero and negative values, 2 => same type is fine
void GetInputValue(Elem& elemInput,int choice)// checking input values for correct types and range
{
    if(choice==0)//correct type and greater than 0 // use for integers
    {
        while (!(cin >> elemInput) || (elemInput<0) )
        {
            cin.clear(); //clear bad input flag
            cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //discard input
            cout << "Invalid input; please re-enter."<<endl;
        }
    }
    if(choice==1)//correct type and greater than 1// use for integers
    {
        while (!(cin >> elemInput) || (elemInput<=0) )
        {
            cin.clear(); //clear bad input flag
            cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //discard input
            cout << "Invalid input; please re-enter."<<endl;
        }
    }
    else if(choice==2)
    {
            while (!(cin >> elemInput))//correct type only. use for all types integers, double, char
        {
            cin.clear(); //clear bad input flag
            cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); //discard input
            cout << "Invalid input; please re-enter."<<endl;
        }
    }
}
int main()
{
    maxheap<pair<int, int>,pairpairCompare> PairTtest(pairArr,0,maxArrayRoom);//create heap with empty array
        cout<<"Press=> 1 to add. 2 to remove. 3 to change. 4 to see all array. 0 to quit"<<endl;//menus

    while(1)//infinite loop
    {   
        int inputInt=-1;//create input variable
        GetInputValue(inputInt,0);//get input
        if(inputInt==1)//adding new priority
        {
            int ObjID, priority=-1;
            cout<<"Key in Object ID"<<endl;//ask for object id
            GetInputValue(ObjID,2);
            cout<<"Key in priority"<<endl;//ask for priority id
            GetInputValue(priority,2);
            if(PairTtest.enqueue(ObjID,priority))//call enqueue to add. if succeeeded
            {
                cout<<"Succeeded"<<endl;
            }
            else//failed. may b array full / sth else
            {
                cout<<"Failed"<<endl;
            }           
        }
        else if(inputInt==2)//removing the max priority obj
        {
            PairTtest.dequeue();
        }
        else if(inputInt==3)//change the priority
        {
            int ObjID, priority=-1;
            cout<<"Key in Object ID"<<endl;//ask for object id
            GetInputValue(ObjID,2);
            cout<<"Key in priority"<<endl;//ask for priority
            GetInputValue(priority,2);
            if(PairTtest.changeweight(ObjID,priority))//call changeweight
            {
                cout<<"Succeeded"<<endl;//success
            }
            else
            {
                cout<<"Failed"<<endl;//failure. may b object is not in array

            }
        }
        else if(inputInt==4)//show heap array
        {
            cout<<"current size: "<<PairTtest.heapsize()<<endl;//show current size
            cout<<"-> Object ID & Priority"<<endl;
            for(int a=0;a<PairTtest.heapsize();a++)//loop to show all array
            {
                cout<<"-> "<< pairArr[a].first<< " & "<< pairArr[a].second<<endl;
            }
            cout<<"END of max heap"<<endl;
        }
        else if(inputInt==0)//quit
        {
            cout<<"BYE"<<endl;
            break;//quit loop
        }
        else//invalid input
        {
            cout << "Invalid input; please re-enter."<<endl;
        }

    }
    return 1;
}

Answer 1

好吧，你发布的代码给我错误:

cannot convert 'std::pair<int, int>*' to 'std::pair<char, int>*'

你的第一个意图是好的，事情是你必须改变:

pair<char, int>* pairArr=new pair<int, int>[maxArrayRoom];
pair<string, int>* pairArr=new pair<int, int>[maxArrayRoom];

由

pair<char, int>* pairArr=new pair<char, int>[maxArrayRoom];      // note "new pair<char ...
pair<string, int>* pairArr=new pair<string, int>[maxArrayRoom];  // note "new pair<string ...

您还必须实例化 pairpairCompare函数以便使用它，因为 now 是一个模板:

maxheap<pair<char, int>, pairpairCompare<char, int> > PairTtest(pairArr,0,maxArrayRoom);
maxheap<pair<string, int>,pairpairCompare<string, int> > PairTtest(pairArr,0,maxArrayRoom);

当然，正如 Jarod42 所建议的，您可以使用 vector 。

std::vector<std::pair<char, int> > pairArr(maxArrayRoom);

仍然需要将代码提供给您的错误，这可能是此答案未涵盖的内容。我利用我们可以在您的问题中看到的信息来回答这个问题。