Programming Forums - /usr/bin/ld: Undefined symbols

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - /usr/bin/ld: Undefined symbols (http://www.programmingforums.org/showthread.php?t=12652)

/usr/bin/ld: Undefined symbols

Mac OS X 10.4 Terminal

$ g++ vector.cpp vector_dimension_exception.cpp test.cpp

/usr/bin/ld: Undefined symbols:

trace::vector<double>::magnitude() const

collect2: ld returned 1 exit status

I am pretty sure I have defined that function and compiled it in that command. What is going on here? Interestingly, if I move man right to the bottom of vector.cpp, it compiles and runs perfectly.

vector.h



#ifndef _TRACE_VECTOR

#define _TRACE_VECTOR



#include "vector_dimension_exception.h"

#include <vector>



namespace trace

{

  template< typename T>

  class vector : public std::vector< T >

  {

  public:

    T magnitude() const;

    T dot_product(const vector< T > &) const throw(vector_dimension_exception);

  };

}



#endif

vector.cpp



#include "vector.h"

#include <cmath>



template< typename T >

T trace::vector< T >::magnitude() const

{

  T squares_sum = 0;

  for (int t = 0; t < this->size(); ++ t)

    squares_sum += std::exp(log((*this)[t]) * 2);

  return std::exp(log(squares_sum) * 1 / 2);

}



template< typename T >

T trace::vector< T >::dot_product(const vector< T > &value) const throw(vector_dimension_exception)

{

  if (this->size() != value.size())

    throw vector_dimension_exception();

  T dot_product = 0;

  for (int t = 0; t < this->size(); ++ t)

    dot_product += this->at(t) * value.at(t);

  return dot_product;

}

test.cpp



#include <iostream>

#include "vector.h"



int main()

{

  trace::vector< double > vector1;

  vector1.push_back(3);

  vector1.push_back(4);

  std::cout << vector1.magnitude() << std::endl;

  trace::vector< double > vector2;

  vector2.push_back(5);

  vector2.push_back(12);

  std::cout << vector2.magnitude() << std::endl;

  return 0;

}

When working with templates, the compiler needs to see the complete definition. When compiling test.cpp only sees the declaration of trace::vector<T>::magnitude() but does not see the definition. This results in linker error (i.e. the messages from /usr/bin/ld are) about undefined symbols (i.e. the linker cannot find a definition of the function to link in).

There are some techniques to work around this. For information on going this with g++, have a look here.

Incidentally, unrelated to your problem: deriving a class from std::vector<> is not usually a good idea. std::vector<> is not designed to be used that way.

thanks grumpy. of course that makes perfect sense to me now.

on the note of deriving from std::vector: every class is designed to be a derivative class, that is built into the language. i guess not every class is designed to be destroyed through polymorphism. i have no custom destructor logic. if i did, i am not holding onto my vector using pointers to std::vector. why would i want to reinvent the wheel?

i just wrote those two methods to use algorithm instead of for loops and all my future methods will use algorithm also. there are so many useful things in the stl classes that i would just hate rewriting them or aggregating them even. how would you approach the issue?

Quote:

Originally Posted by jubitzu (Post 124343)

on the note of deriving from std::vector: every class is designed to be a derivative class, that is built into the language.

Absolute rubbish. The language has some shortfalls in the sense that, by default, it is possible to derive from a class even in cases where doing so doesn't make sense (eg can cause undefined behaviour). There are several reasons those shortfalls exist, such as;

1) the language design expects the programmer to be disciplined, and avoid doing things that don't make sense. In other words, the language provides tools for the programmer, but the programmer is responsible for using the right tool for the right job;

2) it is difficult to envisage all cases in which derivation does not make sense, and therefore build features into the language to detect them, let alone prevent them. That is the reason cases where derivation does not make sense are often associated with some form of undefined behaviour.

C++ is not unique in this regard; if you look carefully at into the corners of specifications for other languages (eg Java, Ada, Smalltalk) you will find things that are the equivalent of C++'s notion of undefined behaviour.

C++ goes a bit further in this regard because of its backward compatibility to C. For example, a side effect of the "no runtime overhead unless a feature is used" rule is that the language design assumes classes will NOT be derived from, despite the fact that there is usually nothing stopping the programmer from deriving a class from them.

Just because something is technically allowed within a language, does not mean the programmer has absolute freedom to use it. It can actually mean (as it does in this case) that current state-of-the-art compiler technologies cannot prevent a programmer from doing certain things, or detect cases when they have.

Quote:

Originally Posted by jubitzu (Post 124343)

i guess not every class is designed to be destroyed through polymorphism. i have no custom destructor logic. if i did, i am not holding onto my vector using pointers to std::vector. why would i want to reinvent the wheel?

Not having a "custom destructor logic" is not a sufficient reason for assuming you are safe to derive from a class like std::vector. It is equally unsafe if your derived class has an empty constructor. You are still skirting with undefined behaviour. It happens with some compilers that things will work as you intend. It also happens with some other compilers that they will not. That is one of the marvels of undefined behaviour: with some compilers it can yield the behaviour you expect, so you think you are safe even when you are not.

Unfortunately, some help files with some compilers tell you otherwise. As do some textbooks written by people who only use those particular compilers. That does not make your statement correct. It is still wrong.

Quote:

Originally Posted by jubitzu (Post 124343)

i just wrote those two methods to use algorithm instead of for loops and all my future methods will use algorithm also. there are so many useful things in the stl classes that i would just hate rewriting them or aggregating them even. how would you approach the issue?

That's simple: I would not have a derived class. I would implement the algorithm in separate functions. For example, if your "magnitude" function is specific to a vector type, then the implementation would be;

// Warning:  following not fed to a compiler.

//   It may include errors.  It illustrates the idea only



namespace trace

{

    template <typename T> magnitude(const std::vector<T> &, T initialvalue = 0);

}



template<typename T>

T trace::magnitude(const std::vector<T> &v, T initialvalue)

{

    typename std::vector<T>::const_iterator i, end = v.end();

    for (i = v.first(); i != end; ++i)

    {

         // warning:  potential for overflow here.

        initialvalue += (*i) * (*i);

    }

    return std::sqrt(initialvalue);

}

If the code was equally applicable to any container (eg a vector<T>, a list<T>, a simple array of T, etc) I would provide overloaded versions of the functions that take iterators so they can work on any container. For example;

// Warning:  following not fed to a compiler.

//    It may include errors.  It illustrates the idea only



namespace trace

{

    template <typename InputIterator, typename T> magnitude(InputIterator first, InputIterator last, T initialvalue = 0);

}



template<typename InputIterator, typename T>

T trace::magnitude(InputIterator first, InputIterator last, T initialvalue)

{

    // implement the function here in terms of arguments 

    while (first != last)

    {

         // warning:  potential for overflow here.

        initialvalue += (*first) * (*first);

        ++first;

    }

    return std::sqrt(initialvalue);

}



int main()

{

    std::vector<double> x;

      // add some elements to x

    double mag_x = trace::magnitude(x.begin(), x.end());



       // use the first version of the algorithm I gave above



    double mag_x2 = trace::magnitude(x);



    //  I can also do this, if it makes sense, which can't be done with

    //   a derived class



    std::list<double> y;

      // add some elements to y

    double mag_y = trace::magnitude(y.begin(), y.end());



}

If the functions only work for particular types of T (which, in your case, is any type that can be implicitly converted to a double and has positive values), then use a traits class to trigger a compile error if a different type is supplied.

If you think this is an inferior approach to yours, consider the following;

1) No scope for undefined behaviour because of invalid class derivation. In fact, no derived classes.

2) The C++ standard uses the same approach for defining standard algorithms.

You might also want to actually look into the standard algorithms to see if your algorithm can be implemented in terms of them, rather than rolling your own. For example, your dot_product() can probably be implemented in terms of the standard algorithm named inner_product() -- and might just be an alternate name for it. In other words, you are recreating the wheel by implementing something that is already in the C++ standard.

on reinventing the wheel: i had rewritten my methods using dot_product as inner_product with my size checking exception. and i had defined magnitude as the square root of the dot product of the vector with itself.

back to the original topic: what makes std::vector unintended for derivation? where is that documented?

1) Substitutibility means that, if S is a subtype of T, then objects of type T in a program may be replaced with objects of type S without altering any of the desirable properties (most notably correctness) of that program.

2) This is interpreted in OO methodologies using the Liskov Substitution Principle which (when applied to class hierarchies) means that a derived class can be used in any place where a base class can be used without altering desirable properties of the program. It is applied by using "is a" relationships in OO designs.

3) The means of implementing "is a" relationships in C++ is class inheritence (usually, but not always, public inheritence);

4) There are common use-cases in C++ in which a derived class cannot be destroyed without yielding undefined behaviour unless the base class has a virtual destructor. For example;

    Base *b = new Derived;

    delete b;     // undefined behaviour here

Such use cases therefore potentially yield incorrect behaviour if a base class has no virtual destructor. This compromises correctness of the program which uses those classes.

5) This yields a guideline that, if a C++ class is intended for derivation, it must have a virtual destructor.

6) A similar logic train can also be used to argue that a C++ class intended for derivation must also have virtual member functions. Essentially, a Derived object can not be substituted in place of a Base object and still result in correct program behaviour unless the base class has virtual member functions (the only exception to this case is trivial: the Derived class does not override any behaviour of the Base class).

7) std::vector, like most of the STL classes, does not have any virtual member functions.

grumpy: thanks for your advice. i still disagree on the point about undefined behavior with what i was doing. i have not actually read iso 14882 to see if it is defined, but it seems that multiple compilers gave the behavior, that while confusing to some, was exactly what i expected.

i have decided that i should not limit my vector math to only std::vector, and generalized it for any iterator. i have been stuck in a c#/java mindset for a while now and just was not thinking in c++ when i started the ray tracer. obviously generalizing my vector math in such a way has eliminated the need to derive from std::vector.

excellent advice in the last code block in post #4. thanks again. here is what i have now:

#include <iterator>

#include <stdexcept>

#include <numeric>

#include <cmath>

#include <functional>

#include <algorithm>



namespace trace

{

  template< typename InIter, typename T >

  T length(InIter first, InIter last)

  {

    return std::inner_product< InIter, InIter, T >(first, last, first, 0);

  }

  

  template< typename InIter, typename T >

  T magnitude(InIter first, InIter last)

  {

    return std::sqrt(length< InIter, T >(first, last));

  }

  

  template< typename InIter, typename OutIter, typename T >

  OutIter normalize(InIter first, InIter last, OutIter result)

  {

    return std::transform(first, last, result, std::bind2nd(std::divides< T >(), magnitude< InIter, T >(first, last)));

  }

  

  template< typename InIter1, typename InIter2, typename T >

  T dot_product(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2)

  {

    if (std::distance< InIter1 >(first1, last1) != std::distance< InIter2 >(first2, last2))

      throw std::domain_error("std::distance(first1, last1) != std::distance(first2, last2)");

    return std::inner_product< InIter1, InIter2, T >(first1, last1, first2, 0);

  }

}

i have examined the boost library and decided to design my library similarly so as to avoid the initial question in this post about liking template code. thanks for all the help.

one more thing: i am finding that i have to specify where i am calling which template to generate so as to not get any casting weirdness. is there a way to alias some of my methods:

trace::dot_product< std::vector< double >::iterator, std::vector< double >::iterator, double >

aliased as:

dot_product3d

Typedef

typedef trace::dot_product< std::vector< double >::iterator, std::vector< double >::iterator, double > dot_product3d;

Quote:

Originally Posted by jubitzu (Post 124826)

i still disagree on the point about undefined behavior with what i was doing. i have not actually read iso 14882 to see if it is defined, but it seems that multiple compilers gave the behavior, that while confusing to some, was exactly what i expected.

<sigh>

The C++ standard, Section 5.3.5 para 3 specifies;

Quote:

Originally Posted by ISO/IEC 14882

In the first alternative (delete object), if the static type of the operand is different from its dynamic type, the static type shall be a base class of the operand�s dynamic type and the static type shall have a virtual destructor or the behavior is undefined. In the second alternative (delete array) if the dynamic type of the object to be deleted differs from its static type, the behavior is undefined.

The fact that some compilers give you the behaviour you expect is irrelevant, whether that behaviour is logical or not. There is no guarantee that any other compiler (including future versions of the compilers you have tested) will do so.

The C++ standard constrains (or explicitly does not constrain, in the case of undefined behaviour) what a compiler is allowed to do. Much as some vendors would prefer to believe otherwise, the behaviour of compilers does not define what the standard says.

Game Ender: that wont work because it is not defining a type for that function. a typedef can certainly be used to define a pointer to that function, but not the way you did it. i guess i will just #define it even though i dont like doing things that way.

Grumpy: you were of course correct all along. i guess it just isnt enough for me to trust someone who says that there is undefined behavior unless they can show me exactly where that undefined behavior is defined. and when i said last time that i had not read iso/iec 14882, i in fact had read chapter 10 in its entirety, and although it seemed clear that it is not a great idea to do what i was doing, I found nothing referring to undefined behavior in the chapter.

i would think that if that behavior of deleting a dynamic type with a pointer to a static type that does not have a virtual destructor were undefined, then it would be inherently undefined for many more cases.