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

Latest Forum Discussions

See All

Top Mobile Game Discounts
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links... | Read more »
Price of Glory unleashes its 1.4 Alpha u...
As much as we all probably dislike Maths as a subject, we do have to hand it to geometry for giving us the good old Hexgrid, home of some of the best strategy games. One such example, Price of Glory, has dropped its 1.4 Alpha update, stocked full... | Read more »
The SLC 2025 kicks off this month to cro...
Ever since the Solo Leveling: Arise Championship 2025 was announced, I have been looking forward to it. The promotional clip they released a month or two back showed crowds going absolutely nuts for the previous competitions, so imagine the... | Read more »
Dive into some early Magicpunk fun as Cr...
Excellent news for fans of steampunk and magic; the Precursor Test for Magicpunk MMORPG Crystal of Atlan opens today. This rather fancy way of saying beta test will remain open until March 5th and is available for PC - boo - and Android devices -... | Read more »
Prepare to get your mind melted as Evang...
If you are a fan of sci-fi shooters and incredibly weird, mind-bending anime series, then you are in for a treat, as Goddess of Victory: Nikke is gearing up for its second collaboration with Evangelion. We were also treated to an upcoming... | Read more »
Square Enix gives with one hand and slap...
We have something of a mixed bag coming over from Square Enix HQ today. Two of their mobile games are revelling in life with new events keeping them alive, whilst another has been thrown onto the ever-growing discard pile Square is building. I... | Read more »
Let the world burn as you have some fest...
It is time to leave the world burning once again as you take a much-needed break from that whole “hero” lark and enjoy some celebrations in Genshin Impact. Version 5.4, Moonlight Amidst Dreams, will see you in Inazuma to attend the Mikawa Flower... | Read more »
Full Moon Over the Abyssal Sea lands on...
Aether Gazer has announced its latest major update, and it is one of the loveliest event names I have ever heard. Full Moon Over the Abyssal Sea is an amazing name, and it comes loaded with two side stories, a new S-grade Modifier, and some fancy... | Read more »
Open your own eatery for all the forest...
Very important question; when you read the title Zoo Restaurant, do you also immediately think of running a restaurant in which you cook Zoo animals as the course? I will just assume yes. Anyway, come June 23rd we will all be able to start up our... | Read more »
Crystal of Atlan opens registration for...
Nuverse was prominently featured in the last month for all the wrong reasons with the USA TikTok debacle, but now it is putting all that behind it and preparing for the Crystal of Atlan beta test. Taking place between February 18th and March 5th,... | Read more »

Price Scanner via MacPrices.net

AT&T is offering a 65% discount on the ne...
AT&T is offering the new iPhone 16e for up to 65% off their monthly finance fee with 36-months of service. No trade-in is required. Discount is applied via monthly bill credits over the 36 month... Read more
Use this code to get a free iPhone 13 at Visi...
For a limited time, use code SWEETDEAL to get a free 128GB iPhone 13 Visible, Verizon’s low-cost wireless cell service, Visible. Deal is valid when you purchase the Visible+ annual plan. Free... Read more
M4 Mac minis on sale for $50-$80 off MSRP at...
B&H Photo has M4 Mac minis in stock and on sale right now for $50 to $80 off Apple’s MSRP, each including free 1-2 day shipping to most US addresses: – M4 Mac mini (16GB/256GB): $549, $50 off... Read more
Buy an iPhone 16 at Boost Mobile and get one...
Boost Mobile, an MVNO using AT&T and T-Mobile’s networks, is offering one year of free Unlimited service with the purchase of any iPhone 16. Purchase the iPhone at standard MSRP, and then choose... Read more
Get an iPhone 15 for only $299 at Boost Mobil...
Boost Mobile, an MVNO using AT&T and T-Mobile’s networks, is offering the 128GB iPhone 15 for $299.99 including service with their Unlimited Premium plan (50GB of premium data, $60/month), or $20... Read more
Unreal Mobile is offering $100 off any new iP...
Unreal Mobile, an MVNO using AT&T and T-Mobile’s networks, is offering a $100 discount on any new iPhone with service. This includes new iPhone 16 models as well as iPhone 15, 14, 13, and SE... Read more
Apple drops prices on clearance iPhone 14 mod...
With today’s introduction of the new iPhone 16e, Apple has discontinued the iPhone 14, 14 Pro, and SE. In response, Apple has dropped prices on unlocked, Certified Refurbished, iPhone 14 models to a... Read more
B&H has 16-inch M4 Max MacBook Pros on sa...
B&H Photo is offering a $360-$410 discount on new 16-inch MacBook Pros with M4 Max CPUs right now. B&H offers free 1-2 day shipping to most US addresses: – 16″ M4 Max MacBook Pro (36GB/1TB/... Read more
Amazon is offering a $100 discount on the M4...
Amazon has the M4 Pro Mac mini discounted $100 off MSRP right now. Shipping is free. Their price is the lowest currently available for this popular mini: – Mac mini M4 Pro (24GB/512GB): $1299, $100... Read more
B&H continues to offer $150-$220 discount...
B&H Photo has 14-inch M4 MacBook Pros on sale for $150-$220 off MSRP. B&H offers free 1-2 day shipping to most US addresses: – 14″ M4 MacBook Pro (16GB/512GB): $1449, $150 off MSRP – 14″ M4... Read more

Jobs Board

All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.