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

OmniGraffle 7.3 - Create diagrams, flow...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
OmniGraffle Pro 7.3 - Create diagrams, f...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
DEVONthink Pro 2.9.11 - Knowledge base,...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
DiskCatalogMaker 6.8.1 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Tunnelblick 3.7.0 - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Adobe Dreamweaver CC 2017 17.0.2.9391 -...
Dreamweaver CC 2017 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2017 allows you to... Read more
Adobe Animate CC 2017 16.2.0 - Advanced...
Animate CC 2017 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2017 (was Flash CC) lets you... Read more
A Better Finder Rename 10.15 - File, pho...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
Creative Kit 1.1 - $149.99
Creative Kit 2016--made exclusively for Mac users--is your ticket to the most amazing images you've ever created. With a variety of powerful tools at your fingertips, you'll not only repair and fine-... Read more
iMazing 2.2.3 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more

Power Rangers: Legacy Wars beginner...
Rita Repulsa is back, but this time she's invading your mobile phone in Power Rangers: Legacy Wars. What looks to be a straightforward beat 'em up is actually a tough-as-nails multiplayer strategy game that requires some deft tactical maneuvering.... | Read more »
Hearthstone celebrates the upcoming Jour...
Hearthstone gets a new expansion, Journey to Un'Goro, in a little over a week, and they'll be welcoming the Year of the Mammoth, the next season, at the same time. There's a lot to be excited about, so Blizzard is celebrating in kind. Players will... | Read more »
4 smart and stylish puzzle games like Ty...
TypeShift launched a little over a week ago, offering some puzzling new challenges for word nerds equipped with an iOS device. Created by Zach Gage, the mind behind Spelltower, TypeShift boasts, like its predecessor, a sleak design and some very... | Read more »
The best deals on the App Store this wee...
Deals, deals, deals. We're all about a good bargain here on 148Apps, and luckily this was another fine week in App Store discounts. There's a big board game sale happening right now, and a few fine indies are still discounted through the weekend.... | Read more »
The best new games we played this week
It's been quite the week, but now that all of that business is out of the way, it's time to hunker down with some of the excellent games that were released over the past few days. There's a fair few to help you relax in your down time or if you're... | Read more »
Orphan Black: The Game (Games)
Orphan Black: The Game 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dive into a dark and twisted puzzle-adventure that retells the pivotal events of Orphan Black. | Read more »
The Elder Scrolls: Legends is now availa...
| Read more »
Ticket to Earth beginner's guide: H...
Robot Circus launched Ticket to Earth as part of the App Store's indie games event last week. If you're not quite digging the space operatics Mass Effect: Andromeda is serving up, you'll be pleased to know that there's a surprising alternative on... | Read more »
Leap to victory in Nexx Studios new plat...
You’re always a hop, skip, and a jump away from a fiery death in Temple Jump, a new platformer-cum-endless runner from Nexx Studio. It’s out now on both iOS and Android if you’re an adventurer seeking treasure in a crumbling, pixel-laden temple. | Read more »
Failbetter Games details changes coming...
Sunless Sea, Failbetter Games' dark and gloomy sea explorer, sets sail for the iPad tomorrow. Ahead of the game's launch, Failbetter took to Twitter to discuss what will be different in the mobile version of the game. Many of the changes make... | Read more »

Price Scanner via MacPrices.net

Is Apple Planning An iPhone Based Modular Doc...
Today’s more powerful and larger-screened smartphones and phablets are becoming the default anchor computing device for more and more users computing devices, but even a five or six inch panel is not... Read more
Razer Launches New Razer Blade Pro World’s Fi...
Razer, the gaming and high performance hardware specialists, have announced the new Razer Blade Pro laptop — the first laptop to be qualified for THX Mobile Certification, an accreditation reserved... Read more
Gro CRM’s Apple Small Business Mac And iOS CR...
Gro Software, developers of the Mac CRM software for small business and enterprise, are included in FinancesOnline 2017 CRM Rising Stars and Great User Experience lists by business software review... Read more
Deal alert! 15-inch and 13-inch MacBook Pros...
B&H Photo has the new 2016 15″ and 13″ Apple MacBook Pros in stock today and on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Save up to $420 on a new MacBook Pro with App...
Apple is offering Certified Refurbished 2016 15″ and 13″ MacBook Pros, including some Touch Bar models, for up to $420 off original MSRP. An Apple one-year warranty is included with each model, and... Read more
12-inch 1.2GHz Retina MacBooks on sale for $1...
B&H has 12″ 1.2GHz Retina MacBooks on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.2GHz Space Gray Retina MacBook: $1449 $150 off MSRP - 12″ 1.... Read more
Is A New 10.5-inch iPad Still Coming In April...
There was no sign or mention of a long-rumored and much anticipated 10.5-inch iPad Pro in Apple’s product announcements last week. The exciting iPad news was release of an upgraded iPad Air with a... Read more
T-Mobile’s Premium Device Protection Now Incl...
Good news for T-Mobile customers who love their iPhones and iPads. The “Un-carrier” has become the first national wireless company to give customers AppleCare Services at zero additional cost as part... Read more
FileWave Ensures Support for Latest Apple OS...
FileWave multi-platform device management providers announced support for Apple’s release yesterday of iOS 10.3, macOS Sierra 10.12.4, and tvOS 11.2. FileWave has a history of providing zero-day... Read more
Use Apple’s Education discount to save up to...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: -... Read more

Jobs Board

Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
Desktop Analyst - *Apple* Products - Montef...
…technology to improve patient care. JOB RESPONSIBILITIES: Provide day-to-day support for Apple Hardware and Software in the environment based on the team's support Read more
*Apple* Mobile Master - Best Buy (United Sta...
**493168BR** **Job Title:** Apple Mobile Master **Location Number:** 000827-Denton-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
*Apple* Mobile Master - Best Buy (United Sta...
**492889BR** **Job Title:** Apple Mobile Master **Location Number:** 000886-Norwalk-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.