Zenoture
asked on
c++: template to work with sorted list of ints and strings
So I have finally templated the script, and it works with ints, chars, floats, and doubles, but does not like strings. How would I go about allowing this program to make a sorted list of strings based on the template?
// driver file
#include <iostream>
#include "llSorted.h"
int main()
{
llSorted<int> templatize;
templatize.init();
}
// header file - llSorted.h
#ifndef LLSORTED_H
#define LLSORTED_H
template <class itemType>
class llSorted
{
private:
struct node
{
itemType data;
node* next;
node* prev;
};
node *head, *tail, *cur;
int MAX_SIZE;
int length;
itemType temp;
int index;
int value;
int cmd;
bool found;
bool inserted;
public:
llSorted();
bool isFull();
bool isEmpty();
void init();
void printList();
void InsertItem();
void RetrieveItem();
void DeleteItem();
void getLength();
void usrVal(int);
void validation();
int exit();
};
#endif
// implementation file - llSorted.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "llSorted.h"
using std::cout;
using std::cin;
using std::endl;
template <class itemType>
llSorted<itemType>::llSorted()
{
srand(time(0));
head = NULL;
tail = NULL;
cur = NULL;
index = 0;
MAX_SIZE = 11;
length = rand() % 10 + 1;
cmd = 0;
for (int i = 0; i < length; i++)
{
if (head == NULL)
{
head = new node;
head->data = rand() % 101;
head->next = new node;
head->prev = NULL;
cur = head->next;
cur->prev = head;
}
else
{
cur->data = rand() % 101;
cur->next = new node;
cur->next->prev = cur;
cur = cur->next;
}
}
tail = cur;
tail->next = head;
head->prev = tail;
// sort the list
if (head != NULL)
{
cur = head;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
if (cur->next != tail)
{
if (cur->data > cur->next->data)
{
temp = cur->data;
cur->data = cur->next->data;
cur->next->data = temp;
}
}
cur = cur->next;
}
}
}
}
template <class itemType>
void llSorted<itemType>::init()
{
printList();
cout << "\nAvailable Commands:\n 1. Insert Item\n 2. Retrieve Item\n 3. Delete Item\n 4. List Details\n 9. Select Different Implementation\n 0. Exit\n\nCommand: ";
while(!(cin >> cmd))
{
cout << "Please enter only the number associated with the command\nCommand: ";
cin.clear();
cin.ignore(1000, 10);
}
switch (cmd)
{
case 1:
InsertItem();
break;
case 2:
RetrieveItem();
break;
case 3:
DeleteItem();
break;
case 4:
getLength();
break;
case 9:
init();
break;
case 0:
exit();
break;
default:
validation();
break;
}
}
template <class itemType>
void llSorted<itemType>::printList()
{
cout << "List: ";
// memory issue if list is empty
if (!(isEmpty()))
{
cur = head;
while (cur != tail)
{
cout << cur->data;
if (cur->next != tail)
cout << ", ";
cur = cur->next;
}
}
}
template <class itemType>
bool llSorted<itemType>::isFull()
{
return (length == MAX_SIZE);
}
template <class itemType>
bool llSorted<itemType>::isEmpty()
{
return (length == 0);
}
template <class itemType>
void llSorted<itemType>::InsertItem()
{
// Check to see if the list is full
if(isFull())
{
cout << "List is Full!\n" << endl;
init();
}
// List is not full, ask user for value and insert sorted
else
{
usrVal(0);
// if list is empty, just insert it right after head
if (isEmpty())
{
length++;
cur->data = value;
cur->next = NULL;
tail = cur->next;
cout << endl;
init();
}
else
{
// Traverse the list til next is > the value
cur = head->next;
inserted = false;
while (cur != tail)
{
if (value > cur->data)
{
cur = cur->next;
}
else
{
cur = new node;
cur->data = value;
inserted = true;
length++;
break;
}
}
if (!inserted)
{
cur = new node;
cur->data = value;
cur->next = NULL;
tail = cur->next;
length++;
}
cout << endl;
init();
}
}
}
template <class itemType>
void llSorted<itemType>::RetrieveItem()
{
// Check to see if the list is empty
if(isEmpty())
{
cout << "List is empty!\n" << endl;
init();
}
// List is not empty, ask user for value to find
else
{
usrVal(1);
// Traverse the list until tail is hit
cur = head;
index = 0;
while (cur != tail)
{
if (cur->data == value)
{
found++;
cout << " Found! Properties of '" << cur->data << "':" << endl;
cout << " Address:\t\t\t" << &cur->data << endl;
cout << " Index:\t\t\t" << index << endl;
if (cur->next != tail)
cout << " Next Address & Value:\t\t" << &cur->next << " = " << cur->next->data << endl;
cur = cur->next;
}
else
cur = cur->next;
index++;
}
if(!found)
cout << "Value does not exist!\n";
cout << endl;
init();
}
}
template <class itemType>
void llSorted<itemType>::DeleteItem()
{
// Check if list is empty
if (isEmpty())
{
cout << "List is empty!" << endl;
init();
}
// List is not empty, ask user for value and "delete" item
else
{
usrVal(2);
// traverse the list until you find the value
cur = head;
while(cur->next != tail)
{
// check if cur->next contains the value
if(cur->next->data == value)
{
found++;
length--;
cur->next = cur->next->next;
}
else
cur = cur->next;
}
if(!(found))
cout << "Value does not exist!\n" << endl;
cout << endl;
init();
}
}
template <class itemType>
void llSorted<itemType>::getLength()
{
// offset by -1 due to NULL head
cout << "Maximum number of items list can hold:\t" << MAX_SIZE - 1 << endl;
cout << "Currently stored items:\t\t\t" << length - 1 << endl;
cout << "Last selected index:\t\t\t";
if (index == 0)
cout << "None" << endl;
else
cout << index - 1 << endl;
cout << endl;
init();
}
template <class itemType>
void llSorted<itemType>::usrVal(int val)
{
cout << "What integer would you like to ";
if (val == 0)
cout << "insert? ";
else if (val == 1)
cout << "retrieve? ";
else
cout << "delete? ";
while (!(cin >> value))
{
cout << "Please enter only integer digits: ";
cin.clear();
cin.ignore(1000, 10);
}
// reset found to 0
found = 0;
}
template <class itemType>
void llSorted<itemType>::validation()
{
cout << "Invalid Command. Please try again.\n" << endl;
init();
}
template <class itemType>
int llSorted<itemType>::exit()
{
cout << "Good bye.";
return 0;
}
template class llSorted<int>;
template class llSorted<char>;
template class llSorted<float>;
//template class llSorted<std::string>;
But what potential problem do you see where it "works" for, say, double?
ASKER
Constructor also has to be re-written since comparison of strings and integers are completely different. How would I go about making a special set of instructions only if the type is string?
ASKER
For double and float, if the value is int, then it'll truncate, so that needs to be changed to itemType as well (which I did). Also, at initialization of the list, all items in the list will be integers since rand() is of int type, but what if I typecast? Will it make a difference?
When creating a template, the purpose is to provide a stable product that does not have to be modified for every data type being used. If you didn't write a linked list, but were, instead, a user, then you would not expect the linked list product to initialize data for you (especially not randomly). If you wanted to put random data in the list (say for number types), then you might do that in your test driver, and then insert the nodes from the driver into the list.
Getting a string from a rand() is a matter of mapping random numbers to chars. For example, 0..25 could be 'A'-'Z'; 26 could be 'a', etc.
For things, like rand(), that may make no sense for string (or other data types), then you should think about making a template function to specialize the class template. I'll be back tonight. Others can certainly continue assisting in the meantime.
In the constructor is:
// sort the list
I guess this is what you mean by "since comparison of strings and integers are completely different"
You can specify here what exactly the sort order should be, and we can help make it work. But, again, when I think of a constructor for a linked list, my immediate thought is that the list is empty (unless you define constructors that allow externally created data to be included as arguments).
Take a look at the this list's api and see whether you would like to pattern your design after some of their approaches.
http://www.cplusplus.com/reference/stl/list/
Getting a string from a rand() is a matter of mapping random numbers to chars. For example, 0..25 could be 'A'-'Z'; 26 could be 'a', etc.
For things, like rand(), that may make no sense for string (or other data types), then you should think about making a template function to specialize the class template. I'll be back tonight. Others can certainly continue assisting in the meantime.
In the constructor is:
// sort the list
I guess this is what you mean by "since comparison of strings and integers are completely different"
You can specify here what exactly the sort order should be, and we can help make it work. But, again, when I think of a constructor for a linked list, my immediate thought is that the list is empty (unless you define constructors that allow externally created data to be included as arguments).
Take a look at the this list's api and see whether you would like to pattern your design after some of their approaches.
http://www.cplusplus.com/reference/stl/list/
You have made too many assumptions about the type itemType in your code. It's seemingly hard coded to work with ints, yet you expect it to be able to take any data type you throw at it including strings?
head->data = rand() % 101 ; // assigning an int to type itemType ?
cur->data = rand() % 101; // assigning an int to type itemType ?
cur->data = value; // assigning an int to type itemType ?
For example:
std::string data = 3; // this is not valid c++
head->data = rand() % 101 ; // assigning an int to type itemType ?
cur->data = rand() % 101; // assigning an int to type itemType ?
cur->data = value; // assigning an int to type itemType ?
For example:
std::string data = 3; // this is not valid c++
zenoture : any specific reason why you do not want to use STL? looks to me you are re-inventing the wheel here. If its for academic purposes this should be fine but for production level code it pays to use a library which has been tested over time
ASKER
@trinitrotoluene
Not allowed to use STL. This is an academic exercise to show the usage of templates and understand how they work.
@davesgonebananas
I understand what are are saying, and I made it clear in my previous posts that I know ints and strings will need to handled differently. My question now is if there is a way to use templates with a conditional statement. For example, if the template is of type int, run the regular code the way it is as it will work for ints, chars, floats and doubles. If the the template is of type string, run a special case string function to do the same basic concept.
@phoffric
I was actually thinking the same thing. Maybe it would be best if I moved the list generation and sorting into a separate function which does what it is supposed to do based on the type. Again, since STLs are not allowed, I can take concepts of STL but I can't actually use the STL itself.
So now that the question is clear, how would I go about truly making this sorted circular 2-way linked list work for any datatype provided? If I do special cases for each type, I might as well just write a function for each one separately... So where do I go from here?
Not allowed to use STL. This is an academic exercise to show the usage of templates and understand how they work.
@davesgonebananas
I understand what are are saying, and I made it clear in my previous posts that I know ints and strings will need to handled differently. My question now is if there is a way to use templates with a conditional statement. For example, if the template is of type int, run the regular code the way it is as it will work for ints, chars, floats and doubles. If the the template is of type string, run a special case string function to do the same basic concept.
@phoffric
I was actually thinking the same thing. Maybe it would be best if I moved the list generation and sorting into a separate function which does what it is supposed to do based on the type. Again, since STLs are not allowed, I can take concepts of STL but I can't actually use the STL itself.
So now that the question is clear, how would I go about truly making this sorted circular 2-way linked list work for any datatype provided? If I do special cases for each type, I might as well just write a function for each one separately... So where do I go from here?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
>>Just wondering.. What is the deadline for completion? Do you have to hand in intermediate steps >>(e.g., design, implementation, conversion to template, get string to work)? Depending upon the >>deadline, your time available, and your desire to learn new things, we can advise accordingly, so as >>not to get yourself too deep. Do you need to be able to include an arbitrary data type (e.g., your own >>class definition)?
Was actually due yesterday (10/21) but my professor is lenient and would rather have good, working, "beautiful" code rather than something hacked together. I actually enjoy learning about the intricacies of the code, as I used to be a PHP developer a while ago (not knowing basic programming skills), but now have a much better understanding of everything due to these exercises, so I always try to milk it as much as I can. As for the steps, it needs to be turned in like a complete program, no steps, and only the following datatypes:
int, char, float, double, and string
Anything else is optional. There is no extra credit for going above and beyond the requirements, but the deeper understanding of what's going on is more worth it to me.
Was actually due yesterday (10/21) but my professor is lenient and would rather have good, working, "beautiful" code rather than something hacked together. I actually enjoy learning about the intricacies of the code, as I used to be a PHP developer a while ago (not knowing basic programming skills), but now have a much better understanding of everything due to these exercises, so I always try to milk it as much as I can. As for the steps, it needs to be turned in like a complete program, no steps, and only the following datatypes:
int, char, float, double, and string
Anything else is optional. There is no extra credit for going above and beyond the requirements, but the deeper understanding of what's going on is more worth it to me.
ASKER
Hoping to complete this by Sunday night however, as there are other exercises being assigned, and I don't want to fall too much behind.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> "beautiful" code rather than something hacked together
Then can you get an extra extension. Before "beautiful" code can be created, I think you need a better design (doesn't have to be beautiful, but at least adequate from a user's perspective as well as a designer's). I think two Sundays from now will give you the time. If you ask multiple short questions that are somewhat independent of each other, then you will get more parallel processing from multiple experts to keep you going 24x7. We should just focus on string, and forget the user defined classes until after you meet your deadline.
Could you explain exactly the problem you are facing with the string? What behavior are you getting that you do not like? What behavior do you expect?
If this Sunday is the absolute deadline, let us know what you want to do in light of our comments from me, davesgoneba…, and trinitrotoluene.
Then can you get an extra extension. Before "beautiful" code can be created, I think you need a better design (doesn't have to be beautiful, but at least adequate from a user's perspective as well as a designer's). I think two Sundays from now will give you the time. If you ask multiple short questions that are somewhat independent of each other, then you will get more parallel processing from multiple experts to keep you going 24x7. We should just focus on string, and forget the user defined classes until after you meet your deadline.
Could you explain exactly the problem you are facing with the string? What behavior are you getting that you do not like? What behavior do you expect?
If this Sunday is the absolute deadline, let us know what you want to do in light of our comments from me, davesgoneba…, and trinitrotoluene.
I would take everything a step back and try to clean your list from code that does not belong there (like said a couple of times before).
Once you have done that, those problems with int/double/strings incompatibilities will go away, since the remaining code will be generalized.
So lets look at the member-functions of your list:
isFull -> makes no sense, a list has an open capactiy by definition
Then there are a lot of utility functions, that dont belong to a general list.
The basic operations on a list are those:
void Init();
void Deinit();
bool IsEmpty() const;
void InsertItem(const itemType &item);
void DeleteItem(const itemType &item);
bool FindItem(const itemType &item) const;
void getLength(); -> wrong name, better: GetItemCount()
Start to implement those functions cleanly, make sure they work as expected and remove all the rest.
Use always the same style for your function names, either capital letters on the beginning or not.
Your professor will be more happy with less stuff that is working and clean than lots of cluttered code of funny things that dont work and dont belong into the list.
Focus on the basics first, make them work, if time is left then move to the higher level.
ike
Once you have done that, those problems with int/double/strings incompatibilities will go away, since the remaining code will be generalized.
So lets look at the member-functions of your list:
isFull -> makes no sense, a list has an open capactiy by definition
Then there are a lot of utility functions, that dont belong to a general list.
The basic operations on a list are those:
void Init();
void Deinit();
bool IsEmpty() const;
void InsertItem(const itemType &item);
void DeleteItem(const itemType &item);
bool FindItem(const itemType &item) const;
void getLength(); -> wrong name, better: GetItemCount()
Start to implement those functions cleanly, make sure they work as expected and remove all the rest.
Use always the same style for your function names, either capital letters on the beginning or not.
Your professor will be more happy with less stuff that is working and clean than lots of cluttered code of funny things that dont work and dont belong into the list.
Focus on the basics first, make them work, if time is left then move to the higher level.
ike
I agree that taking a step back is valuable. I'd recommend trying to use method names in the STL list link provided earlier. In that way you are getting used to nomenclature that you will need to know later.
ASKER
Ok, the code was modified using typeid to execute different code based on the type. It works for chars, floats, ints, and doubles, but once the last line (template class llSorted<std::string>;) is uncommented, the errors start to roll in. At this point all I want is to be able to use the code I have with as minimal change as possible to work with strings. With the typeid's in place, it shouldn't really care if bool operations are happening since that code will not be executed as a string.
I don't mind doing template specialization for stings, but doesn't defeat the purpose of a function that can handle any datatype? Why would someone template a function if it just has to be re-written all over again for a different datatype?
Errors:
1>------ Build started: Project: Templetized sorted 2-way circular linked list, Configuration: Debug Win32 ------
1> stdafx.cpp
1> llSorted.cpp
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(40): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genLis t(void)'
1> with
1> [
1> itemType=float
1> ]
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(368) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1> with
1> [
1> itemType=float
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(46): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(11): error C2593: 'operator =' is ambiguous
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(77 2): could be 'std::basic_string<_Elem,_ Traits,_Ax > &std::basic_string<_Elem,_ Traits,_Ax >::operato r =(_Elem)'
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c har>,
1> _Ax=std::allocator<char>
1> ]
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(76 7): or 'std::basic_string<_Elem,_ Traits,_Ax > &std::basic_string<_Elem,_ Traits,_Ax >::operato r =(const _Elem *)'
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c har>,
1> _Ax=std::allocator<char>
1> ]
1> while trying to match the argument list '(std::string, int)'
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(5) : while compiling class template member function 'llSorted<itemType>::llSor ted(void)'
1> with
1> [
1> itemType=std::string
1> ]
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(370) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1> with
1> [
1> itemType=std::string
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(26): error C2593: 'operator =' is ambiguous
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(77 2): could be 'std::basic_string<_Elem,_ Traits,_Ax > &std::basic_string<_Elem,_ Traits,_Ax >::operato r =(_Elem)'
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c har>,
1> _Ax=std::allocator<char>
1> ]
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(76 7): or 'std::basic_string<_Elem,_ Traits,_Ax > &std::basic_string<_Elem,_ Traits,_Ax >::operato r =(const _Elem *)'
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c har>,
1> _Ax=std::allocator<char>
1> ]
1> while trying to match the argument list '(std::string, int)'
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genLis t(void)'
1> with
1> [
1> itemType=std::string
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_T raits,_All oc> &,const _Elem *)' : could not deduce template argument for 'const _Elem *' from 'int'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(243 ) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_T raits,_All oc> &)' : could not deduce template argument for 'const _Elem *' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(233 ) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_T raits,_All oc> &,const std::basic_string<_Elem,_T raits,_All oc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_T raits,_All oc> &' from 'int'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(223 ) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran It> &,const std::reverse_iterator<_Ran It2> &)' : could not deduce template argument for 'const std::reverse_iterator<_Ran It> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran It> &,const std::reverse_iterator<_Ran It2> &)' : could not deduce template argument for 'const std::reverse_iterator<_Ran It> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran It> &,const std::reverse_iterator<_Ran It2> &)' : could not deduce template argument for 'const std::reverse_iterator<_Ran It> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 356) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas e> &,const std::_Revranit<_RanIt2,_Ba se2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Bas e> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas e> &,const std::_Revranit<_RanIt2,_Ba se2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Bas e> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas e> &,const std::_Revranit<_RanIt2,_Ba se2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Bas e> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1 179) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31 8) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31 8) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31 8) : see declaration of 'std::operator <'
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2676: binary '<' : 'std::string' does not define this operator or a conversion to a type acceptable to the predefined operator
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): fatal error C1903: unable to recover from previous error(s); stopping compilation
1> Generating Code...
1> Skipping... (no relevant changes detected)
1> Lab7.cpp
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
I don't mind doing template specialization for stings, but doesn't defeat the purpose of a function that can handle any datatype? Why would someone template a function if it just has to be re-written all over again for a different datatype?
Errors:
1>------ Build started: Project: Templetized sorted 2-way circular linked list, Configuration: Debug Win32 ------
1> stdafx.cpp
1> llSorted.cpp
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(40): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genLis
1> with
1> [
1> itemType=float
1> ]
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(368) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1> with
1> [
1> itemType=float
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(46): warning C4244: '=' : conversion from 'int' to 'float', possible loss of data
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(11): error C2593: 'operator =' is ambiguous
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(77
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c
1> _Ax=std::allocator<char>
1> ]
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(76
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c
1> _Ax=std::allocator<char>
1> ]
1> while trying to match the argument list '(std::string, int)'
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(5) : while compiling class template member function 'llSorted<itemType>::llSor
1> with
1> [
1> itemType=std::string
1> ]
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(370) : see reference to class template instantiation 'llSorted<itemType>' being compiled
1> with
1> [
1> itemType=std::string
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(26): error C2593: 'operator =' is ambiguous
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(77
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c
1> _Ax=std::allocator<char>
1> ]
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xstring(76
1> with
1> [
1> _Elem=char,
1> _Traits=std::char_traits<c
1> _Ax=std::allocator<char>
1> ]
1> while trying to match the argument list '(std::string, int)'
1> f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(20) : while compiling class template member function 'void llSorted<itemType>::genLis
1> with
1> [
1> itemType=std::string
1> ]
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_T
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(243
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_T
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(233
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::basic_string<_Elem,_T
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\string(223
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::reverse_iterator<_Ran
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Bas
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(1
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'std::string'
1> c:\program files (x86)\microsoft visual studio 10.0\vc\include\utility(31
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): error C2676: binary '<' : 'std::string' does not define this operator or a conversion to a type acceptable to the predefined operator
1>f:\comsc-210 labs\7\templetized sorted 2-way circular linked list\llsorted.cpp(39): fatal error C1903: unable to recover from previous error(s); stopping compilation
1> Generating Code...
1> Skipping... (no relevant changes detected)
1> Lab7.cpp
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
#include "stdafx.h"
template <class itemType>
llSorted<itemType>::llSorted()
{
srand((unsigned int)time(0));
head = NULL;
tail = NULL;
cur = NULL;
temp = NULL;
MAX_SIZE = 10 + 1;
length = rand() % 10 + 1;
cmd = 0;
genList();
}
template <class itemType>
void llSorted<itemType>::genList()
{
for (int i = 0; i < length; i++)
{
if (head == NULL)
{
head = new node;
head->data = NULL;
head->next = new node;
head->prev = NULL;
cur = head->next;
cur->prev = head;
}
else
{
if (typeid(itemType) != typeid(std::string))
{
// if itemType is char, generate new number between A - z
if (typeid(itemType) == typeid(char))
{
while (temp < 65)
temp = rand() % 123;
cur->data = temp;
temp = 0;
}
// if itemType is anything but char, just generate a random int
else
cur->data = rand() % 101;
// if this is the last item on the list, set it to head
if (i == (length-1))
{
cur->next = head;
head->prev = cur;
}
else
{
cur->next = new node;
cur->next->prev = cur;
cur = cur->next;
}
}
else
{
// if IS string
}
}
}
sortList();
}
template <class itemType>
void llSorted<itemType>::sortList()
{
if (!isEmpty())
{
if (typeid(itemType) != typeid(std::string))
{
cur = head->next;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
if (cur->prev->data > cur->data)
{
temp = cur->data;
cur->data = cur->prev->data;
cur->prev->data = temp;
cur->prev->next = cur;
}
if (cur->next != head)
{
cur = cur->next;
}
else
break;
}
cur = head->next;
}
}
else
{
// if IS string
}
}
}
template <class itemType>
void llSorted<itemType>::init()
{
printList();
cout << "\nAvailable Commands:\n 1. Insert Item\n 2. Retrieve Item\n 3. Delete Item\n 4. List Details\n 9. Select Different Implementation\n 0. Exit\n\nCommand: ";
while(!(cin >> cmd))
{
cout << "Please enter only the number associated with the command\nCommand: ";
cin.clear();
cin.ignore(1000, 10);
}
switch (cmd)
{
case 1:
InsertItem();
break;
case 2:
RetrieveItem();
break;
case 3:
DeleteItem();
break;
case 4:
getLength();
break;
case 9:
init();
break;
case 0:
exit();
break;
default:
validation();
break;
}
}
template <class itemType>
void llSorted<itemType>::printList()
{
cout << "List: ";
// memory issue if list is empty
if (!(isEmpty()))
{
cur = head->next;
while (cur != head)
{
cout << cur->data;
if (cur->next != head)
cout << ", ";
cur = cur->next;
}
}
}
template <class itemType>
bool llSorted<itemType>::isFull()
{
return (length == MAX_SIZE);
}
template <class itemType>
bool llSorted<itemType>::isEmpty()
{
return (length == 1);
}
template <class itemType>
void llSorted<itemType>::InsertItem()
{
// Check to see if the list is full
if(isFull())
{
cout << "List is Full!\n" << endl;
init();
}
// List is not full, ask user for value and insert sorted
else
{
usrVal(0);
// if list is empty, just insert it right after head
if (isEmpty())
{
length++;
head->next = new node;
cur = head->next;
cur->data = value;
cur->prev = head;
cur->next = head;
head->prev = cur;
cout << endl;
init();
}
else
{
if (typeid(itemType) != typeid(std::string))
{
// Traverse the list til next is > the value
cur = head->next;
inserted = false;
while (cur != head)
{
if (value > cur->data)
{
cur = cur->next;
}
else
{
tempNode = new node;
tempNode->data = value;
tempNode->next = cur;
tempNode->prev = cur->prev;
cur->prev->next = tempNode;
cur->prev = tempNode;
inserted = true;
length++;
break;
}
}
if (!inserted)
{
tempNode = new node;
tempNode->data = value;
tempNode->next = head;
tempNode->prev = head->prev;
head->prev->next = tempNode;
head->prev = tempNode;
length++;
}
cout << endl;
init();
}
else
{
// if IS string
}
}
}
}
template <class itemType>
void llSorted<itemType>::RetrieveItem()
{
// Check to see if the list is empty
if(isEmpty())
{
cout << "List is empty!\n" << endl;
init();
}
// List is not empty, ask user for value to find
else
{
usrVal(1);
// Traverse the list until tail is hit
cur = head->next;
while (cur != head)
{
if (cur->data == value)
{
found++;
cout << " Found! Properties of '" << cur->data << "':" << endl;
cout << " Address:\t\t\t" << &cur->data << endl;
cout << " Prev Address & Value:\t\t" << &cur->prev << " = " << cur->prev->data << endl;
cout << " Next Address & Value:\t\t" << &cur->next << " = " << cur->next->data << endl;
cur = cur->next;
}
else
cur = cur->next;
}
if(!found)
cout << "Value does not exist!\n";
cout << endl;
init();
}
}
template <class itemType>
void llSorted<itemType>::DeleteItem()
{
// Check if list is empty
if (isEmpty())
{
cout << "List is empty!" << endl;
init();
}
// List is not empty, ask user for value and delete item
else
{
usrVal(2);
// traverse the list until you find the value
cur = head->next;
while(cur != head)
{
// check if cur->next contains the value
if(cur->data == value)
{
found++;
length--;
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
tempNode = cur;
cur = cur->next;
delete tempNode;
break;
}
else
cur = cur->next;
}
if(!(found))
cout << "Value does not exist!\n" << endl;
cout << endl;
init();
}
}
template <class itemType>
void llSorted<itemType>::getLength()
{
// offset by -1 due to NULL head
cout << "Maximum number of items list can hold:\t" << MAX_SIZE - 1 << endl;
cout << "Currently stored items:\t\t\t" << length - 1 << endl;
cout << endl;
init();
}
template <class itemType>
void llSorted<itemType>::usrVal(int val)
{
cout << "What " << typeid(itemType).name() << " would you like to ";
if (val == 0)
cout << "insert? ";
else if (val == 1)
cout << "retrieve? ";
else
cout << "delete? ";
while (!(cin >> value))
{
cout << "Please enter only integer digits: ";
cin.clear();
cin.ignore(1000, 10);
}
// reset found to 0
found = 0;
}
template <class itemType>
void llSorted<itemType>::validation()
{
cout << "Invalid Command. Please try again.\n" << endl;
init();
}
template <class itemType>
int llSorted<itemType>::exit()
{
cout << "Good bye.";
return 0;
}
template class llSorted<int>;
template class llSorted<char>;
template class llSorted<float>;
template class llSorted<double>;
template class llSorted<std::string>;
Looks like your header has changed. What is it?
Try to avoid RTTI if other approaches are available.
Using typeid within the template bodies as a switch statement on the type (using if-else if-else) is difficult.
It would be nice if you responded to the various comments made for general improvement. If you wish to ignore a suggestion, at least explain why so we'll be on the same page. (Or, we may even be able to turn your explanation into a better design.)
======
Lines 37-39:
if (typeid(itemType) == typeid(char))
{
while (temp < 65)
Line 370:
template class llSorted<std::string>;
======
temp is of type itemType which in line 370, you are asking for a string.
So line 39 is asking: if the string value in temp is less than 65, then...
Is that what you intended?
In http:#33955382 I provided a link showing funky non-C++ code using a switch statement to handle different types in a template. To repeat:
http://www.parashift.com/c++-faq-lite/templates.html#faq-35.7
*** Read up to section 35.9 ***
You also ask:
>> (1) how would I go about truly making this sorted circular 2-way linked list work
>> (2) for any data type provided?
IMO, this project question should be broken up into smaller chunks with each issue delved with separately. It will be easier to follow the threads if you do this. For starters, I suggest that you try to implement the ideas presented in templates.html#faq-35.7 through 35.9 as your own mini project. If you run into problems, post what you have in a new question.
If you still need help with sorted circular 2-way linked lists, I suggest you post a non-template solution in a new question, and indicate the problems you are having.
I noticed that init() calls init(). Why do you want to do that? And if cmd results in another function called, then that function calls init(), which in turn calls init. I suspect that there is a cleaner design.
Try to avoid RTTI if other approaches are available.
Using typeid within the template bodies as a switch statement on the type (using if-else if-else) is difficult.
It would be nice if you responded to the various comments made for general improvement. If you wish to ignore a suggestion, at least explain why so we'll be on the same page. (Or, we may even be able to turn your explanation into a better design.)
======
Lines 37-39:
if (typeid(itemType) == typeid(char))
{
while (temp < 65)
Line 370:
template class llSorted<std::string>;
======
temp is of type itemType which in line 370, you are asking for a string.
So line 39 is asking: if the string value in temp is less than 65, then...
Is that what you intended?
In http:#33955382 I provided a link showing funky non-C++ code using a switch statement to handle different types in a template. To repeat:
http://www.parashift.com/c++-faq-lite/templates.html#faq-35.7
*** Read up to section 35.9 ***
You also ask:
>> (1) how would I go about truly making this sorted circular 2-way linked list work
>> (2) for any data type provided?
IMO, this project question should be broken up into smaller chunks with each issue delved with separately. It will be easier to follow the threads if you do this. For starters, I suggest that you try to implement the ideas presented in templates.html#faq-35.7 through 35.9 as your own mini project. If you run into problems, post what you have in a new question.
If you still need help with sorted circular 2-way linked lists, I suggest you post a non-template solution in a new question, and indicate the problems you are having.
I noticed that init() calls init(). Why do you want to do that? And if cmd results in another function called, then that function calls init(), which in turn calls init. I suspect that there is a cleaner design.
cur->data = value;
Looks like a type mismatch.