Jump to content
  • Advertisement
Sign in to follow this  
Sion Sheevok

[C++] Multiple Template-Parameter Partial Template-Specialization

This topic is 3318 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

I can't find any better way to term it than that. ^^ I'm making a few data structures for my own use and I'm running into a few things. Just as an example, I have a templated Dictionary/Map data structure. The template parameters are KeyType and ValueType. This data structure has a binary search tree to store node containing keys and values. Because this is a binary search tree, it needs to compare the keys to insert them appropriately. This is the issue: >, <, ==, >=, <=, !=. All theses operators will not have a consistent or appropriate effect with character-strings. The solution I've heard is partial template specialization so I can explicitly write the templated method that will be used for said template parameter. However, in my situation, I have two template parameters. I can't seem to find a way to get the compiler to understand that I'm manually writing the templated method that it can then template for different ValueTypes.
template<typename KeyType, typename ValueType>
class MultiDictionary
{
    // ...
    void Add(KeyType Key, ValueType Value);
    // ...
}

template<typename KeyType, typename ValueType>
void MultiDictionary<KeyType, ValueType>::Add(KeyType Key, ValueType Value)
{
    // ...
}

template<, typename ValueType>
void MultiDictionary<TCHAR*, ValueType>::Add(TCHAR* Key, ValueType Value)
{
    // ...
}
The last method shown is what I thought it might be like, based on single template-parameter partial template-specialization, but no luck. Said code results in a compiler error about having no declaration for said method within the MultiDictionary class. Am I going to have to copy every single bit of the code over and declare something like:
template<typename KeyType, typename ValueType>
class MultiDictionary
{
    // ...
    void Add(TCHAR* Key, ValueType Value);
    // ...
}
I'm not that familiar with the more complicated aspects of template programming. I also need to figure out how to partially specialize so that my data structures will operate correctly if given pointers or references. I'm trying to avoid run-time type identification. Clearly this can be done at compile time, manually, but using templates, I was hoping to take advantage of reusable code techniques. One source for all templates, besides that partial specialization, instead of declaring and defining multiple data structures for each variation with nearly identical code.

Share this post


Link to post
Share on other sites
Advertisement
If you have a template class:

template <typename T1, typename T2>
class A { };




you can specialize it, e.g.:

template <typename T>
class A<T, int> { ... };

or

template <typename T>
class A<int, T> { ... };

or

template <>
class A<int, float> { .. };




The same applies for functions.

However, you cannot define member function for different class specializations without specializing the whole class.


template<typename ValueType>
void MultiDictionary<TCHAR*, ValueType>::Add(TCHAR* Key, ValueType Value)
{
// ...
}



That's an error because class MultiDictionary<TCHAR*, ValueType> can be totally different from the general MultiDictionary<KeyType, ValueType>. I may not even contain Add.

Share this post


Link to post
Share on other sites
Blarg, I was hoping that wouldn't be the case... a lot of copy-pasting code. Alright... might I ask, what about template specialization for references or pointers? Say I wanted a remove method to call delete if it were pointer-based or a assignment operator that deep-copies or shallow-copies appropriately?

Thanks for the help.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sion Sheevok
Blarg, I was hoping that wouldn't be the case... a lot of copy-pasting code.


Copy pasting is solved via refactoring.

If you find there will be plenty of shared functionality, factor out the common parameter:
template < class T > 
struct Base {
};

template<typename KeyType, typename ValueType>
class MultiDictionary : Base<ValueType> {
};

template<typename ValueType>
struct MultiDictionary<TCHAR*, ValueType> : Base<ValueType> {
};


Quote:
Alright... might I ask, what about template specialization for references or pointers? Say I wanted a remove method to call delete if it were pointer-based or a assignment operator that deep-copies or shallow-copies appropriately?


What about it?

Share this post


Link to post
Share on other sites
Implement everything in terms of operator <.

This is what the standard containers do, it has two advantages. First, it prevents the problem you've encountered when operator results are not consistent with each other, and it means that to use the container the key type only needs one operator defined. The standard containers go a step further and take a comparison predicate as a template parameter; the default predicate uses operator<.

With this,
>= becomes a !< b
= becomes a !< b && b !< a
The rest follow from this.

Share this post


Link to post
Share on other sites
@Antheus: Thanks, template programming is a little foreign to me, hadn't considered inheritance. Regarding pointers and references, I mean partially specializing the template for any types given to it that are pointers or references.

As in my example: Say an assignment operator for a data structure that deep-copies if the template parameter is a pointer type. Obviously I don't want it to start trying to dereference parameters that aren't pointers, in the event that the template parameter is a value as opposed to a pointer. Would I simply need to make two templated classes *or* extra methods specified for deep-copying? I'm trying to avoid Run-Time Type Identification.

I've asked around and it looks as if there's no way to do this at compile-time. I'm curious how the STL data structures manage to function appropriately with pointers, references, and values. I'm assuming the STL does.

@Deyja: That's not what I was referring to. I'm not referring to using my own comparison operators, I mean that using those operators universally doesn't work, such as in the case of a character string. Given a character string, the comparison operators will compare the memory address of the first element in the array, not the values.

Share this post


Link to post
Share on other sites
STL uses a type-traits system and/or a functor passed to the container.

For example, a std map's first 3 type parameters are:
Key type
Value type
Key comparison functor

The third defaults to std::less<Key type> (which is generally < for most types, but it is also guaranteed to work on pointers -- < is not guaranteed to work on pointers in general!)

This lets someone implement their own ordering.

If you do std::map< char*, int >, you get some arbitrary ordering on the char* pointers that doesn't pay attention to the value being pointed to.

If you std::map< char*, int, stringLess >, where stringLess is:

struct stringLess {
bool operator()( char* left, char* right) const {
return strcmp(left, right) < 0;
}
};


then the map all of a sudden orders the char*s by assuming they are pointers to C-style character strings.

You can use the same sort of strategy -- either have a functor passed in, or expose a traits class that you allow (or require!) to be specialised for particular types to change how the ordering works.

Share this post


Link to post
Share on other sites
Aye, that sounds better than specializing for only a few of many potentially troublesome parameters. I'll do just that mate. Thanks. ^^

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!