Back to General and Gameplay Programming

c++ template question

General and Gameplay Programming Programming

Started by Volte6 March 16, 2005 05:18 PM

17 comments, last by Polymorphic OOP 19 years, 1 month ago

Volte6

106

Author

March 16, 2005 05:18 PM

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.

Agony

3,452

March 16, 2005 05:31 PM

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.

"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas only, and not for things themselves." - John Locke

technomancer

199

March 16, 2005 05:36 PM

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.

darookie

1,441

March 16, 2005 05:39 PM

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 operatortemplate<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 functiontemplate<class Match> C *DoublyLinkedList::findElement( Match isMatch ){  C *pNow = pFirst;  while ( pNow )  {    if ( isMatch(pNow) ) {      return pNow;    }    pNow = pNow->pNext;  }  return NULL;}// usage samplelist.findElement( MatchNameAndWidth ("name", 100 ) );

Telastyn

3,778

March 16, 2005 05:50 PM

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 :]

-- Tangent Developer Journal - Delegates - Part 2

Volte6

106

Author

March 16, 2005 05:55 PM

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.

Agony

3,452

March 16, 2005 06:26 PM

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.

"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas only, and not for things themselves." - John Locke

MaulingMonkey

1,729

March 16, 2005 11:36 PM

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"] = &person1std::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]

Volte6

106

Author

March 17, 2005 11:55 AM

Thanks for all the terrific info. You guys rock.

Volte6

106

Author

March 17, 2005 03:35 PM

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.

c++ template question

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

c++ template question

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines