TweetFollow Us on Twitter

Sept 98 Factory Floor

Volume Number: 14 (1998)
Issue Number: 9
Column Tag: From The Factory Floor

The New C++ Standard:
Partial Template Specialization

by Howard Hinnant and Dave Mark, ©1998 by Metrowerks, Inc., all rights reserved.

In last month's column, we continued our exploration of the new C++ standard, specifically taking a look at the subject of locales. In this month's column, Howard Hinnant is back once again, and will take us through partial template specialization.

Howard Hinnant is a software engineer on the MSL team at Metrowerks, and is responsible for the C++ and EC++ libraries. Howard is a refugee from the aerospace industry where FORTRAN still rules. He has extensive experience in scientific computing including C++ implementations of linear algebra, finite difference and finite element solvers.

Dave: What exactly is partial template specialization?

Howard: In order to explain partial template specialization, it might first be easier to describe full template specialization. Consider:

template <class T>
class vector
{
...
};

This works well for most items that we might want to keep a list of. However, if we wanted to keep a vector<bool>, then an obvious optimization would be store each value in one bit, instead of actually storing a list of bools. This could be neatly accomplished by defining a specialization of our vector class:

template <>
class vector<bool>
{
...
};

This is known as template specialization.

Now consider a class template with two type parameters. I'll keep picking on vector:

template <class T, class Allocator>
class vector {
...
};

And let's say we still want to optimize for when T == bool. We can do this by:

template <class Allocator>
class vector<bool, Allocator> {
...
};

Since not all template parameters have been nailed down, this is known as partial template specialization. So now when I say:

vector<bool, myAllocator> a;

I get the optimized implementation for bool.

Dave: Cool. Any other useful optimizations you could do?

Howard: You can do some really cool things with this concept. For example, let's say you wanted to make a special vector for holding pointers. Here is a possibility:

template <class T, class Allocator>
class vector<T*, Allocator>
{
...
};

This might come in handy if you wanted some special behavior for when the element type was a pointer to something. For instance, one might want to treat vectors of pointers as pointing to heap based objects, and manage those pointers with new and delete. The standard library, of course, does not do this.

Dave: So how does partial template specialization affect the standard library?

Howard: MSL does use partial template specialization to implement vector<bool> as alluded to earlier. Additionally, there is a struct in <iterator> that looks like:

template <class Iterator>
struct iterator_traits
{
  typedef typename Iterator::difference_type  difference_type;
  typedef typename Iterator::value_type  value_type;
  typedef typename Iterator::pointer    pointer;
  typedef typename Iterator::reference    reference;
  typedef typename Iterator::iterator_category  iterator_category;
};

The purpose of this class is to help code that takes iterators find out valuable things about the iterator that it's working on. For example, consider the standard algorithm iter_swap that takes two iterators, and swaps the values that the iterators point to:

template <class ForwardIterator1, class ForwardIterator2>
void
iter_swap(ForwardIterator1 a, ForwardIterator2 b)
{
  typedef typename                               iterator_traits<ForwardIterator1>::value_type Value;
  Value tmp(*a);
  *a = *b;
  *b = tmp;
}

The routine iter_swap must create a temporary variable in order to accomplish the swap. But what is the type of the temporary? It queries the iterator to find out the proper type.

Thus all valid iterators (at least those that want to be used in standard algorithms and containers) must create the typedefs referred to above so that they can be queried via iterator_traits. This can be easily accomplished by deriving your custom iterators from the standard iterator struct:

In <iterator>:

template <class Category, class T, class Distance = ptrdiff_t,
     class Pointer = T*, class Reference = T&>  
struct iterator
{
   typedef Distance    difference_type;
   typedef T        value_type;
   typedef Pointer    pointer;
   typedef Reference  reference;
   typedef Category    iterator_category;
};

In your code:

class MyIterator
  : public std::iterator<random_access_iterator_tag, MyClass>
{
...
};

Dave: I see. But if I remember right, an iterator is just a generalization of a built-in pointer. In fact, built-in pointers can be used in all the standard algorithms. So how does iter_swap query a built-in pointer for its value_type? You can't derive int* from std::iterator.

Howard: Ahh... Exactly! This is where partial template specialization rides in to save the day. The standard library defines a specialization of iterator_traits for a pointer to anything:

template <class T>
struct iterator_traits<T*>
{
  typedef ptrdiff_t    difference_type;
  typedef T          value_type;
  typedef T*        pointer;
  typedef T&        reference;
  typedef random_access_iterator_tag  iterator_category;
};

So now when iter_swap tries to define Value:

typedef typename iterator_traits<ForwardIterator1>::value_type Value;

And ForwardIterator1 has the type int*, iterator_traits<int*> picks up the partial specialization and answers back with int. This is really a pretty slick design.

Dave: That is neat. But partial template specialization is a relatively new feature of CodeWarrior. How did MSL handle this problem before this feature was available?

Howard: Oh, yes... The Dark Time. We took advantage of the fact that we did have full template specialization available to us. So we created full specializations for iterator_traits for every type we could think of: char*, int*, bool*, short*, long* ... plus all combinations of unsigned and const modifiers. This worked pretty well except for one minor little detail. We could not create a specialization for myType*. Here myType represents all of the classes which the customer created.

In order to combat this last problem, we (actually Dennis C. De Mars) created a macro which defined a full specialization of iterator_traits for its argument myType:

#define __MSL_FIX_ITERATORS__(myType) \
 template<> \
 struct std::iterator_traits  <myType*> { \
   typedef ptrdiff_t      difference_type; \
   typedef myType        value_type; \
   typedef myType*        pointer; \
   typedef myType&        reference; \
   typedef random_access_iterator_tag  iterator_category; \
 };

Yes, everyone knows about __MSL_FIX_ITERATORS__. And you now know the full story behind this macro. It is a macro that no one liked, but we could not live without it.

Even if you didn't use the standard algorithms, you got bit by this when you used the standard containers, because they used it. We had plans to reduce MSL's dependence on iterator_traits, but Andreas (our C++ compiler guru) came out with partial specialization before we could implement those plans. This was really best as we could have only reduced the dependence, not eliminated it.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

The beginner's guide to Warbits
Warbits is a turn-based strategy that's clearly inspired by Nintendo's Advance Wars series. Since turn-based strategy games can be kind of tricky to dive into, see below for a few tips to help you in the beginning. Positioning is crucial [Read... | Read more »
How to upgrade your character in Spellsp...
So you’ve mastered the basics of Spellspire. By which I mean you’ve realised it’s all about spelling things in a spire. What next? Well you’re going to need to figure out how to toughen up your character. It’s all well and good being able to spell... | Read more »
5 slither.io mash-ups we'd love to...
If there's one thing that slither.io has proved, it's that the addictive gameplay of Agar.io can be transplanted onto basically anything and it will still be good fun. It wouldn't be surprising if we saw other developers jumping on the bandwagon,... | Read more »
How to navigate the terrain in Sky Charm...
Sky Charms is a whimsical match-'em up adventure that uses creative level design to really ramp up the difficulty. [Read more] | Read more »
Victorious Knight (Games)
Victorious Knight 1.3 Device: iOS Universal Category: Games Price: $1.99, Version: 1.3 (iTunes) Description: New challenges awaits you! Experience fresh RPG experience with a unique combat mechanic, packed with high quality 3D... | Read more »
Agent Gumball - Roguelike Spy Game (Gam...
Agent Gumball - Roguelike Spy Game 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Someone’s been spying on Gumball. What the what?! Two can play at that game! GO UNDERCOVERSneak past enemy... | Read more »
Runaway Toad (Games)
Runaway Toad 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: It ain’t easy bein’ green! Tap, hold, and swipe to help Toad hop to safety in this gorgeous new action game from the creators of... | Read more »
PsyCard (Games)
PsyCard 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: From the makers och Card City Nights, Progress To 100 and Ittle Dew PSYCARD is a minesweeper-like game set in a cozy cyberpunk... | Read more »
Sago Mini Robot Party (Education)
Sago Mini Robot Party 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: -- Children's Technology Review Editor's Choice -- | Read more »
How to get a high score in every level o...
Sky Charms is an adorable match three puzzler that provides a decent challenge thanks to its creative level design. It regularly presents something new, forcing you to think on your feet. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple restocks Certified Refurbished Mac mini...
Apple has restocked Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
Amazon.com has the 15″ 2.2GHz Retina MacBook Pro on sale for $1699.99 including free shipping. Their price is $300 off MSRP, and it’s the lowest price available for this model from any reseller (and... Read more
Apple Beats Microsoft at Own Game; Amazon Pri...
First quarter seasonality combined with an overall disinterested customer base led to an annual decline of 14.7% in worldwide tablet shipments during the first quarter of 2016 (1Q16). Worldwide... Read more
Tablets Had Worst Quarter Since 2012, says St...
The global tablet market began 2016 just as 2015 left off, down. Tablet shipments fell 10% to 46.5 million units during the Q1 2016, according to the new “Preliminary Global Tablet Shipments and... Read more
Clearance 13-inch MacBook Airs, Apple refurbi...
Apple recently dropped prices on certified refurbished 2015 13″ MacBook Airs with 4GB of RAM with models now available starting at $759. An Apple one-year warranty is included with each MacBook, and... Read more
Clearance 12-inch Retina MacBooks, Apple refu...
Apple has dropped prices on Certified Refurbished 2015 12″ Retina MacBooks with models now available starting at $929. Apple will include a standard one-year warranty with each MacBook, and shipping... Read more
Aleratec Releases Mac Software Upgrade for 1...
California based Aleratec Inc., designer, developer and manufacturer of Portable Device Management (PDM) charge/sync products for mobile devices and professional-grade duplicators for hard disk... Read more
Sale! Amazon offers 27-inch iMac, 13-inch 2.9...
Amazon has the 27″ 3.2GHz 5K iMac and the 13″ 3.9GHz Retina MacBook Pro on sale for $300 off MSRP, each including free shipping, for a limited time: - 27″ 3.2GHz/1TB HD 5K iMac (model MK462LL/A): $... Read more
Apple refurbished 13-inch Retina MacBook Pros...
Apple has Certified Refurbished 13″ Retina MacBook Pros available for up to $270 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.7GHz... Read more
13-inch 2.7GHz/128GB Retina MacBook Pro on sa...
Take $200 off MSRP on the price of a new 13″ 2.7GHz/128GB Retina MacBook Pro (model MF839LL/A) at Amazon. Shipping is free: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1099.99 $200 off MSRP Act now if... Read more

Jobs Board

Automotive Sales Consultant - Apple Ford Linc...
…you. The best candidates are smart, technologically savvy and are customer focused. Apple Ford Lincoln Apple Valley is different, because: $30,000 annual salary Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 48260200 Phoenix, Arizona, United States Posted: Apr. 22, 2016 Weekly Hours: 40.00 **Job Summary** As an Apple Solutions Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
Simply Mac *Apple* Specialist- Service Repa...
Simply Mac is the largest premier retailer of Apple products in the nation. In order to support our growing customer base, we are currently looking for a driven Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.