• Advertisement
Sign in to follow this  

c++ template question

This topic is 4725 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

While writing a lot of linked lists into my code, I found that using a template was helpful ( I am deliberately avoiding std:vector, std:list etc ). However I've come across a certain difficulty... I want to search the list, which will be a custom field based on the class i use with the template. Here it is:
template <class C>
class DoublyLinkedList
{
public:
  C *pFirst, *pFinal;

  DoublyLinkedList();
  ~DoublyLinkedList();

  C *addElement( C *pElement );
  C *findElement( const char* name );
  void remElement( C *pNow );
};

// CONSTRUCTOR
template <class C>
DoublyLinkedList<C>::DoublyLinkedList() {
  pFirst = NULL;
  pFinal = NULL;
};

template <class C>
DoublyLinkedList<C>::~DoublyLinkedList(){;};

template <class C>
C *DoublyLinkedList<C>::addElement( C *pElement )
{
  C *pNow = pFinal;

  if ( !pFirst ) {
    pFirst = pElement;
  }
  else if ( !pFinal ) { // There is a pFirst though!
    pFinal = pElement;
    pFirst->pNext = pFinal;
  }
  else {
    pFinal->pNext   = pElement;
    pElement->pPrev = pFinal;
    pFinal          = pElement;
  }
  return pElement;
};

template <class C>
C *DoublyLinkedList<C>::findElement( const char* filename )
{
  C *pNow = pFirst;
  while ( pNow )
  {
    if ( strcmp( pNow->filename, filename ) == 0 ) {
      return pNow;
    }
    pNow = pNow->pNext;
  }
  return NULL;
}

template <class C>
void DoublyLinkedList<C>::remElement( C *pNow )
{
  C *pTemp = NULL;

  if ( !pNow )
    return false;

  pTemp = pNow;

  if ( pNow == pFirst )
  {
    if ( pNow->pNext ) {
      pFirst = pNow->pNext;
      pFirst->pPrev = NULL;
    }
    else {
      pFirst = NULL;
      pFinal = NULL;
    }
  }
  else if ( pNow == pFinal )
  {
    if ( pNow->pPrev ) {
      pFinal = pNow->pPrev;
      pFinal->pNext = NULL;
    }
    else {
      pFinal = NULL;
      pFirst = NULL;
    }
  }
  else
  {
    pNow->pPrev->pNext = pNow->pNext;
    pNow->pNext->pPrev = pNow->pPrev;
  }
  delete pNow;
};
At the moment I have a findElement() which finds by filename ( for a gfx surface list ). That actually functions exactly as I'd like... but if possible I would like to make the findElement() method far more generic, much like the template itself. I can't figure how to do this... but is there a way I could set it up to do something like:

DoublyLinkedList<GfxSurface> myList;
GfxSurface *foundSurface = myList.findElement("width", 100);

This way I could tell it to search the width value of the elements for 100.

Share this post


Link to post
Share on other sites
Advertisement
Well, if you're not going to use the STL, then you could at least take a look at their functions to find out how they do it. (Or look up predicates in the context of template programming.)

Though I have to ask, why do you wish to avoid the STL? There are some good reasons to do so, but there are definitely some not so good ones as well. And if you're going to end up using pretty much the same method that the STL uses, then you likely might as well use the STL itself, unless you're merely learning. Even in that case, though, I suggest that you at least take a look at some code from some implementation of the STL.

Share this post


Link to post
Share on other sites
Agony has a point, i wouldn't waste my time writing a linked list template functions when STL offers these like, list, slist and vectors. May i ask why your delibratley not using STL ? if you are doing it for experience then fair enough but the STL linked list code is going to be alot more robust and probably faster than anything you can write yourself.

Share this post


Link to post
Share on other sites
Instead of discussing the in's-and-out's of using the STL, I'll try to answer the actual question [wink].

Just provide an additional parameter for findElement that will represent a comparison-function:



// Matching operator
template<class T>
class MatchNameAndWidth {
int width;
const char * filename;
public:
// constructor
MatchNameAndWidth(const char * name, int w) : filename(name), width(w)
{
}

// match against name and width
bool operator (const T* v) {
return !strcmp(v->filename, filename) && v->width == width;
}
};

// add an additional template for the matching function
template<class Match> C *DoublyLinkedList::findElement( Match isMatch )
{

C *pNow = pFirst;

while ( pNow )
{
if ( isMatch(pNow) ) {
return pNow;
}

pNow = pNow->pNext;
}

return NULL;
}

// usage sample
list.findElement( MatchNameAndWidth ("name", 100 ) );




Share this post


Link to post
Share on other sites
Slightly offtopic:

Agony: What are the good reasons to avoid the STL? Far too often I hear people blindly promote it, and not any of the other side. PM perhaps if this thread gets back to the question at hand.

Slightly more on topic:

Darookie: Doesn't the template declaration for MatchNameandWidth go before the operator overload, not the class?

I'm just learning templates now, and am trying to pay more attention to others' examples and designs here :]

Share this post


Link to post
Share on other sites
The primary reason I'm avoid std is because i'm trying to actually learn, and at first I did linked lists, which was good experience on how those work ( and helped familiarize myself with pointers ). Now I'm at the point I want to simplify that ( having learned it ), and while I'm aware of pre-designed templates, I want to know how to do it myself so that I can apply the experience to future needs.

I have no criticism of the STL though.

darookie:

I would 'like' to be able to access an arbitrary property of the object and compare against an arbitrary value. I'm guessing this is probably not doable in C++.

In PHP I could build a variable and access it such as:


<?php

$person1 = "Dylan";

$i=1;
$customVar = "person".$i;
echo( ${$customVar} );

// Result:
// Dylan
?>

Is there a similar technique in c++? In Foxpro they have something called Macro Substitution which does that as well.

Share this post


Link to post
Share on other sites
Nope, C++ wasn't designed to be quite that powerful and flexible with its runtime type information. I know plenty of other languages have such features, but they're not necessarily things you want to rely on heavily, as they are slower. These features are really useful in many situations, but you don't want to be looking up a type's member by name every single time you use it in loops throughout your program (such as in a find() method). C++'s templates, with the aid of predicates, manages all this at compile time, making it significantly faster at runtime, as it becomes merely a straight-up function call, rather than some virtual function calls and string comparisons, which finally lead to the real function call. Plus, it can even be inlined if you desire, potentially making it even faster.

Secondly, your requested method, that of being able to find an element based on a particular field, is still not nearly as flexible as merely using a predicate function. A comparison is often not as simple as comparing a single field for equality with a value. With a predicate function, you can write it to do whatever comparison you want, regardless of how complex or unusual it might be.

As for why I didn't give more information, well, that's primarily because I don't know enough about the topic to describe it thoroughly, though I do understand it enough to use it myself. But since there were 29 views and no responses, I figured I'd suggest directing you towards some STL code to get an idea of how to do it, since that's pretty much how I figured it out as well.

As for reasons why not to use the STL, I partially threw that comment in there to avoid upsetting anyone who might actually have good reasons, but the best reason I know of is when someone is learning. There may indeed be particular cases where someone could benefit by writing their own container or whatnot for a very specific purpose, but it's probably pretty rare, and I would expect this person to be intimately familiar with the STL, and know precisely why they're using something else. As for details, I wouldn't be able to give any, because the cases where I'd understand avoiding the STL are likely to be very specific cases, and I can't think of any offhand, as I've never personally had any of these that I can remember. Many of the reasons given might simply be due to limited knowledge of the STL, such as not realizing that you can write your own allocators for memory management. So anyway, like I said, I largely said that there are good reasons in order to cover the learning scenario, and to avoid upsetting anyone.

Share this post


Link to post
Share on other sites
Quote:
Original post by Volte6
<?php

$person1 = "Dylan";

$i=1;
$customVar = "person".$i;
echo( ${$customVar} );

// Result:
// Dylan
?>


Is there a similar technique in c++? In Foxpro they have something called Macro Substitution which does that as well.


Sort of, but not quite. Here's the closest (simple) equivilant I can think of:

std::map< std::string , std::string > vars;
vars["person1"] = "Dylan";


vars["i"] = "1";
//alternative(s):
//= boost::lexical_cast< std::string >( 1 );

vars["customVar"] = std::string( "person" ) + vars["i"];
//alternative(s):
//= boost::str( boost::format("person%1%") % vars["i"] );
//= boost::str( boost::format("person%1%") % 1 );
//= std::string( "person" ) + boost::lexical_cast< std::string >( 1 )

std::cout << vars[ vars["customVar"] ];


That is, you can't directly access the named variables of C++, but you can create a layer of indirection that will achieve the same effect. Managing this kind of thing can get hairy with complex types (read: custom classes with submembers to access). If you want to get into that I might suggest looking into boost::any. Note my ample use of the boost library in my alternatives examples - it's a wonderful library that is worth looking into :).

Also, to provide a poor example alternative, to explain some how you can add this effect after the fact:

std::string person1 = "Dylan";

std::map< std::string , std::string * > vars;
vars["person1"] = &person1;

std::string customVar = "person"; customVar += "1";
assert( vars[ customVar ] );
std::cout << *vars[ customVar ];


Note: the reason there's only one vars[...] statement in this example is because "customVar" is an actual variable instead of a string to be used to access the vars[] array. If you were werid, you could replace the last 2 lines with:

std::string customVar = "person"; customVar += "1";
vars[ "customVar" ] = &customVar;
assert( vars[ "customVar" ] );
assert( vars[ *vars[ "customVar" ] ] );
std::cout << *vars[ *vars[ "customVar" ] ];

[Edited by - MaulingMonkey on March 17, 2005 12:36:11 AM]

Share this post


Link to post
Share on other sites
Interesting related question:

I thought I would phase out the sprite list, and a sprite list manager ( AKA sprite list list ).

So at first I thought:

class SpriteManager {
LinkedList< LinkedList<Sprite>> listList;
};

Which in my head sounds like a list of lists... but it doesn't work that way for whatever reason ( Apparently templates are more like macros... they aren't real code ).

Then I got an idea:

typedef LinkedList<Sprite> SpriteList;

class SpriteManager {
LinkedList<SpriteList> listList;
};

And that compiles... does it look right to you? I define a NEW type "SpriteList" which is just a linked list of sprites.
Then I create a linked list of that new type.

Share this post


Link to post
Share on other sites
Quote:
Original post by Volte6
Interesting related question:

I thought I would phase out the sprite list, and a sprite list manager ( AKA sprite list list ).

So at first I thought:

class SpriteManager {
LinkedList< LinkedList<Sprite>> listList;
};

Which in my head sounds like a list of lists... but it doesn't work that way for whatever reason ( Apparently templates are more like macros... they aren't real code ).

Then I got an idea:

typedef LinkedList<Sprite> SpriteList;

class SpriteManager {
LinkedList<SpriteList> listList;
};

And that compiles... does it look right to you? I define a NEW type "SpriteList" which is just a linked list of sprites.
Then I create a linked list of that new type.


They are real code, and not at all like macros other than that they expand. Your original code will work, you have just encountered one of C++'s odd parsing errors. You need a space between your >>, otherwise the compiler thinks you have a right bit-shift.

class SpriteManager {
LinkedList< LinkedList<Sprite> > listList;
};

will work fine, although the typedef is much nicer.

Share this post


Link to post
Share on other sites
Okay so that worked... great! Any Snafu's i should be aware of?

Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.

Additionally, How does my typedef version compare to the single line version? Is there anything I should know about typedef?

Sorry, doing this whole self education thing leaves one with many questions :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Volte6
Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.
Compile time (unlike Java.NET generics, which are expanded at runtime). The main difference is that templates allow for recursion, are type-checked by the compiler, and are part of the language, and not an add-on like the preprocessor.

Templates exist mainly to avoid some of the problems of macros, but macros can do things that templates can't - and the combination of template metaprogramming and preprocessor metaprogramming is incredibly powerful.

Quote:
Original post by Volte6
Additionally, How does my typedef version compare to the single line version? Is there anything I should know about typedef?
The typedef version avoids the parsing issue that mfawcett mentioned. When nesting templates (such as vector< vector<int> > The space in the > > is extremely important. Typedes can help avoid little gotchas like this.

Template code has a lot of gotchas. Look at the boost code to see how much effort is put into getting templates to work across multiple compilers. Boost also is a good place to look for ideas on how to push C++ to the very edge of its capability - many of the people involved in Boost are writing the specs for the next revision of C++.

Share this post


Link to post
Share on other sites
Quote:
Original post by jdhardy
Quote:
Original post by Volte6
Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.
Compile time (unlike Java.NET generics, which are expanded at runtime). The main difference is that templates allow for recursion, are type-checked by the compiler, and are part of the language, and not an add-on like the preprocessor.

Templates exist mainly to avoid some of the problems of macros, but macros can do things that templates can't - and the combination of template metaprogramming and preprocessor metaprogramming is incredibly powerful.


Yes, yes it is. I feel compelled to share something I put together recently (based on something Fruny provided to me in the channel, which in turn comes from the Boost mailing list or something like that):

// introspect.h -- deep magic that I *mostly* understand.
// Remove the spaces after backslashes if you use this.

#ifndef INTROSPECT_H
#define INTROSPECT_H
typedef char (&n)[1];
typedef char (&y)[2];

template< bool condition, typename T> struct enable_if {};
template< typename T > struct enable_if<true,T> { typedef T type; };

#define INTROSPECT_IMPL(id, ret, func, cflag, ...) \
template< typename T, ret (T::*)(__VA_ARGS__) cflag> struct has_##id##_pfn {}; \
template< typename T > n has_##id##_x(...); \
template< typename T > y has_##id##_x(int, has_##id##_pfn<T, &T::func >* p = 0); \
template< typename T > struct has_##id { \
enum { value = sizeof(has_##id##_x<T>(0)) == sizeof(y) }; \
}

#define INTROSPECT(id, ret, func, ...) INTROSPECT_IMPL(id, ret, func,, __VA_ARGS__)
#define INTROSPECT_CONST(id, ret, func, ...) INTROSPECT_IMPL(id, ret, func, const, __VA_ARGS__)

#define WHEN_AVAILABLE(id, ret) \
template<typename T> typename enable_if<has_##id<T>::value,ret>::type

#define WHEN_UNAVAILABLE(id, ret) \
template<typename T> typename enable_if<!has_##id<T>::value,ret>::type

#define WHEN_AVAILABLE_INLINE(id, ret) \
template<typename T> inline typename enable_if<has_##id<T>::value,ret>::type

#define WHEN_UNAVAILABLE_INLINE(id, ret) \
template<typename T> inline typename enable_if<!has_##id<T>::value,ret>::type
#endif



// A usage example:

#include <algorithm>
#include <vector>
#include <complex>
#include "introspect.h"

// This was the nicest interface I could acheive - the first parameter for the
// INTROSPECT (or INTROSPECT_CONST) macro is a "cookie" which is associated with
// the particular introspection we are doing. In this case, symbol "foo" is
// associated with objects which provide the member function "void swap(T)",
// where T is the object type (you don't get to change this or specify extra
// template parameters unfortunately). The other parameters are of course the
// return type, function name (it also works with operators), and argument list
// (you can specify 'const's and '&'s and so on in there too). INTROSPECT_CONST
// is the same except it looks for const member functions instead.

INTROSPECT(foo, void, swap, T);

// For objects that provide the member function associated with "foo", this
// version of fast_swap is instantiated, and declared inline. It is again
// templated on T, and returns void (the second parameter to
// WHEN_AVAIABLE_INLINE).
WHEN_AVAILABLE_INLINE(foo, void) fast_swap(T& a, T& b) {
a.swap(b);
}

// For other types, this other version is instantiated. Thus fast_swap will
// call an object's own swap() method if it exists, but otherwise default to
// std::swap.
WHEN_UNAVAILABLE_INLINE(foo, void) fast_swap(T& a, T& b) {
::std::swap<T>(a,b);
}

// I also provided plain WHEN_AVAILABLE and WHEN_UNAVAILABLE macros which do
// not declare the function inline. The problem is that "inline" has to come
// before the return type, but the return type has to be specified in the macro.

// Test cases. This is as in the original sample; I suppose it would be more
// dramatic to actually initialize some values and output them...
int main() {
std::vector<int> vector1, vector2;
std::complex<int> complex1, complex2;
double a,b;

fast_swap(vector1, vector2);
fast_swap(complex1, complex2);
fast_swap(a,b);
}



Tested/developed with DJGPP (GXX 3.43).

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by jdhardy
Quote:
Original post by Volte6
Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.
Compile time (unlike Java.NET generics, which are expanded at runtime). The main difference is that templates allow for recursion, are type-checked by the compiler, and are part of the language, and not an add-on like the preprocessor.

Templates exist mainly to avoid some of the problems of macros, but macros can do things that templates can't - and the combination of template metaprogramming and preprocessor metaprogramming is incredibly powerful.


Yes, yes it is. I feel compelled to share something I put together recently (based on something Fruny provided to me in the channel, which in turn comes from the Boost mailing list or something like that):

// introspect.h -- deep magic that I *mostly* understand.
// Remove the spaces after backslashes if you use this.
*** Source Snippet Removed ***

// A usage example:
*** Source Snippet Removed ***

Tested/developed with DJGPP (GXX 3.43).
Nifty. It looks like it allows the choice of operation based on what's available.

Here's mine, minus a lot of extra scaffolding:

//This is valid C++ code!
CREATE(Employees,
((SIN AS int))
((Name AS string))
)

CREATE(Tasks,
((Employee_SIN AS int))
((Name AS string))
)

cout<<SELECT( (Employees::SIN)(Employees::Name)(Tasks::Name)
FROM (Employees)(Tasks)
WHERE Employees::SIN() == Tasks::Employee_SIN()
)<<endl<<endl;

It's part of a relational database engine with the query optimizer implemented at compile-time. Right now it's just a naive join (cross product followed by a selection), but I hope to add some smarts to it.

Without Boost.MPL and Boost.Preprocessor, this wouldn't even be close to possible.

Share this post


Link to post
Share on other sites
Quote:
Original post by Volte6
Okay so that worked... great! Any Snafu's i should be aware of?

Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.

Additionally, How does my typedef version compare to the single line version? Is there anything I should know about typedef?

Sorry, doing this whole self education thing leaves one with many questions :)

They do expand at compile time. That is a HUGE difference from macros which are expanded during preprocessing (i.e. when type information is not present).

Share this post


Link to post
Share on other sites
Quote:
Original post by jdhardy
Nifty. It looks like it allows the choice of operation based on what's available.


Yup, that's exactly what it does. You write a 'wrapper' function template which check if a class provides an 'optimized' operation (like container::swap vs. std::swap or std::list::sort vs. std::sort) and if so, transparently use it, or default to the 'general but slow' version.

Kudos to Zahlman for doing what I didn't quite feel up to: wrapping it all up in macros. One comment though: Boost's MPL already provides enable_if and types for true/false values.

Quote:
Also, These are expanded at run time or compile time? That's why I thought they were like macros.. I thought they were expanded at compile time.


Macros know nothing about your program. They are pure text substitutions. One huge consequence is that macros do not respect scope - templates do.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by jdhardy
Nifty. It looks like it allows the choice of operation based on what's available.


Yup, that's exactly what it does. You write a 'wrapper' function template which check if a class provides an 'optimized' operation (like container::swap vs. std::swap or std::list::sort vs. std::sort) and if so, transparently use it, or default to the 'general but slow' version.
While this is probably a bad example, what does this get you that regular template specialization/function overloading doesn't? One could overload std::swap for the std:: containers (which I imagine they do), but this just may be a case of bad example. [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
One comment though: Boost's MPL already provides enable_if and types for true/false values.

Just noting that enable_if, lazy_enable_if, and the associated disablers aren't in MPL, they're in Boost.Utility.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement