C++ How to use vectors with templates?

Question

I'm working through an algorithm text, trying to implement everything in C++ for practice. But I can't seem to figure out templating.I have three files: algPlayground.h

#include <stdlib.h>
#include <vector>

using namespace std;

template <class T> void insertionSort(vector<T>& toSort);

algPlayground.cpp

#include <stdlib.h>
#include <vector>
#include "algPlayground.h"

using namespace std;

template <class T> void insertionSort(vector<T>& toSort) {
    for (int j=1; j < toSort.size(); ++j) {
        T key = toSort[j];
        int i = j-1;

        while (i > -1  && toSort[i] > key) {
            toSort[i+1] = toSort[i];
            i -= 1;
        } // end while

    toSort[i+1] = key;

    } // end for

} // end insertionSort

and algTest.cpp

#include <stdlib.h>
#include <vector>
#include <iostream>
#include "algPlayground.h"

using namespace std;

int main() {

    vector<int> vectorPrime(5);

    vectorPrime[0]=5;
    vectorPrime[1]=3;
    vectorPrime[2]=17;
    vectorPrime[3]=8;
    vectorPrime[4]=-3;

    insertionSort(vectorPrime);
    for (int i=0; i<vectorPrime.size(); ++i) {
        cout << vectorPrime[i] << " ";
    }// end for
}

I get the following error:

algTest.cpp:(.text+0xb1): undefined reference to `void insertionSort<int>(std::vector<int, std::allocator<int> >&)'
collect2: error: ld returned 1 exit status

I saw this thread where, someone suggested that the proper way to do this was

template<typename T, typename A>
void some_func( std::vector<T,A> const& vec ) {
}

but when I make that correction, I'm still getting a similar error:

algTest.cpp:(.text+0xb1): undefined reference to `void insertionSort<int, std::allocator<int> >(std::vector<int, std::allocator<int> >&)'
collect2: error: ld returned 1 exit status

I have no idea where I'm going wrong here. Help?

this is not a problems with vector in particular. Splitting declarations and definitions of templates is not a good idea in general. — Sebastian Hoffmann, Feb 16 '14 at 15:17

score 2 · Accepted Answer · answered Feb 16 '14 at 15:17

Your problem is that you need to implement the template in the header file. The compiler needs to be able to see the implementation of the template whenever it is being instantiated so that it can generate the appropriate code. So just move the definition from algPlayground.cpp to algPlayground.h.

An alternative approach that achieves the same thing is to reverse the #includes, so that at the bottom of algPlayground.h you #include "algPlayground.cpp". People who like this approach often use a tpp extension for the implementation file to make it clear what's going on.

score 1 · Answer 2 · edited May 23 '17 at 12:21

1

The problem is that your insertionSort<T> template is not instantiated in the algTest.cpp file. Move the definition of the template either to the header file (recommended) or to algTest.cpp, and you should be good.
You can check this question or that question for more details.

edited May 23 '17 at 12:21

Community

1
1

answered Feb 16 '14 at 15:18

Martin J.

5,028
4
24
41

C++ How to use vectors with templates?

2 Answers2

Linked