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.

 
AAPL
$96.13
Apple Inc.
+0.53
MSFT
$42.86
Microsoft Corpora
-0.30
GOOG
$566.07
Google Inc.
-5.53

MacTech Search:
Community Search:

Software Updates via MacUpdate

Data Rescue 3.2.4 - Recover lost data on...
Data Rescue is a robust and reliable hard-drive recovery solution for your Mac. Recover lost or deleted files, mount corrupted drives, and more -- Data Rescue offers complete relief from crippling... Read more
Adobe Lightroom 5.6 - Import, develop, a...
Adobe Lightroom software helps you bring out the best in your photographs, whether you're perfecting one image, searching for ten, processing hundreds, or organizing thousands. Create incredible... Read more
OneNote 15.2 - Free digital notebook fro...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that’s too important to forget. Whether you’re at... Read more
iStat Menus 4.22 - Monitor your system r...
iStat Menus lets you monitor your system right from the menubar. Included are 8 menu extras that let you monitor every aspect of your system. Some features: CPU -- Monitor cpu usage. 7 display... Read more
Ember 1.8 - Versatile digital scrapbook....
Ember (formerly LittleSnapper) is your digital scrapbook of things that inspire you: websites, photos, apps or other things. Just drag in images that you want to keep, organize them into relevant... Read more
OmniPlan 2.3.6 - Robust project manageme...
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Command-C 1.1.1 - Clipboard sharing tool...
Command-C is a revolutionary app which makes easy to share your clipboard between iOS and OS X using your local WiFi network, even if the app is not currently opened. Copy anything (text, pictures,... Read more
Knock 1.1.7 - Unlock your Mac by knockin...
Knock is a faster, safer way to sign in. You keep your iPhone with you all the time. Now you can use it as a password. You never have to open the app -- just knock on your phone twice, even when it's... Read more
Mellel 3.3.6 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
LibreOffice 4.3.0.4 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more

Latest Forum Discussions

See All

Bio Inc. is $0.99 for the Weekend, Recei...
Bio Inc. is $0.99 for the Weekend, Receives Small Update Posted by Ellis Spice on August 1st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Happy 7th Birthday Readdle! Thank You fo...
Happy 7th Birthday Readdle! | Read more »
Sharknado: The Video Game Review
Sharknado: The Video Game Review By Lee Hamlet on August 1st, 2014 Our Rating: :: SHARKNA-DON'TUniversal App - Designed for iPhone and iPad Sharknado: The Video Game brings the craziness of the movies to iOS, though it quickly... | Read more »
Clima (Weather)
Clima 1.0 Device: iOS iPhone Category: Weather Price: $.99, Version: 1.0 (iTunes) Description: Clima show you all weather information, just beautifully simple. A series of color bars can tell you at a glance exactly current... | Read more »
Sticky Soccer Review
Sticky Soccer Review By Andrew Fisher on August 1st, 2014 Our Rating: :: STICK THIS GAMEUniversal App - Designed for iPhone and iPad Sticky Soccer puts too much emphasis on the ‘sticky’ and not enough on the ‘Soccer’ or ‘Fun’.   | Read more »
Graphics-less Apocalyptic Adventure A Da...
Graphics-less Apocalyptic Adventure A Dark Room Goes Free for a Limited Time Posted by Rob Rich on August 1st, 2014 [ permalink ] | Read more »
Fraud Tycoon Review
Fraud Tycoon Review By Rob Thomas on August 1st, 2014 Our Rating: :: UNHEALTHY CREDITUniversal App - Designed for iPhone and iPad Fraud Tycoon is a half-baked, messy, promotional tie-in that does their sponsor no favors whatsoever... | Read more »
Guardians of the Galaxy: The Universal W...
Guardians of the Galaxy: The Universal Weapon is on Sale for the Weekend Posted by Rob Rich on August 1st, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Mister Beam Review
Mister Beam Review By Jordan Minor on August 1st, 2014 Our Rating: :: ILLUMINATINGUniversal App - Designed for iPhone and iPad Mister Beam’s puzzles are great. But its platforming? Not so much.   | Read more »
Hook Some More Fun With MapHook’s New Up...
Hook Some More Fun With MapHook’s New Update Posted by Jessica Fisher on August 1st, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »

Price Scanner via MacPrices.net

13-inch MacBook Airs on sale for $100 off MSR...
B&H Photo has the new 2014 13″ MacBook Airs on sale $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more
16GB iPad Air on sale for $399, save $100
Best Buy is offering the 16GB WiFi iPad Air for $399.99 on their online store for a limited time. Their price is $100 off MSRP. Choose free shipping or free store pickup (if available). Price is for... Read more
All Over For Tablets Or Just A Maturing, Evol...
CNN’s David Goldman weighs in on tablet sector doom and gloom, asking rhetorically: “Is this the beginning of the end for the tablet?” Answering that, he contends that hysteria and panic are... Read more
Letterspace 1.0.1 – New Free iOS Text Editor...
Bangkok, Thailand based independent developer Sittipon Simasanti has released Letterspace, a new text editor for iPhone, iPad, and iPod touch devices. Letterspace is a note taking app with an... Read more
Save up to $130 on an iPad mini with Apple re...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays available for up to $130 off the cost of new models, starting at $339. Apple’s one-year warranty is included... Read more
iPad Cannibalization Threat “Overblown”
Seeking Alpha’s Kevin Greenhalgh observes that while many commentators think Apple’s forthcoming 5.5-inch panel iPhone 6 will cannibalize iPad sales, in his estimation, these concerns are being... Read more
Primate Labs Releases July 2014 MacBook Pro P...
Primate Labs’ John Poole has posted Geekbench 3 results for most of the new MacBook Pro models that Apple released on Tuesday. Poole observes that overall performance improvements for the new MacBook... Read more
Apple Re-Releases Bugfixed MacBook Air EFI Fi...
Apple has posted a bugfixed version EFI Firmware Update 2.9 a for MacBook Air (Mid 2011) models. The update addresses an issue where systems may take longer to wake from sleep than expected, and... Read more
Save $50 on the 2.5GHz Mac mini, plus free sh...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $140 on an iPad Air with Apple ref...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more

Jobs Board

Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.