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

VirtualBox 5.2.0 - x86 virtualization so...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
Dropbox 37.4.29 - Cloud backup and synch...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more
Google Chrome 62.0.3202.62 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Chromium 62.0.3202.62 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 62.0.3202.62: High CVE-2017-5124: UXSS with... Read more
Fantastical 2.4.3 - Create calendar even...
Fantastical 2 is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
Things 3.2.1 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
A Better Finder Attributes 6.06 - Change...
A Better Finder Attributes is the ultimate file-tweaking tool for OS X. It combines photo-shooting date and file date changing along with a few unique tricks of its own. Change EXIF Timestamps at... Read more
MacCleanse 6.0.5 - $29.95
MacCleanse is the product of thousands of hours of intense research and development. It meticulously scans all of the nooks and crannies of a computer for unnecessary junk that can take up huge... Read more
Smultron 10.0.2 - Easy-to-use, powerful...
Smultron 10 is an elegant and powerful text editor that is easy to use. You can use Smultron 10 to create or edit any text document. Everything from a web page, a note or a script to any single piece... Read more
Capto 1.2.5 - $29.99
Capto (was Voila) is an easy-to-use app that takes capturing, recording, video and image editing to the next level. With an intelligent file manager and quick sharing options, Capto is perfect for... Read more

Time Recoil (Games)
Time Recoil 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: Time Recoil is a top-down shooter where you kill to slow time, dominate slow motion gunfights, and trigger devastating special... | Read more »
Campfire Cooking (Games)
Campfire Cooking 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Returner 77 (Games)
Returner 77 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Returner 77 is a cinematic space mystery puzzle game. You are in a giant alien spaceship hovering above Earth, after everything... | Read more »
Dune! guide - how to toe the line and ge...
Publisher Voodoo is at it again with an all new high score chaser -- Dune! In this fast-paced arcade game, you have to propel yourself along sand dunes, gaining enough momentum to jump above the line to score points, while making sure you have... | Read more »
The best deals on the App Store this wee...
Happy Tuesday, dear readers. Your favorite part of the week as officially arrived. It's time to take a look at the best deals in games. Things are admittedly a bit sparse, but there are a few diamonds in the rough to see you through if you're... | Read more »
Be the last person standing in Legacy of...
Yoozoo Games’ popular action MMO Legacy of Discord is getting a huge new update to celebrate its first anniversary. Perhaps the biggest change is the addition of an exciting survival mode titled Last Guardian. This new survival mode will pit you... | Read more »
Home Street guide - how to make friends...
From the creators of Food Street comes Home Street, a new simulation game that tasks you with building a social network and designing a beautiful home. It's a bit like The Sims, but you won't have to worry about the daily chores involved (feeding,... | Read more »
Color Ballz guide - how to bounce to the...
Color Ballz is an addictive new arcade title from Ketchapp Studios. It takes old school mechanics from games like Brickles and puts a fun twist on it. Your job? To catch balls with a paddle and send them back into a chute to be carried back to... | Read more »
Q&A: A-33 Studio explains why Combat...
When it comes to mobile FPS, it’s often tricky to get the fundamentals right on a platform lacking a physical controller, large display and hefty RAM. With Combat Squad: Project Wednesday, A-33 Studio bravely took on the challenge of making a... | Read more »
Taichi Panda 3: Dragon Hunter guide - ti...
Taichi Panda 3: Dragon Hunter launched this week to players all over the world. It's a beautiful mobile MMORPG that blends elements of Eastern and Western fantasy. It reminds us of a mix between World of Warcraft and Jade Empire. MMO's can have a... | Read more »

Price Scanner via MacPrices.net

13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
15″ MacBook Pros on sale for up to $200 off M...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2249, $150... Read more
Roundup of Apple Certified Refurbished iMacs,...
Apple has a full line of Certified Refurbished 2017 21″ and 27″ iMacs available starting at $1019 and ranging up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free... Read more
Sale! 27″ 3.8GHz 5K iMac for $2098, save $201...
Amazon has the 27″ 3.8GHz 5K iMac (MNED2LL/A) on sale today for $2098 including free shipping. Their price is $201 off MSRP, and it’s the lowest price available for this model (Apple’s $1949... Read more
Sale! 10″ Apple WiFi iPad Pros for up to $100...
B&H Photo has 10.5″ WiFi iPad Pros in stock today and on sale for $50-$100 off MSRP. Each iPad includes free shipping, and B&H charges sales tax in NY & NJ only: – 10.5″ 64GB iPad Pro: $... Read more
Apple iMacs on sale for up to $130 off MSRP w...
B&H Photo has 21-inch and 27-inch iMacs in stock and on sale for up to $130 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2179 $... Read more
2017 3.5GHz 6-Core Mac Pro on sale for $2799,...
B&H Photo has the 2017 3.5GHz 6-Core Mac Pro (MD878LL/A) on sale today for $2799 including free shipping plus NY & NJ sales tax only . Their price is $200 off MSRP. Read more
12″ 1.2GHz Space Gray MacBook on sale for $11...
Amazon has the 2017 12″ 1.2GHz Space Gray Retina MacBook on sale for $100 off MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $1199.99 $100 off MSRP Read more
Bare Bones Software Releases macOS High Sierr...
Bare Bones Software has announced the release and immediate availability of BBEdit 12.0, a significant upgrade to its professional strength text and code editor. BBEdit 12 introduces a new foundation... Read more
Yale Announces Availability of Apple HomeKit-...
Yale Locks & Hardware has announced that Apple HomeKit support for its Assure Lock family is available this month. The new Yale iM1 Network Module, which provides support for the Apple Home app... Read more

Jobs Board

*Apple* News Product Marketing Mgr., Publish...
Job Summary The Apple News Product Marketing Manager will work closely with a cross-functional group to assist in defining and marketing new features and services. Read more
Fraud Analyst, *Apple* Advertising Platform...
Job Summary Apple Ad Platforms has an opportunity to redefine advertising on mobile devices. Apple reaches hundreds of millions of iPhone, iPod touch, and iPad Read more
*Apple* Information Security - Security Data...
Job Summary This role is responsible for helping to strengthen Apple 's information security posture through the identification and curation of security event data. Read more
Lead *Apple* Solution Consultant - Apple In...
…develop a team of diverse partner employees focusing on excellence to deliver the Apple story. Even when you're not present, you will maintain a consistent influence Read more
watchOS Frameworks Engineering Manager, *App...
Job Summary Join the team that is shaping the future of software development for Apple Watch! Apple is looking for an exceptional software engineering leader to Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.