- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个使用模板类的数据结构,因此它可以存储任何数据类型 - 整数、 float 、字符串等。
因为数据会被组织起来,所以我需要一种方法来比较两个值。通常我可以使用 > 或 <,但在字符串的情况下不起作用,因为在字符串上使用 >/< 运算符不会告诉我哪个按字母顺序排在第一位。为此,我需要使用 compare() 函数。
然而,由于数据结构是一个模板类,我无法告诉它使用 compare() 函数,因为除了字符串之外,它无法识别 compare() 函数。
作为变通方法,我尝试编写两个比较函数:
template (class t)
int BinaryTree<T>::compareVals(T v1, T v2);
和
template (class t)
int BinaryTree<T>::compareVals(string v1, string v2);
因此在值为字符串类型的情况下,程序将使用其中带有 compare() 函数的方法。
但是尝试这样做时,我收到一个编译器错误,基本上告诉我我不能重载该函数。
所以我没有想法。我怎样才能让这个模板类正确地比较和排序字符串以及数字?
非常感谢您的意见!
这里是整个类,供引用:
#ifndef binarytree_class
#define binarytree_class
#include <iostream>
#include <string>
#include <vector>
using std::cout;
using std::string;
using std::vector;
template <class T>
class BinaryTree{
public:
struct TreeNode{
TreeNode * leftChild,
* rightChild;
T key;
vector<T> data;
int size;
};
BinaryTree();
~BinaryTree();
bool isEmpty();
int getSize();
void add(T key, T data);
void remove(T key);
int getHeight();
bool keyExists(T key);
int getKeyHeight(T key);
void displayAll();
private:
int size;
TreeNode * root;
TreeNode * findParent(TreeNode * start, TreeNode * child); //finds the parent node of child in subtree starting at root start
TreeNode * findNode(TreeNode * node, T input); //find node with data input in subtree at root node
TreeNode * findMin(TreeNode * node);
void removeNode(TreeNode * node); //Small part of algorithm (case: 2 children) borrowed from tech-faq.com/binary-tree-deleting-a-node.html
void displaySubTree(TreeNode * node); //displays subtree starting at node
void sortAdd(TreeNode * eNode, TreeNode * nNode); //adds a new node nNode to subtree starting at root eNode
void destroySubTree(TreeNode * node); //destroys subtree starting at node.
void display(TreeNode * node, string indent, bool last); //Algorithm borrowed from http://stackoverflow.com/questions/1649027/how-do-i-print-out-a-tree-structure
char leftOrRight(TreeNode * eNode, TreeNode * nNode); //compares keys in existing node vs new node and returns L or R
int calcHeight(TreeNode * node, int depth); //calculates the height from node. Algorithm borrowed from wiki.answers.com
int compareVals(T v1, T v2);
int compareVals(string v1, string v2);
};
template <class T>
BinaryTree<T>::BinaryTree<T>() : size(0){}
template <class T>
bool BinaryTree<T>::isEmpty(){
return (!size);
}
template <class T>
int BinaryTree<T>::compareVals(T v1, T v2){
int result;
v1 <= v2? result = -1 : result = 1;
return result;
}
template <class T>
int BinaryTree<T>::compareVals(string v1, string v2){
int result;
result = v1.compare(v2);
if(result >= 0)
result = -1;
else
result = 1;
return result;
}
template <class T>
int BinaryTree<T>::getSize(){
return size;
}
template <class T>
void BinaryTree<T>::add(T key, T data){
bool done = false;
TreeNode * temp;
if(keyExists(key)){
temp = findNode(root,key);
temp->size++;
temp->data.push_back(key);
}
else{
temp = new TreeNode;
temp->leftChild = 0;
temp->rightChild = 0;
temp->key = key;
temp->size = 0;
temp->data.push_back(data);
if(isEmpty())
root = temp;
else
sortAdd(root, temp);
size++;
}
}
template <class T>
void BinaryTree<T>::sortAdd(TreeNode * eNode, TreeNode * nNode){
if(leftOrRight(eNode, nNode) == 'L'){
if(eNode->leftChild == 0)
eNode->leftChild = nNode;
else
sortAdd(eNode->leftChild,nNode);
} else {
if(eNode->rightChild == 0)
eNode->rightChild = nNode;
else
sortAdd(eNode->rightChild,nNode);
}
}
template <class T>
char BinaryTree<T>::leftOrRight(TreeNode * eNode, TreeNode * nNode){
char result;
if(compareVals(nNode->key, eNode->key) == -1)
result = 'L';
else
result = 'R';
return result;
}
template <class T>
void BinaryTree<T>::displayAll(){
display(root,"",true);
}
template <class T>
void BinaryTree<T>::display(TreeNode * node, string indent, bool last){
if(!isEmpty()){
cout << indent;
if(last){
cout << "\\-";
indent += " ";
} else {
cout << "|-";
indent += "| ";
}
cout << node->key << "\n";
if(node->leftChild != 0)
display(node->leftChild, indent, false);
if(node->rightChild != 0)
display(node->rightChild, indent, true);
} else
cout << "TREE IS EMPTY" << "\n\n";
}
template <class T>
int BinaryTree<T>::getHeight(){
if(!root)
cout << "ERROR: getHeight() root is NULL!" << "\n";
int result;
if(isEmpty())
result = 0;
else
result = calcHeight(root, 1);
return result;
}
template <class T>
int BinaryTree<T>::getKeyHeight(T key){
int result = -1;
if(!keyExists(key))
cout << "ERROR: Trying to get height of nonexistant key " << key << "\n";
else{
TreeNode * temp = findNode(root, key);
result = getHeight() - calcHeight(temp,1);
}
return result;
}
template <class T>
int BinaryTree<T>::calcHeight(TreeNode * node, int depth){ //Algorithm borrowed from wiki.answers.com
int leftDepth,
rightDepth,
result;
if(node->leftChild)
leftDepth = calcHeight(node->leftChild, depth+1);
else
leftDepth = depth;
if(node->rightChild)
rightDepth = calcHeight(node->rightChild, depth+1);
else
rightDepth = depth;
if(leftDepth > rightDepth)
result = leftDepth;
else
result = rightDepth;
return result;
}
template <class T>
void BinaryTree<T>::remove(T input){
if(!keyExists(input))
cout << "ERR: trying to remove nonexistant key " << input << "\n";
else{
TreeNode * temp = findNode(root,input);
removeNode(temp);
}
}
template <class T>
bool BinaryTree<T>::keyExists(T key){
bool result;
if(isEmpty())
result = false;
else{
if(findNode(root,key) != 0)
result = true;
else
result = false;
}
return result;
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findNode(TreeNode * node, T input){
TreeNode * result = 0; //Returns 0 if none found
if(node->key == input)
result = node;
else{
if(node->leftChild != 0)
result = findNode(node->leftChild, input);
if(result == 0 && node->rightChild != 0)
result = findNode(node->rightChild, input);
}
return result;
}
template <class T>
void BinaryTree<T>::removeNode(TreeNode * node){
TreeNode * parent = 0;
if(node != root)
parent = findParent(root,node);
if(node->leftChild && node->rightChild){ //Case: both children (algorithm borrowed from tech-faq.com)
TreeNode * temp = findMin(node->rightChild);
string tkey = temp->key;
removeNode(temp);
node->key = tkey;
} else {
if(parent){
if(!(node->leftChild) && !(node->rightChild)){ //case: no children & not root
if(parent->leftChild == node)
parent->leftChild = 0;
else
parent->rightChild = 0;
}
if(!(node->leftChild) && node->rightChild){ //case: right child only & not root
if(parent->leftChild == node)
parent->leftChild = node->rightChild;
else
parent->rightChild = node->rightChild;
}
if(node->leftChild && !(node->rightChild)){ //case: left child only & not root
if(parent->leftChild == node)
parent->leftChild = node->leftChild;
else
parent->rightChild = node->leftChild;
}
delete node;
size--;
}
else{
if(node->leftChild) //case: left child only & root
root = node->leftChild;
else //case: right child only & root
root = node->rightChild;
delete node; //case: no children & root intrinsically covered
size--;
}
}
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findMin(TreeNode * node){
TreeNode * result;
if(node->leftChild == 0)
result = node;
else
result = findMin(node->leftChild);
return result;
}
template <class T>
typename BinaryTree<T>::TreeNode * BinaryTree<T>::findParent(TreeNode * start, TreeNode * child){
TreeNode * result = 0;
if(start->leftChild){
if(start->leftChild->key == child->key)
result = start;
else
result = findParent(start->leftChild, child);
}
if(start->rightChild && result == 0){
if(start->rightChild->key == child->key)
result = start;
else
result = findParent(start->rightChild, child);
}
return result;
}
template <class T>
void BinaryTree<T>::destroySubTree(TreeNode * node){
TreeNode * parent = 0;
if(node != root)
parent = findParent(root,node);
if(node->leftChild)
destroySubTree(node->leftChild);
if(node->rightChild)
destroySubTree(node->rightChild);
if(parent){
if(parent->leftChild == node)
parent->leftChild = 0;
else
parent->rightChild = 0;
}
size--;
delete node;
}
template <class T>
BinaryTree<T>::~BinaryTree<T>(){
if(!isEmpty())
destroySubTree(root);
}
#endif
最佳答案
当 T
是 std::string
时,您最终将不得不使用具有相同签名的函数,这就是您的编译器提示的原因。要克服这个问题,只需将 compareVals
设为它自己的模板即可。我还建议您将它们设为 static
,这样您就可以在没有对象的情况下调用它们。
static int compareVals(std::string const& v1, std::string const& v2)
{
//compare std::string
}
template<typename U>
static int compareVals(U v1, U v2)
{
//compare everything else
}
事实上,std::string
does have built in relational operators ,因此对于您的特定用例,可能没有必要像上面那样定义比较函数。无论如何,这种方法可能仍然有用,可以避免假设运算符是为您的 BinaryTree
将来可能最终支持的每种数据类型定义的。
关于c++ - 如何比较作为模板类传递的字符串?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19085170/
如何使用 SPListCollection.Add(String, String, String, String, Int32, String, SPListTemplate.QuickLaunchO
我刚刚开始使用 C++ 并且对 C# 有一些经验,所以我有一些一般的编程经验。然而,似乎我马上就被击落了。我试过在谷歌上寻找,以免浪费任何人的时间,但没有结果。 int main(int argc,
这个问题已经有答案了: In Java 8 how do I transform a Map to another Map using a lambda? (8 个回答) Convert a Map>
我正在使用 node + typescript 和集成的 swagger 进行 API 调用。我 Swagger 提出以下要求 http://localhost:3033/employees/sear
我是 C++ 容器模板的新手。我收集了一些记录。每条记录都有一个唯一的名称,以及一个字段/值对列表。将按名称访问记录。字段/值对的顺序很重要。因此我设计如下: typedef string
我需要这两种方法,但j2me没有,我找到了一个replaceall();但这是 replaceall(string,string,string); 第二个方法是SringBuffer但在j2me中它没
If string is an alias of String in the .net framework为什么会发生这种情况,我应该如何解释它: type JustAString = string
我有两个列表(或字符串):一个大,另一个小。 我想检查较大的(A)是否包含小的(B)。 我的期望如下: 案例 1. B 是 A 的子集 A = [1,2,3] B = [1,2] contains(A
我有一个似乎无法解决的小问题。 这里...我有一个像这样创建的输入... var input = $(''); 如果我这样做......一切都很好 $(this).append(input); 如果我
我有以下代码片段 string[] lines = objects.Split(new string[] { "\r\n", "\n" }, StringSplitOptions.No
这可能真的很简单,但我已经坚持了一段时间了。 我正在尝试输出一个字符串,然后输出一个带有两位小数的 double ,后跟另一个字符串,这是我的代码。 System.out.printf("成本:%.2
以下是 Cloud Firestore 列表查询中的示例之一 citiesRef.where("state", ">=", "CA").where("state", "= 字符串,我们在Stack O
我正在尝试检查一个字符串是否包含在另一个字符串中。后面的代码非常简单。我怎样才能在 jquery 中做到这一点? function deleteRow(locName, locID) { if
这个问题在这里已经有了答案: How to implement big int in C++ (14 个答案) 关闭 9 年前。 我有 2 个字符串,都只包含数字。这些数字大于 uint64_t 的
我有一个带有自定义转换器的 Dozer 映射: com.xyz.Customer com.xyz.CustomerDAO customerName
这个问题在这里已经有了答案: How do I compare strings in Java? (23 个回答) 关闭 6 年前。 我想了解字符串池的工作原理以及一个字符串等于另一个字符串的规则是
我已阅读 this问题和其他一些问题。但它们与我的问题有些无关 对于 UILabel 如果你不指定 ? 或 ! 你会得到这样的错误: @IBOutlet property has non-option
这两种方法中哪一种在理论上更快,为什么? (指向字符串的指针必须是常量。) destination[count] 和 *destination++ 之间的确切区别是什么? destination[co
This question already has answers here: Closed 11 years ago. Possible Duplicates: Is String.Format a
我有一个Stream一个文件的,现在我想将相同的单词组合成 Map这很重要,这个词在 Stream 中出现的频率. 我知道我必须使用 collect(Collectors.groupingBy(..)
我是一名优秀的程序员,十分优秀!