10 Replies - 1487 Views - Last Post: 21 April 2012 - 06:35 PM Rate Topic: -----

#1 CoryG89  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 29-March 11

Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 03:45 PM

I have been trying to build up a small library of my own utility functions that can be used in all projects. I am attempting to code some generic functions that will handle dealings with std::vector objects. My "library" is simply implemented as two files "cgUtil.h" and "cgUtil.cpp" which I will include as needed in future projects.

A little backstory: I was working on a MaxHeap class that implements heapsort as a method. It uses primitive integer arrays. I was wanting to test this algorithm with random inputs against the heapsort algorithm included in the <algorithms> library. I discovered however that I could only use vectors with that algorithm and so I wanted to code a function that would allow me to allocate space for and copy a vector<int> into an integer array.

This is what I wrote:

using namespace std;

int *vecToAry(vector<int> input)
{
	int *output = new int[input.size()];
	copy(input.begin(), input.end(), output);
	return output;
}



After putting lots of utility functions together into said library I wanted to make some of them generic. So the above code then became:

using namespace std;

template <typename T>
T *vecToAry(vector<T> input)
{
	T *output = new T[input.size()];
	copy(input.begin(), input.end(), output);
	return output;
}



However, when I compile with the following driver I receive the linker errors below.

#include <iostream>
#include <vector>
#include "cgUtil.h"
using namespace std;

int main()
{
	int a[5] = {1,2,3,4,5};
	vector<int> v(a, a+5);
	
	int *result = vecToAry(v);

	ENTER_EXIT(0);
}



Error	1	error LNK2019: unresolved external symbol "int * __cdecl vecToAry<int>(class std::vector<int,class std::allocator<int> >)" (??$vecToAry@H@@YAPAHV?$vector@HV?$allocator@H@std@@@std@@@Z) referenced in function _main	C:\Users\cory\Desktop\Dropbox\Dev\Source\C++\HeapSort\HeapSort\heapsort.obj



I am not sure what I am doing wrong, or how I am supposed to create a generic function to do something similar if this is not possible. Anyone care to share some insight?

Is This A Good Question/Topic? 0
  • +

Replies To: Question about generic functions in C++ (vectors and templates)

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4140
  • View blog
  • Posts: 12,891
  • Joined: 25-December 09

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 03:58 PM

Did you perhaps forget to include the vector header file in you cgUtil.h header file? And do you have include guards in this header?

Also it is considered a bad practice to have the "using namespace std;" clause inside a header file.

Jim

This post has been edited by jimblumberg: 21 April 2012 - 03:59 PM

Was This Post Helpful? 0
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,267
  • Joined: 21-June 11

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 04:03 PM

Do you have the function definition in the header file or in a c++ file? For templated functions the definition needs to be in the header file.
Was This Post Helpful? 1
  • +
  • -

#4 CoryG89  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 29-March 11

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:02 PM

View Postsepp2k, on 21 April 2012 - 04:03 PM, said:

Do you have the function definition in the header file or in a c++ file? For templated functions the definition needs to be in the header file.


Sure enough this was the problem. Thanks for the tip. Any insight as to why this is so with templated functions? Makes me tempted to put all the definitions in the header and just include that to be consistent.
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:09 PM

well, there is a linker issue here but there is another issue too.

template <typename T>
T *vecToAry(vector<T> input)
{
	T *output = new T[input.size()];
	copy(input.begin(), input.end(), output);
	return output;
}


this literally has, *no* purpose. vectors, and many other things in C++, provide iterators. iterators allow for generic code to be written that works for vectors, lists, deques, maps, sets, complex classes like LLVM's module class(has like 4 different types of iterators), and an unbounded number of other data structures. you would be *FAR* better off just using the '=' operator of an std::vector *if* you absolutely needed a copy.

std::vector<int> x;
//...
//populate x here
//...
//copy x
std::vector<int> y = x;



you can actually pretty easily convert your sorting algorithm to use iterators.

Quote

Any insight as to why this is so with templated functions? Makes me tempted to put all the definitions in the header and just include that to be consistent.

in a separate C++ file, the code gets compiled to a linkable binary. in binary form, the code of the template is no longer known so the compiler can't recompile the template for new types(and other template arguments), it doesn't exist anymore. with header files the template gets copied into every source file that includes it; this means that each binary compiles just the templates it needs.

if there is a particular application of a template that is being used frequently in many files you can use what is called specialization. with specialization you can tell the compiler to explicitly compile 1 form of the template so that it *can* go in a separate binary file. this can improve compile times, code size, and even locality.

a lot of libraries are just written in headers actually but larger projects have to worry about compile times, and even code size. for most projects that I do I just put everything in headers.

This post has been edited by ishkabible: 21 April 2012 - 05:21 PM

Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is online

  • member icon


Reputation: 4140
  • View blog
  • Posts: 12,891
  • Joined: 25-December 09

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:12 PM

Templates are quite often header only implementations. This is because both the definition and implementation must be in the same compilation unit, it is usually easier just to put it all in the header.

Jim
Was This Post Helpful? 0
  • +
  • -

#7 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,267
  • Joined: 21-June 11

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:18 PM

View PostCoryG89, on 22 April 2012 - 02:02 AM, said:

Any insight as to why this is so with templated functions?


When you have a templated function, the compiler doesn't create one function, it creates one function for every instantiation of the template. It has to because it's impossible to have one function that can deal with an argument of an arbitrary type (and thus size). So if you have a function template template<class T> f(T x) {...} and you use it once with a char and once with an int as arguments, the compiler will compile two functions __f_char(char x) and __f_int(int x). However to do that the compiler needs to know which types the function will be used with. So the function can't be compiled in a different compilation unit than it is used (i.e. the compiler needs to be able to see the function's source code when it compiles the code that uses the function).

Quote

Makes me tempted to put all the definitions in the header and just include that to be consistent.


For functions that aren't free static functions, templated functions, inline functions or member functions of a templated class, that would actually be an error. I.e. if you define such a function in the header and include that header in multiple c++ files, you will get a linker error when linking those c++ files' object files together.

This post has been edited by sepp2k: 21 April 2012 - 05:27 PM

Was This Post Helpful? 0
  • +
  • -

#8 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:23 PM

Quote

For non-templated, non-inline functions that would actually be an error. I.e. if you define such a function in the header and include that header in multiple c++ files, you will get a linker error when linking those c++ files' object files together.


you could make it static to fix this too(not just template or inline).

This post has been edited by ishkabible: 21 April 2012 - 05:24 PM

Was This Post Helpful? 0
  • +
  • -

#9 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2133
  • View blog
  • Posts: 3,267
  • Joined: 21-June 11

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 05:27 PM

View Postishkabible, on 22 April 2012 - 02:23 AM, said:

you could make it static to fix this too(not just template or inline).


Good point. I've edited that into my post.
Was This Post Helpful? 0
  • +
  • -

#10 CoryG89  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 9
  • Joined: 29-March 11

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 06:19 PM

View Postishkabible, on 21 April 2012 - 05:09 PM, said:

this literally has, *no* purpose. vectors, and many other things in C++, provide iterators. iterators allow for generic code to be written that works for vectors, lists, deques, maps, sets, complex classes like LLVM's module class(has like 4 different types of iterators), and an unbounded number of other data structures. you would be *FAR* better off just using the '=' operator of an std::vector *if* you absolutely needed a copy.


I'm not sure what you mean by this. Are you saying that I shouldn't be trying to convert a templated vector object to a corresponding array? Or are you saying that there is a better way to do this. The code you gave simply assigned one vector to another.

Quote

you can actually pretty easily convert your sorting algorithm to use iterators.


Yes, I am aware of this and probably will sometime in the future. This was a quick fix to compare output results.
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: Question about generic functions in C++ (vectors and templates)

Posted 21 April 2012 - 06:35 PM

Quote

I'm not sure what you mean by this. Are you saying that I shouldn't be trying to convert a templated vector object to a corresponding array? Or are you saying that there is a better way to do this. The code you gave simply assigned one vector to another.


I'm saying to use iterators. Sorry, I should have been more clear. If you used iterators it would modify the vector in place; hence if you needed a copy like what you did, there is a better way to make a copy and you can modify that copy in place using an iterator implementation.

This post has been edited by ishkabible: 21 April 2012 - 06:37 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1