C++

Forum

 
Function Pointer Issue

kevinkjt2000 (1063)
I'm receiving a linker error that doesn't make a whole lot of sense to me:
C:\Users\Kevin\Desktop\College\CSC 4400 - Analysis of Algorithms\program/main.cpp:20: undefined refer
ence to `Backtrack<std::string>::Backtrack(std::vector<std::string, std::allocator<std::string> > (*)
(std::vector<std::string, std::allocator<std::string> > const&), bool (*)(std::vector<std::string, st
d::allocator<std::string> > const&, std::vector<std::string, std::allocator<std::string> > const&), b
ool (*)(std::vector<std::string, std::allocator<std::string> > const&, std::vector<std::string, std::
allocator<std::string> > const&), std::vector<std::string, std::allocator<std::string> > (*)(std::vec
tor<std::string, std::allocator<std::string> > const&, std::vector<std::string, std::allocator<std::s
tring> > const&), std::vector<std::string, std::allocator<std::string> > (*)(std::vector<std::string,
 std::allocator<std::string> > const&, std::vector<std::string, std::allocator<std::string> > const&)
, void (*)(std::vector<std::string, std::allocator<std::string> > const&, std::vector<std::string, st
d::allocator<std::string> > const&))'


So what I read is something akin to: Backtrack<string>(vector<string> (*)(vector<string> const&), ... ) does not exist? But as far as I know is this constructor does exist in the Backtrack class.
So... I'm assuming its a problem with how I'm using templates. So my question is how do I create an object of type Backtrack with these callback function pointers?

main.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include "Backtrack.h"
#include <iostream>
#include <string>
#include <vector>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
using std::vector;

vector<string> root(vector<string> const&);
bool reject(vector<string> const&, vector<string> const&);
bool accept(vector<string> const&, vector<string> const&);
vector<string> first(vector<string> const&, vector<string> const&);
vector<string> next(vector<string> const&, vector<string> const&);
void output(vector<string> const&, vector<string> const&);

int main(int argc, char **argv)
{
   Backtrack<string> bt(&root, &reject, &accept, &first, &next, &output);
   return 0;
}

vector<string> root(vector<string> const& P)
{
   return vector<string>(1, P[0]);
}

bool reject(vector<string> const& P, vector<string> const& c)
{

}

bool accept(vector<string> const& P, vector<string> const& c)
{

}

vector<string> first(vector<string> const& P, vector<string> const& c)
{

}

vector<string> next(vector<string> const& P, vector<string> const& s)
{

}

void output(vector<string> const& P, vector<string> const& c)
{

}


Backtrack.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <vector>
using std::vector;

template <class T>
class Backtrack
{
private:
   vector<T> P;
   void bt(vector<T>& c);
   vector<T> (*root)(vector<T> const&);
   bool (*reject)(vector<T> const&, vector<T> const&);
   bool (*accept)(vector<T> const&, vector<T> const&);
   vector<T> (*first)(vector<T> const&, vector<T> const&);
   vector<T> (*next)(vector<T> const&, vector<T> const&);
   void (*output)(vector<T> const&, vector<T> const&);
public:
   Backtrack<T>( vector<T> (*root)(vector<T> const&),
         bool (*reject)(vector<T> const&, vector<T> const&),
         bool (*accept)(vector<T> const&, vector<T> const&),
         vector<T> (*first)(vector<T> const&, vector<T> const&),
         vector<T> (*next)(vector<T> const&, vector<T> const&),
         void (*output)(vector<T> const&, vector<T> const&) );
   void backtrack();
};
Last edited on
Cubbi (4774)
It's a linker error, not a compiler error. Did you by any chance define the Backtrack<T>'s constructor in a .cpp file? It needs to be in the header.
kevinkjt2000 (1063)
I did define it in a .cpp file but when linking I pass both main.o and Bactrack.o
I moved the definition to the header, but it still produced the same linker error.
For now I'm going to leave it in the cpp file.

makefile:
all: main.exe
.PHONY : all

debug: all
	gdb main.exe
.PHONY : debug

run: all
	./main.exe
.PHONY : run

main.o : main.cpp
	g++ -c -g main.cpp

bactrack.o : Backtrack.cpp
	g++ -c -g Backtrack.cpp

main.exe : main.o Backtrack.o
	g++ -o main.exe main.o Backtrack.o

clean :
	rm -f *.exe *.o
.PHONY : clean
Cubbi (4774)
For now I'm going to leave it in the cpp file.

Why? It's an obvious error.
kevinkjt2000 (1063)
If simply moving it the first time did not fix the obvious error, then I'm assuming there is a seperate problem causing the linker error. Backtrack.cpp is down below feel free to move the constructor to Backtrack.h then run my makefile and get the same linker error if you don't believe me when I say I get the same error.
I think my error lies somehow with an incorrect usage of function pointers and templates being combined the wrong way.
I'm going to attempt to get rid of the templates to see if it works without them.

Backtrack.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include "Backtrack.h"

template <class T>
Backtrack<T>::Backtrack( vector<T> (*root)(vector<T> const&),
      bool (*reject)(vector<T> const&, vector<T> const&),
      bool (*accept)(vector<T> const&, vector<T> const&),
      vector<T> (*first)(vector<T> const&, vector<T> const&),
      vector<T> (*next)(vector<T> const&, vector<T> const&),
      void (*output)(vector<T> const&, vector<T> const&) )
{
   this->root = root;
   this->reject = reject;
   this->accept = accept;
   this->first = first;
   this->next = next;
   this->output = output;
}

template <class T>
void Backtrack<T>::bt(vector<T>& c)
{
   if( reject(P, c) )
      return;
   if( accept(P, c) )
      output(P, c);
   vector<T> s = first(P, c);
   while( s.size() != 0 )
   {
      bt(s);
      s = next(P, s);
   }
}

template <class T>
void Backtrack<T>::backtrack()
{
   bt(root(P));
}
Last edited on
Disch (13742)
Templated functions are not actual functions, they're blueprints for the compiler to generate functions. As such, they are not externally linked. This is why the linker is not finding them, and is why you cannot define them in cpp files. Linking to backtrack.o does nothing for you because backtrack.o does not have any functions to link with.

The solution, as Cubbi has already pointed out, is to define all of Backtrack's members in the header file and do not have a separate cpp file.


I just copy/pasted the code you posted, moved the template functions to the header file and it compiled and linked just fine (after fixing one or two unrelated problems). So that indeed is the problem. Though granted I'm using VS since I don't touch makefiles unless I absolutely have to.
kevinkjt2000 (1063)
Apparently I moved them incorrectly earlier then. What I was doing was moving the code but not rewriting my makefile to link correctly.
Thanks for the reminder about templates not being actual functions Disch!

Final Solution for anyone who finds this later:
Backtrack.hpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
// Pseudocode
// In order to apply backtracking to a specific class of
// problems, one must provide the data P for the particular
// instance of the problem that is to be solved, and six
// procedural parameters, root, reject, accept, first,
// next, and output. These procedures should take the
// instance data P as a parameter and should do the following:
// root(P): return the partial candidate at the root of the search tree.
// reject(P,c): return true only if the partial candidate c is not worth completing.
// accept(P,c): return true if c is a solution of P, and false otherwise.
// first(P,c): generate the first extension of candidate c.
// next(P,s): generate the next alternative extension of a candidate, after the extension s.
// output(P,c): use the solution c of P, as appropriate to the application.

// The backtracking algorithm reduces then to the call bt(root(P)), where bt is the following recursive procedure:
// procedure bt(c)
   // if reject(P,c) then return
   // if accept(P,c) then output(P,c)
   // s <- first(P,c)
   // while s != null do
      // bt(s)
      // s <- next(P,s)

#ifndef BACKTRACK
#define BACKTRACK

#include <vector>
using std::vector;

template <class T>
class Backtrack
{
private:
   vector<T> P;
   vector<T> (*root)(vector<T>);
   bool (*reject)(vector<T>, vector<T>);
   bool (*accept)(vector<T>, vector<T>);
   vector<T> (*first)(vector<T>, vector<T>);
   vector<T> (*next)(vector<T>, vector<T>);
   void (*output)(vector<T>, vector<T>);
   void bt(vector<T>& c)
   {
      if( reject(P, c) )
         return;
      if( accept(P, c) )
         output(P, c);
      vector<T> s = first(P, c);
      while( s.size() != 0 )
      {
         bt(s);
         s = next(P, s);
      }
   }
public:
   Backtrack<T>( vector<T> (*root)(vector<T>),
         bool (*reject)(vector<T>, vector<T>),
         bool (*accept)(vector<T>, vector<T>),
         vector<T> (*first)(vector<T>, vector<T>),
         vector<T> (*next)(vector<T>, vector<T>),
         void (*output)(vector<T>, vector<T>) )
   {
      this->root = root;
      this->reject = reject;
      this->accept = accept;
      this->first = first;
      this->next = next;
      this->output = output;
   }
   
   void backtrack()
   {
      bt(root(P));
   }
};

#endif

main.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include "Backtrack.hpp"
#include <iostream>
#include <string>
#include <vector>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
using std::vector;

vector<string> root(vector<string>);
bool reject(vector<string>, vector<string>);
bool accept(vector<string>, vector<string>);
vector<string> first(vector<string>, vector<string>);
vector<string> next(vector<string>, vector<string>);
void output(vector<string>, vector<string>);

int main(int argc, char **argv)
{
   Backtrack<string> bt(&root, &reject, &accept, &first, &next, &output);
   return 0;
}

vector<string> root(vector<string> P)
{
   return vector<string>(1, P[0]);
}

bool reject(vector<string> P, vector<string> c)
{

}

bool accept(vector<string> P, vector<string> c)
{

}

vector<string> first(vector<string> P, vector<string> c)
{

}

vector<string> next(vector<string> P, vector<string> s)
{

}

void output(vector<string> P, vector<string> c)
{

}

makefile:
all: main.exe
.PHONY : all

debug: all
	gdb main.exe
.PHONY : debug

run: all
	./main.exe
.PHONY : run

main.o : main.cpp
	g++ -c -g main.cpp

main.exe : main.o
	g++ -o main.exe main.o

clean :
	rm -f *.exe *.o
.PHONY : clean
Topic archived. No new replies allowed.