Trouble with Linking to Object File Undefined Reference.

Im having issues on my program assignment. I keep getting errors like


undefined reference to `void get_list<int, std::less<int> >(std::vector<int, std::allocator<int> >&, char const*, std::less<int>)'


I have a header file, and a CC file. It compiles fine but it will not link for some reason. Here is my code

Code:

---


#include "340.h"

#ifndef H_PROG7
#define H_PROG7

// data files

#define D1 "prog7.d1"
#define D2 "prog7.d2"
#define D3 "prog7.d3"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12  // width of string

#define INT_LN 15  // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class P> void insert(vector<T>&, const T&, P);
template<class T,class P> T remove(vector<T>&, P);

template<class T,class P> void upheap(vector<T>&, int, P);
template<class T,class P> void downheap(vector<T>&, int, P);

template<class T,class P>
void get_list(vector<T>&, const char*, P);

template<class T,class P>
void print_list(vector<T>&, const int, const int, P);

template<class T, class P>
void get_list(vector<T>& v, const char* file, P func) {
ifstream inFile("file");
T data;

while(inFile >> data) {
  inFile >> data;
  insert(v, data, func);
}
}

template<class T, class P>
void insert(vector<T>& v, const T& data, P func) {
v.push_back( data );
upheap( v, v.size()-1, func );
}

template<class T,class P>
void upheap(vector<T>& v, int start, P func) {

while( start <= v.size()/2 )  {

  unsigned int parent = start / 2;

  if( parent - 1  <= v.size() && v[parent - 1] > v[parent] )
    parent = parent - 1;

  if( v[start] <= v[parent] )
    break;

  swap( v[start], v[parent] );
  start = parent;
}
}

template<class T,class P>
void downheap(vector<T>& v, int start, P func) {

while(start <= v.size()/2 )  {

  unsigned int child = 2 * start;

  if( child + 1 <= v.size() && v[child + 1] > v[child])
    child = child + 1;

  if( v[start] >= v[child] )
    break;

  swap( v[start], v[child] );
  start = child;
}
}

template<class T,class P>
T remove(vector<T>& v, P func) {
swap( v[0], v.back() );
T& item = v.back();

v.pop_back();
downheap( v, 1, func );

return item;
}

template<class T,class P>
void print_list(vector<T>& v, const int size, const int line, P func) {

for(int i = 1; i < v.size(); i++) {
  cout << remove(v, func) << " ";
}
}

#endif

---

That is my header file.
Here is my CC File.

Code:

---



#include "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h"

int main()
{
    vector<int>    v1(1);  // heap of integers
    vector<float>  v2(1);  // heap of floating-pt nums
    vector<string> v3(1);  // heap of strings

    // print header message
    cout << "\t\t\t*** CSCI 340: Program 8 - Output ***\n\n";

    // sort and print first list

    cout << "first list - ascending order:\n\n";
    get_list(v1, D1, less<int>());
    print_list(v1, INT_SZ, INT_LN, less<int>());

    cout << "first list - descending order:\n\n";
    get_list(v1, D1, greater<int>());
    print_list(v1, INT_SZ, INT_LN, greater<int>());

    // sort and print second list

    cout << "second list - ascending order:\n\n";
    get_list(v2, D2, less<float>());
    print_list(v2, FLT_SZ, FLT_LN, less<float>());

    cout << "second list - descending order:\n\n";
    get_list(v2, D2, greater<float>());
    print_list(v2, FLT_SZ, FLT_LN, greater<float>());

    // sort and print third list

    cout << "third list - ascending order:\n\n";
    get_list(v3, D3, less<string>());
    print_list(v3, STR_SZ, STR_LN, less<string>());

    cout << "third list - descending order:\n\n";
    get_list(v3, D3, greater<string>());
    print_list(v3, STR_SZ, STR_LN, greater<string>());

    // print termination message
    cout << "\t\t\t*** end of program execution ***\n\n";
    return 0;
}

---

I cant figure it out. If anyone could help me out. I have been looking at this program for hours and hours.

Quote:

---

Originally Posted by youngyou4

I have a header file, and a CC file. It compiles fine but it will not link for some reason.

---

The obvious reason is that the linker cannot find that function.

The code you posted does not show exactly how that CPP and header file are related. All I see in the cpp file is this:

Code:

---

#include "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h"

---

I don't know what that header file is, as you never indicated what that header file is supposed to be.

Regards,

Paul McKneni

Ok I have moved all the functions into prog8.cc

Code:

---



#include "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h"

int main()
{
    vector<int>    v1(1);  // heap of integers
    vector<float>  v2(1);  // heap of floating-pt nums
    vector<string> v3(1);  // heap of strings

    // print header message
    cout << "\t\t\t*** CSCI 340: Program 8 - Output ***\n\n";

    // sort and print first list

    cout << "first list - ascending order:\n\n";
    get_list(v1, D1, less<int>());
    print_list(v1, INT_SZ, INT_LN, less<int>());

    cout << "first list - descending order:\n\n";
    get_list(v1, D1, greater<int>());
    print_list(v1, INT_SZ, INT_LN, greater<int>());

    // sort and print second list

    cout << "second list - ascending order:\n\n";
    get_list(v2, D2, less<float>());
    print_list(v2, FLT_SZ, FLT_LN, less<float>());

    cout << "second list - descending order:\n\n";
    get_list(v2, D2, greater<float>());
    print_list(v2, FLT_SZ, FLT_LN, greater<float>());

    // sort and print third list

    cout << "third list - ascending order:\n\n";
    get_list(v3, D3, less<string>());
    print_list(v3, STR_SZ, STR_LN, less<string>());

    cout << "third list - descending order:\n\n";
    get_list(v3, D3, greater<string>());
    print_list(v3, STR_SZ, STR_LN, greater<string>());

    // print termination message
    cout << "\t\t\t*** end of program execution ***\n\n";
    return 0;
}


template<class T, class P>
void get_list(vector<T>& v, const char* file, P func) {
ifstream inFile("file");
T data;

while(inFile >> data) {
  inFile >> data;
  insert(v, data, func);
}
}

template<class T, class P>
void insert(vector<T>& v, const T& data, P func) {
v.push_back( data );
upheap( v, v.size()-1, func );
}

template<class T,class P>
void upheap(vector<T>& v, int start, P func) {

while( start <= v.size()/2 )  {

  unsigned int parent = start / 2;

  if( parent - 1  <= v.size() && v[parent - 1] > v[parent] )
    parent = parent - 1;

  if( v[start] <= v[parent] )
    break;

  swap( v[start], v[parent] );
  start = parent;
}
}



template<class T,class P>
void downheap(vector<T>& v, int start, P func) {

while(start <= v.size()/2 )  {

  unsigned int child = 2 * start;

  if( child + 1 <= v.size() && v[child + 1] > v[child])
    child = child + 1;

  if( v[start] >= v[child] )
    break;

  swap( v[start], v[child] );
  start = child;
}
}

template<class T,class P>
T remove(vector<T>& v, P func) {
swap( v[0], v.back() );
T& item = v.back();

v.pop_back();
downheap( v, 1, func );

return item;
}


template<class T,class P>
T remove(vector<T>& v, P func) {
swap( v[0], v.back() );
T& item = v.back();

v.pop_back();
downheap( v, 1, func );

return item;
}

template<class T,class P>
void print_list(vector<T>& v, const int size, const int line, P func) {

for(int i = 1; i < v.size(); i++) {
  cout << remove(v, func) << " ";
}
}

---

That is what my prog8.cc Looks like.
Now the header file that it is linking to looks like this

Code:

---




#include "/home/turing/onyuksel/courses/340/common/340.h"

#ifndef H_PROG8
#define H_PROG8

// data files

#define D1 "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.d1"
#define D2 "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.d2"
#define D3 "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.d3"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12  // width of string

#define INT_LN 15  // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class P> void insert(vector<T>&, const T&, P);
template<class T,class P> T remove(vector<T>&, P);

template<class T,class P> void upheap(vector<T>&, int, P);
template<class T,class P> void downheap(vector<T>&, int, P);

template<class T,class P>
void get_list(vector<T>&, const char*, P);

template<class T,class P>
void print_list(vector<T>&, const int, const int, P);

---

Now when i compile i get errors saying:

Code:

---



prog8.cc:36:  instantiated from here
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’

---

Any idea what the issue is?

Code:

---


z1578264@turing:~/340$ compile.340 prog8
prog8.cc: In function ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P)’:
prog8.cc:60: error: ‘ve’ was not declared in this scope
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::less<int>]’:
prog8.cc:15:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::less<int>]’:
prog8.cc:16:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::less<int>]’:
prog8.cc:16:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::greater<int>]’:
prog8.cc:19:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::greater<int>]’:
prog8.cc:20:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::greater<int>]’:
prog8.cc:20:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::less<float>]’:
prog8.cc:25:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::less<float>]’:
prog8.cc:26:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::less<float>]’:
prog8.cc:26:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::greater<float>]’:
prog8.cc:29:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::greater<float>]’:
prog8.cc:30:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::greater<float>]’:
prog8.cc:30:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:35:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:36:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:36:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:39:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:29: warning: unused parameter ‘file’
prog8.cc: In function ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:40:  instantiated from here
prog8.cc:114: warning: comparison between signed and unsigned integer expressions
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h: At global scope:
prog8.cc: In instantiation of ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:40:  instantiated from here
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘size’
/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h:32: warning: unused parameter ‘line’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = int, P = std::less<int>]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::less<int>]’
prog8.cc:15:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = int, P = std::greater<int>]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::greater<int>]’
prog8.cc:19:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = float, P = std::less<float>]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::less<float>]’
prog8.cc:25:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = float, P = std::greater<float>]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::greater<float>]’
prog8.cc:29:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:35:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In instantiation of ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:39:  instantiated from here
prog8.cc:59: warning: unused parameter ‘data’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = int, P = std::less<int>]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = int, P = std::less<int>]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::less<int>]’
prog8.cc:15:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = int, P = std::less<int>]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = int, P = std::less<int>]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::less<int>]’
prog8.cc:16:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = int, P = std::greater<int>]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = int, P = std::greater<int>]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = int, P = std::greater<int>]’
prog8.cc:19:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = int, P = std::greater<int>]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = int, P = std::greater<int>]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = int, P = std::greater<int>]’
prog8.cc:20:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = float, P = std::less<float>]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = float, P = std::less<float>]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::less<float>]’
prog8.cc:25:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = float, P = std::less<float>]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = float, P = std::less<float>]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::less<float>]’
prog8.cc:26:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = float, P = std::greater<float>]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = float, P = std::greater<float>]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = float, P = std::greater<float>]’
prog8.cc:29:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = float, P = std::greater<float>]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = float, P = std::greater<float>]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = float, P = std::greater<float>]’
prog8.cc:30:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:35:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc: In instantiation of ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:35:  instantiated from here
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:36:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc: In instantiation of ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P =

---

Code:

---


std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:36:  instantiated from here
prog8.cc:83: warning: unused parameter ‘func’
prog8.cc: In function ‘void upheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:61:  instantiated from ‘void insert(std::vector<_Tp, std::allocator<_CharT> >&, const T&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:54:  instantiated from ‘void get_list(std::vector<_Tp, std::allocator<_CharT> >&, const char*, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:39:  instantiated from here
prog8.cc:67: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:65: warning: unused parameter ‘func’
prog8.cc: In function ‘void downheap(std::vector<_Tp, std::allocator<_CharT> >&, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’:
prog8.cc:106:  instantiated from ‘T remove(std::vector<_Tp, std::allocator<_CharT> >&, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:115:  instantiated from ‘void print_list(std::vector<_Tp, std::allocator<_CharT> >&, int, int, P) [with T = std::basic_string<char, std::char_traits<char>, std::allocator<char> >, P = std::greater<std::basic_string<char, std::char_traits<char>, std::allocator<char> > >]’
prog8.cc:40:  instantiated from here
prog8.cc:85: warning: comparison between signed and unsigned integer expressions
prog8.cc: At global scope:
prog8.cc:83: warning: unused parameter ‘func’

---

Quote:

---

Originally Posted by youngyou4

Ok I have moved all the functions into prog8.cc

---

What is "prog.h"? You never stated what this is:

Code:

---

#include "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.h"

---

Secondly, please don't throw stuff together and not know what you're really doing. When developing an application, you're supposed to be compiling and linking incremental changes, and not write the entire code in one shot and then compile and link so much code without knowing if the simplest examples do not compile correctly.

Code:

---

#include <vector>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    vector<int>    v1(1);  // heap of integers
    vector<float>  v2(1);  // heap of floating-pt nums
    vector<string> v3(1);  // heap of strings

    // print header message
    cout << "\t\t\t*** CSCI 340: Program 8 - Output ***\n\n";

    // sort and print first list
    cout << "first list - ascending order:\n\n";
//    get_list(v1, D1, less<int>());
}

---

Let's stick with this. Does this compile and link? It should, as all that there is is vector, string and iostream templates, and they are standard.

After you get this to compile and link, uncomment the get_list function. Now, what are the errors? What is required to have get_list function recognized?

Code:

---

#include <vector>
#include <iostream>
#include <string>
#include <fstream>

template<class T, class P>
void get_list(std::vector<T>& v, const char* file, P func)
{
    std::ifstream inFile("file");
    T data;

    while(inFile >> data)
  {
        inFile >> data;
//        insert(v, data, func);
    }
}

using namespace std;

#define D1 "/home/turing/onyuksel/courses/340/progs/11s/p8/prog8.d1"

int main()
{
    vector<int>    v1(1);  // heap of integers
    vector<float>  v2(1);  // heap of floating-pt nums
    vector<string> v3(1);  // heap of strings

    // print header message
    cout << "\t\t\t*** CSCI 340: Program 8 - Output ***\n\n";

    // sort and print first list
    cout << "first list - ascending order:\n\n";
    get_list(v1, D1, less<int>());
}

---

This should also compile and link. Note that the "insert" function is commented out. Then you slowly add in the functions, looking to compile and link successfully for each iteration you're adding code.

Regards,

Paul McKenzie

Ok now I have everything working except my upheap and downheap functions.
They are not sorting like they should.

Quote:

---

Originally Posted by youngyou4

Ok now I have everything working except my upheap and downheap functions.
They are not sorting like they should.

---

Did you use your compiler's debugger to solve the problem?

Regards,

Paul McKenzie

Code:

---

if( parent - 1  <= v.size() && v[parent - 1] > v[parent] )

if( child + 1 <= v.size() && v[child + 1] > v[child])

---

In these lines you can dereference an end() position. If parent-1 == v.size() then v[parent] is not in the vector. Similarly if child+1==v.size() then v[child+1] is also not in the vector.

Yes Paul thank you. It worked out great.

Russco is that all there is to it for why my sort is not working. It also says im not using all parameters but I don't see how i can use them.

I didn't look that closely but I did notice that you could possibly exceed the bounds of your vector. I haven't written a heapsort in years. C++ provides std::make_heap and std::sort_heap for such purposes.

Okay I tried your way but It only sorts some of the numbers.

This is my upheap

Code:

---


template<class T,class P>
void upheap(vector<T>& v, int start, P func) {
  T x = v[start];
  while (start > 1 && func(x, v[start/2])) {
      v[start] = v[start/2]; start /= 2;
  }
  v[start] = x;
}

---

This is my downheap

Code:

---


template<class T,class P>
void downheap(vector<T>& v, int start, P func) {

while(start <= (int)v.size()/2 )  {

  unsigned int child = 2 * start;

 // if( child + 1 <= v.size() && v[child + 1] > v[child])
  //  child = child + 1;

    if (child +1== v.size())
      child = v[child +1];


  swap( v[start], v[child] );
  start = child;
}
}

---

It's sorting only randomly but the first number sorted is correct. What am I doing wrong?

Here is my output:

Code:

---




first list - ascending order:

-942 -925 -880 -746 -761 -647 -749 -525 -677 -539 -695 -220 -369 -197 -263 -288 -495 -145 -235 -197 -509 -655 -532 -181 516 834 514 179 912 571 830 739 71 349 -187 293 69 164 393 654 -72 560 -390 -546 -202 916 465 934 -136 618
first list - descending order:

934 912 916 834 830 -136 -880 349 739 -145 393 -942 -369 -197 -749 -746 -72 516 654 -539 -235 -197 -532 -647 516 834 514 179 912 571 -263 739 -525 349 -925 -145 -677 -235 514 -197 -72 560 -761 -655 -509 916 465 934 -220 618 -647 69 -655 -546 -749 -220 -263 71 293 560 -695 -369 830 -197 571 71 -288 164 -288 -187 -495 -746 293 -181 69 -942 164 179 393 -880 654 -761 -495 -525 -187 -390 -509 -677 -546 -202 -695 -539 -390 -925 -202 465 -532 -136 -181 618
second list - ascending order:

-834.74 -778.98 -728.5 -497.48 -688.54 -583.92 -630.81 -176.99 -391.86 -237.1 -330.79 -157.06 -208.58 0.63 -430.49 -1.87 76.02 59.06 -391.15 -32.23 -152.79 -180.62 6.82 201.17 337.6 387.5 167.67 200.05 199.22 -327.15 -329.04 163.42 118.35 132.27 87.63 197.7 721.75 -251.65 873.65 378.53 878.72 189.87 -10.69 580.12 113.42 580.2 88.52 355.67 299.95 425.67
second list - descending order:

878.72 873.65 387.5 132.27 721.75 -728.5 378.53 -497.48 -208.58 197.7 580.2 -157.06 -583.92 0.63 299.95 -176.99 76.02 -391.86 -778.98 -32.23 -688.54 580.12 6.82 201.17 337.6 387.5 -208.58 200.05 199.22 -630.81 189.87 163.42 -1.87 132.27 87.63 59.06 721.75 -391.15 873.65 378.53 878.72 189.87 -237.1 -180.62 -330.79 580.2 88.52 355.67 299.95 425.67 -329.04 163.42 355.67 59.06 167.67 -834.74 -630.81 -251.65 -1.87 -327.15 -430.49 -329.04 -834.74 0.63 -728.5 -497.48 118.35 -688.54 -391.15 -152.79 -330.79 113.42 197.7 167.67 337.6 -251.65 -583.92 200.05 199.22 -327.15 -430.49 -176.99 118.35 87.63 76.02 -10.69 -152.79 -391.86 580.12 -32.23 113.42 -10.69 -237.1 -180.62 -778.98 88.52 6.82 201.17 -157.06 425.67
third list - ascending order:

C For However If It The This a become a another about knowledge are made computer book help design is about is called in and thoroughly with word language you or wise the of devoted to just fabrication in your one to the speed language for get you on to
third list - descending order:

your you to word wise The speed or with It to about knowledge This C If is the to a about another one in and thoroughly with word are However or a the of For to become thoroughly language your is to the speed is called language you on to This a about computer called If are a language you made on knowledge wise computer the of fabrication design devoted book for However just help fabrication design C in you made one For book devoted just help become in It language for about get is another get in The and
                        *** end of program execution ***

---

The correct output is this:

Code:

---



 *** CSCI 340: Program 8 - Output ***

first list - ascending order:

-942 -925 -912 -912 -880 -831 -804 -761 -749 -746 -695 -677 -655 -647 -598
-573 -546 -539 -532 -525 -513 -509 -495 -444 -403 -390 -382 -369 -361 -361
-313 -305 -288 -282 -263 -235 -220 -220 -202 -197 -197 -187 -181 -167 -145
-136 -115  -72  -45  -9  -7  28  40  45  69  71  139  144  164  179
 213  251  293  302  348  349  352  393  404  465  475  514  516  517  531
 534  547  557  560  560  571  618  646  654  677  733  739  746  774  830
 834  863  875  895  912  913  916  934  958  966

first list - descending order:

 966  958  934  916  913  912  895  875  863  834  830  774  746  739  733
 677  654  646  618  571  560  560  557  547  534  531  517  516  514  475
 465  404  393  352  349  348  302  293  251  213  179  164  144  139  71
  69  45  40  28  -7  -9  -45  -72 -115 -136 -145 -167 -181 -187 -197
-197 -202 -220 -220 -235 -263 -282 -288 -305 -313 -361 -361 -369 -382 -390
-403 -444 -495 -509 -513 -525 -532 -539 -546 -573 -598 -647 -655 -677 -695
-746 -749 -761 -804 -831 -880 -912 -912 -925 -942

second list - ascending order:

-834.74 -778.98 -728.50 -688.54 -680.65 -648.02 -630.81 -587.31 -583.92
-567.73 -497.48 -492.66 -473.20 -441.58 -430.49 -397.21 -393.01 -391.86
-391.15 -361.08 -330.79 -329.04 -327.15 -323.52 -290.67 -286.83 -286.04
-280.54 -279.66 -267.60 -254.70 -251.65 -239.58 -237.10 -209.56 -208.58
-207.22 -191.03 -180.62 -176.99 -170.40 -157.06 -152.79 -126.17  -40.34
 -32.23  -18.69  -10.69  -1.87    0.63    2.91    6.82  29.85  42.38
  59.06  64.03  76.02  87.63  88.52  104.55  105.74  113.42  118.35
 132.27  136.53  163.42  167.67  168.89  177.14  184.38  189.87  197.70
 199.22  200.05  201.17  225.40  299.95  337.60  344.29  346.79  350.48
 355.67  365.32  378.53  387.50  398.76  425.67  454.23  455.87  468.44
 486.99  499.40  565.64  580.12  580.20  711.98  721.75  873.65  878.72
 974.89

second list - descending order:

 974.89  878.72  873.65  721.75  711.98  580.20  580.12  565.64  499.40
 486.99  468.44  455.87  454.23  425.67  398.76  387.50  378.53  365.32
 355.67  350.48  346.79  344.29  337.60  299.95  225.40  201.17  200.05
 199.22  197.70  189.87  184.38  177.14  168.89  167.67  163.42  136.53
 132.27  118.35  113.42  105.74  104.55  88.52  87.63  76.02  64.03
  59.06  42.38  29.85    6.82    2.91    0.63  -1.87  -10.69  -18.69
 -32.23  -40.34 -126.17 -152.79 -157.06 -170.40 -176.99 -180.62 -191.03
-207.22 -208.58 -209.56 -237.10 -239.58 -251.65 -254.70 -267.60 -279.66
-280.54 -286.04 -286.83 -290.67 -323.52 -327.15 -329.04 -330.79 -361.08
-391.15 -391.86 -393.01 -397.21 -430.49 -441.58 -473.20 -492.66 -497.48
-567.73 -583.92 -587.31 -630.81 -648.02 -680.65 -688.54 -728.50 -778.98
-834.74

third list - ascending order:

          C            C            C          For      However
          If          It      PREFACE          The        This
          a            a            a            a        about
      about          and          and      another          are
      become      become        best        book        book
        book      called        chip      choice    computer
      design      devoted      expand  fabrication    familiar
        for          get        have        help          if
          in          in    increase    involved          is
          is          is          is          is          it
          it        just    knowledge    language    language
    language        learn        made          not          of
          of          on          one          one          or
  processing  proficient  programming        quite        read
    secrets      seeking        speed        that          the
        the          the          the        then        thing
        this        this  thoroughly          to          to
          to          to          to      typing        want
        wise        with        word          you          you
        you          you          you        your        your



third list - descending order:

        your        your          you          you          you
        you          you        word        with        wise
        want      typing          to          to          to
          to          to  thoroughly        this        this
      thing        then          the          the          the
        the        that        speed      seeking      secrets
        read        quite  programming  proficient  processing
          or          one          one          on          of
          of          not        made        learn    language
    language    language    knowledge        just          it
          it          is          is          is          is
          is    involved    increase          in          in
          if        help        have          get          for
    familiar  fabrication      expand      devoted      design
    computer      choice        chip      called        book
        book        book        best      become      become
        are      another          and          and        about
      about            a            a            a            a
        This          The      PREFACE          It          If
    However          For            C            C            C

                        *** end of program execution ***

---

I'm not sure what's going on. Any help would be great.

I never told you how to do it. You misunderstood. I was pointing out to you that because of the way you had written your if statements it was possible the subscript would be past the end of the vector. It was up to you to fix. I never suggested any fix but did tell you that C++ has an algorithm to make a heap that can be used on a container that supports random access iterators and then once the heap is made it can be sorted with sort_heap. I said you are comparing your variables to the vectors size and if those variables are equal to the size then using them as an index into the vector wont work because it would be past the end of the vector.

vector vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);

this vector has size of 3. What value is stored at vec[3]? remember in C++ vectors are zero based. The last valid subscript for this vector is vec[2]. The last indexable element of the vector is always vec[ vec.size() - 1 ].

Do you have to code the heapsort yourself or can you just use the algorithms provided by the language? Heres a quick and dirty example of make_heap and sort_heap

Code:

---

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

void display( const vector<int>& vec, const char* str )
{
  cout << str << " ( " ;
  for ( vector <int>::const_iterator iter = vec.begin( ) ; iter != vec.end( ) ; ++iter )
  {
      cout << *iter << " ";
  }
  cout << ")." << endl;
}

int main()
{
  vector <int> vec;
  for ( int i = 0 ; i <= 9 ; i++ )
  {
      vec.push_back( i );
  }
  random_shuffle( vec.begin( ), vec.end( ) );
  display( vec, "The original vector is ");
  make_heap ( vec.begin( ), vec.end( ) );
  display( vec, "The less than heaped version is ");
  sort_heap( vec.begin(), vec.end() );
  display( vec, "The less than heap after sorting using the default comparison is ");
  random_shuffle( vec.begin( ), vec.end( ) );
  display( vec, "The original vector is now ");
  make_heap ( vec.begin( ), vec.end( ), greater<int>( ) );
  display( vec, "The greater than heaped version is ");
  sort_heap( vec.begin(), vec.end(), greater<int>() );
  display( vec, "The greater than heap after sorting using greater<int> as comparison is ");
  return 0;
}

---

Quote:

---

Originally Posted by youngyou4

Okay I tried your way but It only sorts some of the numbers.

---

Instead of trying to sort so many numbers, try to sort just three or four numbers.

Regards,

Paul McKenzie