template and static methods

[CHAFIK Wassime]

hi
well i was testing various implementations of sorting algorithms,
and i found my self stuck in this error

testSortingCpp.cpp:36: undefined reference to `Sorting<Node>::fibHeapSort
(std::vector<Node*, std::allocator<Node*> >&)'

i'm using g++ ver: 4.3.3 on a i486-linux-gnu platform

#####################################################
here is sorting.hpp
#####################################################
*!implementation of various sorting algorithms.
*/
#ifndef __SORTING_HPP
#define __SORTING_HPP
#include <vector>


/**utility class providing various sorting algorithms and helper methods.
*/
template<typename T>
class Sorting{
public:
static void fibSiftDown( std::vector<T*>& heap,int start ,int end);
/**<sifting down upon a fibonacci heap stored in a vector*/
static void fibHeapify( std::vector<T*>& heap,int end);
/**<heapify a fibonacci heap stored in a vector*/
static void fibHeapSort( std::vector<T*>& heap);
/**< the actual fibonacci heap sort*/
};

#endif


##################################################
here is sorting.cpp
##################################################
#include "sorting.hpp"
using namespace std;

template<typename T>
void Sorting<T>::fibSiftDown(vector<T*>& heap,int start,int end){
int firstChild=3*start+1;
int maxChild = firstChild;
//if start hasn't at least a child return
if(firstChild>end) return;
//point to the max child
if(firstChild+1<=end && *heap[firstChild+1] > *heap[firstChild] ){
maxChild++;
}
if(firstChild+2<=end && *heap[firstChild+2] > *heap[maxChild] ){
maxChild=firstChild+2;
}
if(*heap[start] < *heap[maxChild]){
T* tmp = heap[start];
heap[start] = heap[maxChild];
heap[maxChild] = tmp;
//siftdown the child too
fibSiftDown(heap,maxChild,end);
}
};

template<typename T>
void Sorting<T>::fibHeapify(vector<T*>& heap,int end){
int start = (end-2)/3;
while(start>=0){
fibSiftDown(heap,start,end);
start--;
}
};

template<typename T>
void Sorting<T>::fibHeapSort(vector<T*>& heap){
int end = heap.size()-1;
while(end>0){
fibHeapify(heap,end);
T* tmp = heap[0];
heap[0] = heap[end];
heap[end] = tmp;
end--;
}
}

#########################################################
finally the testing main,
#########################################################

#include "sorting.hpp"
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#define MAXELEMENT 100
using namespace std;
class Node{
public:
int val;
Node(int a):val(a){};
Node(const Node& n):val(n.val){};
};
bool operator < (const Node a,const Node b){
return a.val < b.val;
};
bool operator > (const Node a,const Node b){
return a.val > b.val;
};
bool operator <= (const Node a,const Node b){
return a.val<=b.val;
};
bool operator >= (const Node a,const Node b){
return a.val>=b.val;
};
bool operator == (const Node a,const Node b){
return a.val == b.val;
}

int main(int arg, char** args){
srand(time(0));
vector<Node *> * ptree = new vector<Node*>(MAXELEMENT,new Node(rand
()));
for(int i =1;i<MAXELEMENT;i++){
(*ptree)= new Node(rand());
};
Sorting<Node>::fibHeapSort(*ptree);
cout<<"ordered sequence"<<endl;
for(int i = 0;i<MAXELEMENT;i++){
cout<<(*ptree)->val<<endl;
};
return 0;
}
############################################

i really can't understand what happened exactly
i tested various flavor of this implementation but i can't understand
this particular one


sorry for my English and thanks in advance

 

[red floyd]

hi
well i was testing various implementations of sorting algorithms,
and i found my self stuck in this error

testSortingCpp.cpp:36: undefined reference to `Sorting<Node>::fibHeapSort
(std::vector<Node*, std::allocator<Node*> >&)'

i'm using g++ ver: 4.3.3 on a i486-linux-gnu platform

#####################################################
here is sorting.hpp
#####################################################
*!implementation of various sorting algorithms.
*/
#ifndef __SORTING_HPP
#define __SORTING_HPP
[remainder redacted]

In addition to what Victor said, your code is ill-formed. Any
identifier with a double underscore is reserved to the implementation.
That is, you MAY NOT use it for your own purposes.

Change your include guard to something like SORTING_HPP_

 

[chafik.wassime]

hi
well i was testing various implementations of sorting algorithms,
and i found my self stuck in this error

testSortingCpp.cpp:36: undefined reference to `Sorting<Node>::fibHeapSort
(std::vector<Node*, std::allocator<Node*> >&)'

i'm using g++ ver: 4.3.3 on a i486-linux-gnu platform

#####################################################
here is  sorting.hpp
#####################################################
*!implementation of various sorting algorithms.
 */
#ifndef __SORTING_HPP
#define __SORTING_HPP
[remainder redacted]

In addition to what Victor said, your code is ill-formed.  Any
identifier with a double underscore is reserved to the implementation.
That is, you MAY NOT use it for your own purposes.

Change your include guard to something like SORTING_HPP_

thanks a lot and yeah i was impatient while reading the faq
and reaaaally thanks for the comment on the code form
have a nice day

 

[Juha Nieminen]

Change your include guard to something like SORTING_HPP_

In fact, it's highly recommended that the include guard preprocessor
identifier be more unique.

Since the preprocessor identifier is never actually *used* anywhere
for anything (other than for its role as an inclusion guard in the two
preprocessor lines at the beginning of the file), there's no need to
make it readable or logical in any way. It's better to make this
identifier overly long and obfuscated than short and readable. (It
wouldn't be the first time that two different headers in two different
libraries use the *same* inclusion guard identifier, causing very hard
to trace odd compiler errors when both libraries are used, especially if
they are used through multiple layers of indirection.)

 

[James Kanze]

In fact, it's highly recommended that the include guard
preprocessor identifier be more unique.

Since the preprocessor identifier is never actually *used*
anywhere for anything (other than for its role as an inclusion
guard in the two preprocessor lines at the beginning of the
file), there's no need to make it readable or logical in any
way. It's better to make this identifier overly long and
obfuscated than short and readable. (It wouldn't be the first
time that two different headers in two different libraries use
the *same* inclusion guard identifier, causing very hard to
trace odd compiler errors when both libraries are used,
especially if they are used through multiple layers of
indirection.)

I might add that you should never have to type the include guard
anyway. Just configure your editor to insert it automatically
any time you open a new .hh (or .hpp, or whatever) file, just
like you do to get the copyright notices and stuff in the code.
(This is trivial with vim and emacs, but I imagine any decent
editor would support it.)

(Under Unix, I use
guard3=` dd bs=24 count=1 if=/dev/random 2> /dev/null |
tr '\000-\377' "${alnum}${alnum}${alnum}${alnum}0-7" `
to get the random part---I got this particular solution from
Gennaro Prota; I was using a considerably more complicated
version using od and awk before.)

 

[Michael DOUBEZ]

I might add that you should never have to type the include guard
anyway. Just configure your editor to insert it automatically
any time you open a new .hh (or .hpp, or whatever) file, just
like you do to get the copyright notices and stuff in the code.
(This is trivial with vim and emacs, but I imagine any decent
editor would support it.)

(Under Unix, I use
guard3=` dd bs=24 count=1 if=/dev/random 2> /dev/null |
tr '\000-\377' "${alnum}${alnum}${alnum}${alnum}0-7" `

Or simply:
`xxd -u -c 24 -l 24 -p /dev/random 2> /dev/null`

 

[James Kanze]

Or simply:
`xxd -u -c 24 -l 24 -p /dev/random 2> /dev/null`

But you'd still have to write xxd. It's not standard Unix.

Of course, you can get more or less the same thing by piping od
through sed (to strip the offset and the blanks). With the same
problem: it uses a set of a lot less characters (16 instead of
62), so you need a lot more characters to achieve the same
amount of variation. (In my version, "alnum" is "a-zA-Z0-9".)
My original version used od through sed; I then replaced sed
with an awk script which picked characters out of a table of all
the alphanumerics, precisely to increase the number of
characters used (and thus the variation). Then Genny proposed
the above to me, which is even simpler.

Note that with all of these variants, you can run out of
entropy, with the result that reading /dev/random becomes
inordinately slow. If I'm generating code from C++, I'll use
/dev/random to seed the random number generator, and use that
for the actual random characters. Of course, in C++, you can
get even fancier, ensuring that the first character is alpha,
using '_' as well (but ensuring that it doesn't occur twice in
succession), etc. For the most part, this is probably over
perfectionnism, but why not, if you feel like it?

 

[Michael DOUBEZ]

But you'd still have to write xxd. It's not standard Unix.

True but it is usually part of the vim package

Of course, you can get more or less the same thing by piping od
through sed (to strip the offset and the blanks).
With the same problem: it uses a set of a lot less characters (16 instead of
62), so you need a lot more characters to achieve the same
amount of variation.

Given the probability of collision, so much variation seems overkill to
me but if it is the same price ... why not.