I did manage to get SDL 1.2 working on OSX using XCode4 following many of the great guides out there.

Now I've written a basic "Map" template class that will be used as the basis for my dungeon-generation stuff. It's nothing terribly fancy; mainly just a template around a std::vector and some accessors for accessing locations in the array using x,y coordinates.

However, I'm getting some linker errors when I try to create an instance of my class in my main.cpp; I'm not sure why it's unable to resolve the symbols and am wondering if it might have something to do with SDL's macro magic.

Code here:

Map.h

#ifndef __DungeonSoft__Map__
#define __DungeonSoft__Map__

#include <iostream>
#include <vector>

#include "monads.h"

typedef std::pair<int, int> point; // x, y

template <typename T>
class Map {
    std::vector<T> map;

public:
    const int width;
    const int height;

    Map();
    Map(int w, int h);
    Map<T> operator=(const Map<T>& other);
    ~Map();
    
    int getWidth() { return width; };
    int getHeight() { return height; };
    T get(int x, int y) const;
    void set(int x, int y, T val);
    std::vector<std::pair<point, Maybe<T>>> neighbours(int x, int y) const;
};

#endif /* defined(__DungeonSoft__Map__) */

Map.cpp

#include "Map.h"


template <class T>
Map<T>::Map() : width(0), height(0)
{
}

template <class T>
Map<T>::Map(int w, int h) : width(w), height(h)
{
    map.reserve(width * height);
    for (typename std::vector<T>::iterator it = map.begin(); it != map.end(); ++it) {
        *it = T();
    }
}

template <class T>
Map<T> Map<T>::operator=(const Map<T>& other)
{
    map.clear();
    map.reserve(other.width * other.height);
    for (typename std::vector<T>::iterator it = other.map.begin(); it != other.map.end(); ++it) {
        map[it] = *it;
    }
}

template <class T>
Map<T>::~Map<T>()
{
    map.clear();
}

template <class T>
T Map<T>::get(int x, int y) const
{
    return map[y * width + x];
}

template <class T>
void Map<T>::set(int x, int y, T val)
{
    map[y * width + x] = val;
}

template <class T>
std::vector<std::pair<point, Maybe<T>>> Map<T>::neighbours(int x, int y) const
{
    typedef std::pair<point, Maybe<T>> neighbour;

    point coords[8] = {
        point(-1, -1),
        point(0, -1),
        point(1, -1),
        point(-1, 0),
        point(1, 0),
        point(-1, 1),
        point(0, 1),
        point(1, 1)
    };
    
    std::vector<neighbour> ns;
    for (int i = 0; i <= sizeof(point) * 8; ++i) {
        int x_off = x + coords[i].first;
        int y_off = y + coords[i].second;

        try
        {
            ns.push_back(neighbour(point(x_off, y_off), Maybe<T>(map[y_off * width + x_off])));
        } catch (std::out_of_range& err) {
            ns.push_back(neighbour(point(-1, -1), Maybe<T>()));
        }
    }
    return ns;
}

and the monad.h utility header:

/*
 * Minimal C++ implementation of Functor, Monad and Maybe.
 *
 * Requires c++0x variadic templates and lambda expressions:
 * 
 *      g++ -std=c++0x main.cpp -o main
 *
 * fmap, monadic bind and return implementations for std::vector
 * and Maybe.
 *
 * Copyright 2012 James Brotchie <brotchie@gmail.com>
 *  https://github.com/brotchie/
 *  @brotchie
 *
 */

#ifndef __DungeonSoft__monads__
#define __DungeonSoft__monads__

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

/* Functor */
template <template <typename...> class F>
struct Functor {
    template <typename A, typename B>
    static function <F<B>(F<A>)> fmap(function <B(A)>);
};

template <template <typename...> class F, typename A, typename B>
static function <F<B>(F<A>)> fmap(function <B(A)> f) {
    return Functor<F>::fmap(f);
}

template <template <typename...> class F, typename A, typename B>
static F<B> fmap_(function <B(A)> f, F<A> v) {
    return Functor<F>::fmap(f)(v);
}

template <template <typename...> class F, typename A, typename B>
static F<B> operator %(function <B(A)> f, F<A> v) {
    return Functor<F>::fmap(f)(v);
}

/* Monad */
template <template <typename...> class F>
struct Monad {
    template <typename A>
    static F<A> return_(A);

    template <typename A, typename B>
    static F<B> bind(F<A>, function<F<B>(A)>);
};

template <template <typename...> class F, typename A, typename B>
static F<B> bind(F<A> m, function<F<B>(A)> f) {
    return Monad<F>::bind(m, f);
}

template <template <typename...> class F, typename A>
static F<A> return_(A a) {
    return Monad<F>::return_(a);
}

template <template <typename...> class F, typename A, typename B>
static F<B> operator >=(F<A> m, function<F<B>(A)> f) {
    return Monad<F>::bind(m, f);
}

template <template <typename...> class F, typename A, typename B>
static F<B> operator >>(F<A> a, F<B> b) {
    function<F<B>(A)> f = [b](A){ return b; };
    return a >= f;
}

/* Maybe */
template <typename T>
class Maybe {
public:
    Maybe() : _empty(true){};
    explicit Maybe(T value) : _empty(false), _value(value){};

    T fromJust() const {
        if (isJust()) {
            return _value;
        } else {
            throw "Cannot get value from Nothing";
        }
    }

    bool isJust() const { return !_empty; }
    bool isNothing() const { return _empty; }

    static bool isJust(Maybe &m) { return m.isJust(); }
    static bool isNothing(Maybe &m) { return m.isNothing(); }
private:
    bool _empty;
    T _value;
};

template <typename T>
ostream& operator<<(ostream& s, const Maybe<T> m)
{
    if (m.isJust()) {
        return s << "Just " << m.fromJust();
    } else {
        return s << "Nothing";
    }
}

/* Functor Maybe */
template <>
struct Functor<Maybe> {
    template <typename A, typename B>
    static function <Maybe<B>(Maybe<A>)> fmap(function <B(A)> f) {
        return [f](Maybe<A> m) -> Maybe<B> {
            if (m.isNothing()) {
                return Maybe<B>();
            } else {
                return Maybe<B>(f(m.fromJust()));
            }
        };
    };
};

/* Monad Maybe */
template <>
struct Monad<Maybe> {
    template <typename A>
    static Maybe<A> return_(A v){
        return Maybe<A>(v);
    }

    template <typename A, typename B>
    static Maybe<B> bind(Maybe<A> m, function<Maybe<B>(A)> f){
        if (m.isNothing()){
            return Maybe<B>();
        } else {
            return f(m.fromJust());    
        }
    }
};

/* Functor vector */
template <>
struct Functor<vector> {
    template <typename A, typename B>
    static function <vector<B>(vector<A>)> fmap(function <B(A)> f) {
        return [f](vector<A> v){
            vector<B> result;
            transform(v.begin(), v.end(), back_inserter(result), f);
            return result;
        };
    }
};

/* Monad vector */
template <>
struct Monad<vector> {
    template <typename A>
    static vector<A> return_(A v){
        return vector<A>{v};
    }

    template <typename A, typename B>
    static vector<B> bind(vector<A> m, function<vector<B>(A)> f){
        vector<B> v;
        for_each(m.begin(), m.end(), [f, &v](A a){
            vector<B> result = f(a);
            copy(result.begin(), result.end(), back_inserter(v));
        });
        return v;
    }
};

template <typename A, typename B, typename C>
static function<C(A)> compose(function<B(A)> f1, function<C(B)> f2) {
    return [f1,f2](A v) -> C {
        return f2(f1(v));
    };
}

#endif /* defined(__DungeonSoft__monads__) */

and finally, my main.cpp

#include <SDL/SDL.h>
#include "SDLMain.h"

#include "Map.h"

const int WINDOW_WIDTH = 300;
const int WINDOW_HEIGHT = WINDOW_WIDTH / 16 * 9;
const int SCALE = 3;


int main(int argc, char *argv[])
{
    SDL_Init(SDL_INIT_EVERYTHING);
    
    Map<int> map = Map<int>(10, 10);
    for (int y = 0; y <= map.getHeight(); ++y) {
        for (int x = 0; x <= map.getWidth(); ++x) {
            std::cout << map.get(x, y);
        }
        std::cout << std::endl;
    }

    SDL_Surface *screen = SDL_SetVideoMode(WINDOW_WIDTH * SCALE, WINDOW_HEIGHT * SCALE, 32, SDL_DOUBLEBUF);
    SDL_WM_SetCaption("DungeonSoft Presents: The Song of Wolves", "icon.ico");
    
    bool isRunning = true;
    SDL_Event event;
    while(isRunning) {
        SDL_FillRect(screen, NULL, SDL_MapRGB(screen->format, 0, 0, 0));
        while (SDL_PollEvent(&event)) {
            switch (event.type) {
                case SDL_QUIT:
                    isRunning = false;
                    break;
                    
                case SDL_KEYDOWN:
                    switch (event.key.keysym.sym) {
                        case SDLK_ESCAPE:
                            isRunning = false;
                            break;
                            
                        default:
                            break;
                    }
                    break;
                    
                case SDL_VIDEOEXPOSE:
                    SDL_Flip(screen);
                    break;
                    
                default:
                    break;
            }
            SDL_Flip(screen);
        }
    }

    SDL_Quit();
    return 0;
}

The error I'm getting is:

Undefined symbols for architecture x86_64:
  "Map<int>::Map(int, int)", referenced from:
      _SDL_main in main.o
  "Map<int>::~Map()", referenced from:
      _SDL_main in main.o
  "Map<int>::get(int, int) const", referenced from:
      _SDL_main in main.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)

Do I just have the signature wrong on the ctor or something?

A template is a pattern, not a function or class. A template's definition must be known at the time of instantiation in order for the compiler to generate the code for the specific types needed. Read 35.12, 35.13, and 35.15 of the C++ FAQ Lite.

template <class T>
Map<T>::Map(int w, int h) : width(w), height(h)
{
    map.reserve(width * height);
    for (typename std::vector<T>::iterator it = map.begin(); it != map.end(); ++it) {
        *it = T();
    }
}
 

Are you referring to this ctor? I certainly thought this didn't look right. Not sure what a default value would be here, but commenting it out doesn't resolve the linker issue unfortunately. What would you put here instead? The idea I was going for is that the Map container shouldn't care much about what the user is using for the values at the coordinates in the map; since I will be using several generation algorithms some will use different specialized Cell object types for various purposes..

Ah yes, I think I understand now -- thanks for the links (and subsequently Boost makes a whole lot more sense now)

It certainly has solved my issue.

Now to hunt down the off-by-ones and uninitialized values...

Are you referring to this ctor?

No. I'm referring to your separation of Map in a header and source file. (Though, that constructor isn't quite right. std::vector::reserve allocates the memory for width*height Ts, but does not construct those Ts. On the other hand, using std::resize will create (default-construct) width*height Ts in map, which I assume is what you meant to do.)

Each cpp file is compiled independently of each other. When main.cpp is compiled, it knows of Map and its member function prototypes. When the compiler reaches Map<T>::Map(int,int) with T=int, the constructor definition isn't known to main.cpp for T=int, so the compiler continues on, leaving the definition up to the linker to resolve. Next, Map.cpp is compiled, it only includes Map.h, and doesn't export any classes, since it doesn't know what Ts to use for Map. Both source files compile successfully, and the linker steps in. main.cpp is looking for a Map<T>::Map(int,int) with T=int, and since Map.cpp didn't generate that specific constructor, an "undefined reference" error ("unresolved external symbol" in Visual Studio).

So, how do we get the a Map with T=int?
The FAQs I linked the in the previous post outlines several solution:

1. Keep the definition in the header:

// Foobar.h
#include <lots_of_dependencies>

template<class T>
class Foobar {
public:
    void frobnicate() {
        // ...
    }
};

Straight forward approach, though the definitions can clutter the header (style-issue/personal preference).


2. Move the definitions in a separate file (but include it in the header):

// Foobar.h

template<class T>
class Foobar {
    void frobnicate();
};

#include "Foobar.impl"

// Foobar.impl
#include <lots_of_dependencies>

template<class T>
void Foobar<T>::frobnicate() {
    // ...
}

Same as 1, though the definitions have been moved to another file. (Again, style-issue/personal preference.)


3. Separate the interface from the implementation, and export common types in a source file:

// Foobar.h
template<class T>
class Foobar {
    void frobnicate();
};

// Foobar.impl
#include <lots_of_dependencies>

template<class T>
void Foobar<T>::frobnicate() {
    // ...
}

// Foobar.cpp
#include "Foobar.h"
#include "Foobar.impl"

// Explicitly create Foobars for Ts in (int, double):
template class Foobar<int>;
template class Foobar<double>;

This approach keeps a strict separation between interface and implementation, and minimizes the dependencies Foobar requires on those that use it. This approach is a bit constricted, since the Foobar.cpp needs to be maintained for all Ts of Foobar that is used in the project. It does decouple lots_of_dependencies from those that include it, though.

Thanks for the extensive response. I'm working my way through the links you posted and will be reading up more from my C++ reference books.