template and static methods

Discussion in 'C++' started by CHAFIK Wassime, Apr 21, 2009.

  1. 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
     
    CHAFIK Wassime, Apr 21, 2009
    #1
    1. Advertising

  2. CHAFIK Wassime

    red floyd Guest

    CHAFIK Wassime wrote:
    > 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_
     
    red floyd, Apr 22, 2009
    #2
    1. Advertising

  3. CHAFIK Wassime

    Guest

    On Apr 22, 3:36 am, red floyd <> wrote:
    > CHAFIK Wassime wrote:
    > > 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
     
    , Apr 22, 2009
    #3
  4. red floyd wrote:
    > 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.)
     
    Juha Nieminen, Apr 22, 2009
    #4
  5. CHAFIK Wassime

    James Kanze Guest

    On Apr 22, 12:13 pm, Juha Nieminen <> wrote:
    > red floyd wrote:
    > > 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.)


    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.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Apr 22, 2009
    #5
  6. James Kanze wrote:
    > On Apr 22, 12:13 pm, Juha Nieminen <> wrote:
    >> red floyd wrote:
    >>> 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.)

    >
    > 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`

    --
    Michael
     
    Michael DOUBEZ, Apr 22, 2009
    #6
  7. CHAFIK Wassime

    James Kanze Guest

    On Apr 22, 2:08 pm, Michael DOUBEZ <> wrote:
    > James Kanze wrote:
    > > On Apr 22, 12:13 pm, Juha Nieminen <> wrote:
    > >> red floyd wrote:

    > > 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`


    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?

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Apr 23, 2009
    #7
  8. James Kanze wrote:
    > On Apr 22, 2:08 pm, Michael DOUBEZ <> wrote:
    >> James Kanze wrote:
    >>> On Apr 22, 12:13 pm, Juha Nieminen <> wrote:
    >>>> red floyd wrote:
    >>> 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`

    >
    > 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.

    --
    Michael
     
    Michael DOUBEZ, Apr 23, 2009
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. SaravanaKumar
    Replies:
    6
    Views:
    9,409
    Tony Morris
    Oct 19, 2004
  2. Buster Copley
    Replies:
    5
    Views:
    562
    Gianni Mariani
    Jul 7, 2003
  3. Replies:
    0
    Views:
    322
  4. o_ssie
    Replies:
    0
    Views:
    319
    o_ssie
    Apr 9, 2009
  5. Kenneth McDonald
    Replies:
    5
    Views:
    324
    Kenneth McDonald
    Sep 26, 2008
Loading...

Share This Page