• T a b le o f C o n t e n t s

C++ Templates: The Complete Guide

B yD a v id V a n d e v o o r d e , N ic o la i M . J o s u t t is

P u b lis h e r : A d d is o n W e s le y
P u b D a te : N o v e m b e r 1 2, 20 0 2
IS B N : 0 -20 1 -7 3 4 8 4 -2
P a g e s : 5 5 2

T em p lates are am ong th e m os t p owerfu l featu res of C + + , bu t th ey are too often

neg lected, m i s u nders tood, and m i s u s ed. C++ Templates: The Complete Gu i d e
p rov i des s oftware arch i tects and eng i neers wi th a clear u nders tandi ng of wh y,
wh en, and h ow to u s e tem p lates to bu i ld and m ai ntai n cleaner, fas ter, and
s m arter s oftware m ore effi ci ently.

C++ Templates beg i ns wi th an i ns i g h tfu l tu tori al on bas i c concep ts and lang u ag e

featu res . T h e rem ai nder of th e book s erv es as a com p reh ens i v e reference,
focu s i ng fi rs t on lang u ag e detai ls , th en on a wi de rang e of codi ng tech ni q u es , and
fi nally on adv anced ap p li cati ons for tem p lates . E x am p les u s ed th rou g h ou t th e
book i llu s trate abs tract concep ts and dem ons trate bes t p racti ces .

R eaders learn

• T h e ex act beh av i ors of tem p lates

• H ow to av oi d th e p i tfalls as s oci ated wi th tem p lates
• I di om s and tech ni q u es , from th e bas i c to th e p rev i ou s ly u ndocu m ented
• H ow to reu s e s ou rce code wi th ou t th reateni ng p erform ance or s afety
• H ow to i ncreas e th e effi ci ency of C + + p rog ram s
• H ow to p rodu ce m ore flex i ble and m ai ntai nable s oftware
T h i s p racti cal g u i de s h ows p rog ram m ers h ow to ex p loi t th e fu ll p ower of th e
tem p late featu res i n C + + .
• T a b le o f C o n t e n t s

C++ Templates: The Complete Guide

B yD a v id V a n d e v o o r d e , N ic o la i M . J o s u t t is

P u b lis h e r : A d d is o n W e s le y
P u b D a te : N o v e m b e r 1 2, 20 0 2
IS B N : 0 -20 1 -7 3 4 8 4 -2
P a g e s : 5 5 2

C o p yr i g h t
P r e fa c e
A c k n o w le d g m e n t s
N ic o 's A c k n o w le d g m e n t s
D a v id 's A c k n o w le d g m e n t s

C h a p t e r 1 . A b o u t T h is B o o k
S e c t i o n 1 .1 . W h a t Y o u S h o u l d K n o w B e f o r e R e a d in g T h is B o o k
S e c t i o n 1 .2. O v e r a l l S t r u c t u r e o f t h e B o o k
S e c t i o n 1 .3 . H o w t o R e a d T h is B o o k
S e c t i o n 1 .4 . S o m e R e m a r k s A b o u t P r o g r a m m i n g S t yl e
S e c t i o n 1 .5 . T h e S t a n d a r d v e r s u s R e a l i t y
S e c t i o n 1 .6 . E x a m p l e C o d e a n d A d d i t i o n a l I n f o r m a t i o n s
S e c t i o n 1 .7 . F e e d b a c k

P a r t I : T h e B a s ic s
C h a p t e r 2. F u n c t i o n T e m p l a t e s
S e c t i o n 2.1 . A F ir s t L o o k a t F u n c t io n T e m p la t e s
S e c t i o n 2.2. A r g u m e n t D e d u c t i o n
S e c t i o n 2.3 . T e m p l a t e P a r a m e t e r s
 S e c t i o n 2.4 . O v e r l o a d i n g F u n c t i o n T e m p l a t e s
S e c t i o n 2.5 . S u m m a r y

C h a p t e r 3 . C la s s T e m p la t e s
S e c t i o n 3 .1 . I m p l e m e n t a t i o n o f C l a s s T e m p l a t e Stack
S e c t i o n 3 .2. U s e o f C l a s s T e m p l a t e Stack
S e c t i o n 3 .3 . S p e c i a l i z a t i o n s o f C l a s s T e m p l a t e s
S e c t i o n 3 .4 . P a r t i a l S p e c i a l i z a t i o n
S e c t i o n 3 .5 . D e f a u l t T e m p l a t e A r g u m e n t s
S e c t i o n 3 .6 . S u m m a r y

C h a p t e r 4 . N o n t yp e T e m p l a t e P a r a m e t e r s
S e c t i o n 4 .1 . N o n t yp e C l a s s T e m p l a t e P a r a m e t e r s
S e c t i o n 4 .2. N o n t yp e F u n c t i o n T e m p l a t e P a r a m e t e r s
S e c t i o n 4 .3 . R e s t r i c t i o n s f o r N o n t yp e T e m p l a t e P a r a m e t e r s
S e c t i o n 4 .4 . S u m m a r y

C h a p t e r 5 . T r ic k yB a s ic s
S e c t i o n 5 .1 . K e yw o r d typename
S e c t i o n 5 .2. U s i n g this->
S e c t i o n 5 .3 . M e m b e r T e m p l a t e s
S e c t i o n 5 .4 . T e m p l a t e T e m p l a t e P a r a m e t e r s
S e c t i o n 5 .5 . Z e r o I n i t i a l i z a t i o n
S e c t i o n 5 .6 . U s i n g S t r i n g L i t e r a l s a s A r g u m e n t s f o r F u n c t i o n T e m p l a t e s
S e c t i o n 5 .7 . S u m m a r y

C h a p t e r 6 . U s in g T e m p la t e s in P r a c t ic e
S e c t i o n 6 .1 . T h e I n c l u s i o n M o d e l
S e c t i o n 6 .2. E x p l i c i t I n s t a n t i a t i o n
S e c t i o n 6 .3 . T h e S e p a r a t i o n M o d e l
S e c t i o n 6 .4 . T e m p l a t e s a n d inline
S e c t i o n 6 .5 . P r e c o m p i l e d H e a d e r s
S e c t i o n 6 .6 . D e b u g g i n g T e m p l a t e s
S e c t i o n 6 .7 . A f t e r n o t e s
S e c t i o n 6 .8 . S u m m a r y

C h a p t e r 7 . B a s ic T e m p la t e T e r m in o lo g y
S e c t i o n 7 .1 . " C l a s s T e m p l a t e " o r " T e m p l a t e C l a s s " ?
S e c t i o n 7 .2. I n s t a n t i a t i o n a n d S p e c i a l i z a t i o n
S e c t i o n 7 .3 . D e c l a r a t i o n s v e r s u s D e f i n i t i o n s
S e c t i o n 7 .4 . T h e O n e -D e f i n i t i o n R u l e
S e c t i o n 7 .5 . T e m p l a t e A r g u m e n t s v e r s u s T e m p l a t e P a r a m e t e r s
P a r t I I : T e m p la t e s in D e p t h
C h a p t e r 8 . F u n d a m e n t a ls in D e p t h
S e c t i o n 8 .1 . P a r a m e t e r i z e d D e c l a r a t i o n s
S e c t i o n 8 .2. T e m p l a t e P a r a m e t e r s
S e c t i o n 8 .3 . T e m p l a t e A r g u m e n t s
S e c t i o n 8 .4 . F r i e n d s
S e c t i o n 8 .5 . A f t e r n o t e s

C h a p t e r 9 . N a m e s in T e m p la t e s
S e c t i o n 9 .1 . N a m e T a x o n o m y
S e c t i o n 9 .2. L o o k i n g U p N a m e s
S e c t i o n 9 .3 . P a r s i n g T e m p l a t e s
S e c t i o n 9 .4 . D e r i v a t i o n a n d C l a s s T e m p l a t e s
S e c t i o n 9 .5 . A f t e r n o t e s

C h a p t e r 1 0 . I n s t a n t ia t io n
S e c t i o n 1 0 .1 . O n -D e m a n d I n s t a n t i a t i o n
S e c t i o n 1 0 .2. L a z y I n s t a n t i a t i o n
S e c t i o n 1 0 .3 . T h e C + + I n s t a n t ia t io n M o d e l
S e c t i o n 1 0 .4 . I m p l e m e n t a t i o n S c h e m e s
S e c t i o n 1 0 .5 . E x p l i c i t I n s t a n t i a t i o n
S e c t i o n 1 0 .6 . A f t e r n o t e s

C h a p t e r 1 1 . T e m p la t e A r g u m e n t D e d u c t io n
S e c t i o n 1 1 .1 . T h e D e d u c t i o n P r o c e s s
S e c t i o n 1 1 .2. D e d u c e d C o n t e x t s
S e c t i o n 1 1 .3 . S p e c i a l D e d u c t i o n S i t u a t i o n s
S e c t i o n 1 1 .4 . A l l o w a b l e A r g u m e n t C o n v e r s i o n s
S e c t i o n 1 1 .5 . C l a s s T e m p l a t e P a r a m e t e r s
S e c t i o n 1 1 .6 . D e f a u l t C a l l A r g u m e n t s
S e c t i o n 1 1 .7 . T h e B a r t o n -N a c k m a n T r i c k
S e c t i o n 1 1 .8 . A f t e r n o t e s

C h a p t e r 1 2. S p e c i a l i z a t i o n a n d O v e r l o a d i n g
S e c t i o n 1 2.1 . W h e n " G e n e r ic C o d e " D o e s n 't Q u it e C u t I t
S e c t i o n 1 2.2. O v e r l o a d i n g F u n c t i o n T e m p l a t e s
S e c t i o n 1 2.3 . E x p l i c i t S p e c i a l i z a t i o n
S e c t i o n 1 2.4 . P a r t i a l C l a s s T e m p l a t e S p e c i a l i z a t i o n
S e c t i o n 1 2.5 . A f t e r n o t e s

C h a p t e r 1 3 . F u t u r e D ir e c t io n s
S e c t i o n 1 3 .1 . T h e A n g l e B r a c k e t H a c k
 S e c t i o n 1 3 .2. R e l a x e d typename R u l e s
S e c t i o n 1 3 .3 . D e f a u l t F u n c t i o n T e m p la t e A r g u m e n t s
S e c t i o n 1 3 .4 . S t r i n g L i t e r a l a n d F l o a t i n g -P o i n t T e m p l a t e A r g u m e n t s
S e c t i o n 1 3 .5 . R e l a x e d M a t c h i n g o f T e m p l a t e T e m p l a t e P a r a m e t e r s
S e c t i o n 1 3 .6 . T yp e d e f T e m p l a t e s
S e c t i o n 1 3 .7 . P a r t i a l S p e c i a l i z a t i o n o f F u n c t i o n T e m p l a t e s
S e c t i o n 1 3 .8 . T h e typeof O p e r a t o r
S e c t i o n 1 3 .9 . N a m e d T e m p l a t e A r g u m e n t s
S e c t i o n 1 3 .1 0 . S t a t i c P r o p e r t i e s
S e c t i o n 1 3 .1 1 . C u s t o m I n s t a n t ia t io n D ia g n o s t ic s
S e c t i o n 1 3 .1 2. O v e r l o a d e d C l a s s T e m p l a t e s
S e c t i o n 1 3 .1 3 . L i s t P a r a m e t e r s
S e c t i o n 1 3 .1 4 . L a yo u t C o n t r o l
S e c t i o n 1 3 .1 5 . I n i t i a l i z e r D e d u c t i o n
S e c t i o n 1 3 .1 6 . F u n c t i o n E x p r e s s i o n s
S e c t i o n 1 3 .1 7 . A f t e r n o t e s

P a r t I II : T e m p la t e s a n d D e s ig n
C h a p t e r 1 4 . T h e P o l ym o r p h i c P o w e r o f T e m p l a t e s
S e c t i o n 1 4 .1 . D yn a m i c P o l ym o r p h i s m
S e c t i o n 1 4 .2. S t a t i c P o l ym o r p h i s m
S e c t i o n 1 4 .3 . D yn a m i c v e r s u s S t a t i c P o l ym o r p h i s m
1 4 .4 N e w F o r m s o f D e s ig n P a t t e r n s
S e c t i o n 1 4 .5 . G e n e r i c P r o g r a m m i n g
S e c t i o n 1 4 .6 . A f t e r n o t e s

C h a p t e r 1 5 . T r a it s a n d P o lic y C la s s e s
S e c t i o n 1 5 .1 . A n E x a m p l e : A c c u m u l a t i n g a S e q u e n c e
S e c t i o n 1 5 .2. T yp e F u n c t i o n s
S e c t i o n 1 5 .3 . P o l i c y T r a i t s
S e c t i o n 1 5 .4 . A f t e r n o t e s

C h a p t e r 1 6 . T e m p la t e s a n d I n h e r it a n c e
S e c t i o n 1 6 .1 . N a m e d T e m p l a t e A r g u m e n t s
S e c t i o n 1 6 .2. T h e E m p t y B a s e C l a s s O p t i m i z a t i o n ( E B C O )
S e c t i o n 1 6 .3 . T h e C u r i o u s l y R e c u r r i n g T e m p l a t e P a t t e r n ( C R T P )
S e c t i o n 1 6 .4 . P a r a m e t e r i z e d V i r t u a l i t y
S e c t i o n 1 6 .5 . A f t e r n o t e s

C h a p te r 1 7 . M e ta p r o g r a m s
S e c t i o n 1 7 .1 . A F ir s t E x a m p le o f a M e t a p r o g r a m
S e c t i o n 1 7 .2. E n u m e r a t i o n V a l u e s v e r s u s S t a t i c C o n s t a n t s
 S e c t i o n 1 7 .3 . A S e c o n d E x a m p le : C o m p u t in g t h e S q u a r e R o o t
S e c t i o n 1 7 .4 . U s i n g I n d u c t i o n V a r i a b l e s
S e c t i o n 1 7 .5 . C o m p u t a t i o n a l C o m p l e t e n e s s
S e c t i o n 1 7 .6 . R e c u r s i v e I n s t a n t i a t i o n v e r s u s R e c u r s i v e T e m p l a t e A r g u m e n t s
S e c t i o n 1 7 .7 . U s i n g M e t a p r o g r a m s t o U n r o l l L o o p s
S e c t i o n 1 7 .8 . A f t e r n o t e s

C h a p t e r 1 8 . E x p r e s s io n T e m p la t e s
S e c t i o n 1 8 .1 . T e m p o r a r i e s a n d S p l i t L o o p s
S e c t i o n 1 8 .2. E n c o d i n g E x p r e s s i o n s i n T e m p l a t e A r g u m e n t s
S e c t i o n 1 8 .3 . P e r f o r m a n c e a n d L i m i t a t i o n s o f E x p r e s s i o n T e m p l a t e s
S e c t i o n 1 8 .4 . A f t e r n o t e s

P a r t IV : A d v a n c e d A p p lic a t io n s
C h a p t e r 1 9 . T yp e C l a s s i f i c a t i o n
S e c t i o n 1 9 .1 . D e t e r m i n i n g F u n d a m e n t a l T yp e s
S e c t i o n 1 9 .2. D e t e r m i n i n g C o m p o u n d T yp e s
S e c t i o n 1 9 .3 . I d e n t i f yi n g F u n c t i o n T yp e s
S e c t i o n 1 9 .4 . E n u m e r a t i o n C l a s s i f i c a t i o n w i t h O v e r l o a d R e s o l u t i o n
S e c t i o n 1 9 .5 . D e t e r m i n i n g C l a s s T yp e s
S e c t i o n 1 9 .6 . P u t t i n g I t A l l T o g e t h e r
S e c t i o n 1 9 .7 . A f t e r n o t e s

C h a p t e r 20 . S m a r t P o i n t e r s
S e c t i o n 20 .1 . H o l d e r s a n d T r u l e s
S e c t i o n 20 .2. R e f e r e n c e C o u n t i n g
S e c t i o n 20 .3 . A f t e r n o t e s

C h a p t e r 21 . T u p l e s
S e c t i o n 21 .1 . D u o s
S e c t i o n 21 .2. R e c u r s i v e D u o s
S e c t i o n 21 .3 . T u p l e C o n s t r u c t i o n
S e c t i o n 21 .4 . A f t e r n o t e s

C h a p t e r 22. F u n c t i o n O b j e c t s a n d C a l l b a c k s
S e c t i o n 22.1 . D i r e c t , I n d i r e c t , a n d I n l i n e C a l l s
S e c t i o n 22.2. P o i n t e r s a n d R e f e r e n c e s t o F u n c t i o n s
S e c t i o n 22.3 . P o i n t e r -t o -M e m b e r F u n c t i o n s
S e c t i o n 22.4 . C l a s s T yp e F u n c t o r s
S e c t i o n 22.5 . S p e c i f yi n g F u n c t o r s
S e c t i o n 22.6 . I n t r o s p e c t i o n
S e c t i o n 22.7 . F u n c t i o n O b j e c t C o m p o s i t i o n
 S e c t i o n 22.8 . V a l u e B i n d e r s
F u n c t o r O p e r a t io n s : A C o m p le t e I m p le m e n t a t io n
S e c t i o n 22.1 0 . A f t e r n o t e s

A p p e n d i x A . T h e O n e -D e f i n i t i o n R u l e
S e c t i o n A .1 . T r a n s l a t i o n U n i t s
S e c t i o n A .2. D e c l a r a t i o n s a n d D e f i n i t i o n s
S e c t i o n A .3 . T h e O n e -D e f i n i t i o n R u l e i n D e t a i l

A p p e n d ix B . O v e r lo a d R e s o lu t io n
S e c t i o n B .1 . W h e n D o e s O v e r l o a d R e s o l u t i o n K i c k I n ?
S e c t i o n B .2. S i m p l i f i e d O v e r l o a d R e s o l u t i o n
S e c t i o n B .3 . O v e r l o a d i n g D e t a i l s

B ib lio g r a p h y
N e w s g r o u p s
B o o k s a n d W e b S it e s

G lo s s a r y
Copyright

M any of th e des i g nati ons u s ed by m anu factu rers and s ellers to di s ti ng u i s h th ei r

p rodu cts are clai m ed as tradem ark s . W h ere th os e des i g nati ons ap p ear i n th i s
book , and A ddi s on-W es ley was aware of a tradem ark clai m , th e des i g nati ons
h av e been p ri nted wi th i ni ti al cap i tal letters or i n all cap i tals .

T h e au th ors and p u bli s h er h av e tak en care i n th e p rep arati on of th i s book , bu t

m ak e no ex p res s ed or i m p li ed warranty of any k i nd and as s u m e no res p ons i bi li ty
for errors or om i s s i ons . N o li abi li ty i s as s u m ed for i nci dental or cons eq u enti al
dam ag es i n connecti on wi th or ari s i ng ou t of th e u s e of th e i nform ati on or
p rog ram s contai ned h erei n.

T h e p u bli s h er offers di s cou nts on th i s book wh en ordered i n q u anti ty for s p eci al

s ales . F or m ore i nform ati on, p leas e contact:

U .S. C orp orate and G ov ernm ent Sales

(8 00) 3 8 2-3 4 19

corp s ales @ p ears ontech g rou p .com

F or s ales ou ts i de of th e U ni ted States , p leas e contact:

I nternati onal Sales

(3 17 ) 5 8 1-3 7 9 3

i nternati onal@ p ears ontech g rou p .com

V i s i t A ddi s on-W es ley on th e W eb: www.awp rofes s i onal.com

L i b r ar y of Con g r ess Catalog i n g -i n -Pu b li c ati on D ata

V andev oorde, D av i d.

C + + tem p lates : th e com p lete g u i de / D av i d V andev oorde, N i colai M . J os u tti s .

p . cm .

I nclu des bi bli og rap h i cal references and i ndex .

0-201-7 3 4 8 4 -2

1. M i cros oft V i s u al C + + . 2. C + + (C om p u ter p rog ram lang u ag e) 3 . Standard

tem p late li brary. I . J os u tti s , N i colai M . I I . T i tle.

Q A 7 6.7 3 .C 15 3 V 3 7 2003

005 .26' 8 —dc21 2002027 9 3 3

C op yri g h t © 2003 by P ears on E du cati on, I nc.

A ll ri g h ts res erv ed. N o p art of th i s p u bli cati on m ay be rep rodu ced, s tored i n a
retri ev al s ys tem , or trans m i tted, i n any form , or by any m eans , electroni c,
m ech ani cal, p h otocop yi ng , recordi ng , or oth erwi s e, wi th ou t th e p ri or cons ent of
th e p u bli s h er. P ri nted i n th e U ni ted States of A m eri ca. P u bli s h ed s i m u ltaneou s ly
i n C anada.

F or i nform ati on on obtai ni ng p erm i s s i on for u s e of m ateri al from th i s work , p leas e

s u bm i t a wri tten req u es t to:

P ears on E du cati on, I nc.

R i g h ts and C ontracts D ep artm ent

7 5 A rli ng ton Street, Su i te 3 00

B os ton, M A 02116

F ax : (617 ) 8 4 8 -7 04 7

T ex t p ri nted on recycled p ap er

1 2 3 4 5 6 7 8 9 10—M A —0605 04 03 02

F i rs t p ri nti ng , N ov em ber 2002

Dedication

To K ar i n a

—D av i d

To those w ho help an d lov e

—Ni c o
Preface

T h e i dea of tem p lates i n C + + i s m ore th an ten years old. C + + tem p lates were
already docu m ented i n 19 9 0 i n th e " A nnotated C + + R eference M anu al" or s o-
called " A R M " (s ee [E lli s Strou s tru p A R M ] ) and th ey h ad been des cri bed before th at
i n m ore s p eci ali z ed p u bli cati ons . H owev er, well ov er a decade later we fou nd a
dearth of li teratu re th at concentrates on th e fu ndam ental concep ts and adv anced
tech ni q u es of th i s fas ci nati ng , com p lex , and p owerfu l C + + featu re. W e wanted to
addres s th i s i s s u e and deci ded to wri te the book abou t tem p lates (wi th p erh ap s a
s li g h t lack of h u m i li ty).

H owev er, we ap p roach ed th e tas k wi th di fferent back g rou nds and wi th di fferent
i ntenti ons . D av i d, an ex p eri enced com p i ler i m p lem enter and m em ber of th e C + +
Standard C om m i ttee C ore L ang u ag e W ork i ng G rou p , was i nteres ted i n an ex act
and detai led des cri p ti on of all th e p ower (and p roblem s ) of tem p lates . N i co, an
" ordi nary" ap p li cati on p rog ram m er and m em ber of th e C + + Standard C om m i ttee
L i brary W ork i ng G rou p , was i nteres ted i n u nders tandi ng all th e tech ni q u es of
tem p lates i n a way th at h e cou ld u s e and benefi t from th em . I n addi ti on, we both
wanted to s h are th i s k nowledg e wi th you , th e reader, and th e wh ole com m u ni ty
to h elp to av oi d fu rth er m i s u nders tandi ng , confu s i on, or ap p reh ens i on.

A s a cons eq u ence, you wi ll s ee both concep tu al i ntrodu cti ons wi th day-to-day

ex am p les and detai led des cri p ti ons of th e ex act beh av i or of tem p lates . Starti ng
from th e bas i c p ri nci p les of tem p lates and work i ng u p to th e " art of tem p late
p rog ram m i ng , " you wi ll di s cov er (or redi s cov er) tech ni q u es s u ch as s tati c
p olym orp h i s m , p oli cy clas s es , m etap rog ram m i ng , and ex p res s i on tem p lates . Y ou
wi ll als o g ai n a deep er u nders tandi ng of th e C + + s tandard li brary, i n wh i ch
alm os t all code i nv olv es tem p lates .

W e learned a lot and we h ad m u ch fu n wh i le wri ti ng th i s book . W e h op e you wi ll

h av e th e s am e ex p eri ence wh i le readi ng i t. E nj oy!
Acknowledgments

T h i s book p res ents i deas , concep ts , s olu ti ons , and ex am p les from m any s ou rces .
W e' d li k e to th ank all th e p eop le and com p ani es wh o h elp ed and s u p p orted u s
du ri ng th e p as t few years .

F i rs t, we' d li k e to th ank all th e rev i ewers and ev eryone els e wh o g av e u s th ei r

op i ni on on early m anu s cri p ts . T h es e p eop le endow th e book wi th a q u ali ty i t
wou ld nev er h av e h ad wi th ou t th ei r i np u t. T h e rev i ewers for th i s book were K yle
B laney, T h om as G s ch wi nd, D enni s M ancl, P atri ck M c K i llen, and J an C h ri s ti aan
v an W i nk el. Sp eci al th ank s to D i etm ar K ü h l, wh o m eti cu lou s ly rev i ewed and
edi ted th e wh ole book . H i s feedback was an i ncredi ble contri bu ti on to th e q u ali ty
of th i s book .

W e' d als o li k e to th ank all th e p eop le and com p ani es wh o g av e u s th e op p ortu ni ty

to tes t ou r ex am p les on di fferent p latform s wi th di fferent com p i lers . M any th ank s
to th e E di s on D es i g n G rou p for th ei r g reat com p i ler and th ei r s u p p ort. I t was a
bi g h elp du ri ng th e s tandardi z ati on p roces s and th e wri ti ng of th i s book . M any
th ank s als o g o to all th e dev elop ers of th e free G N U and eg cs com p i lers (J as on
M erri ll was es p eci ally res p ons i v e), and to M i cros oft for an ev alu ati on v ers i on of
V i s u al C + + (J onath an C av es , H erb Su tter, and J as on Sh i rk were ou r contacts
th ere).

M u ch of th e ex i s ti ng " C + + wi s dom " was collecti v ely created by th e onli ne C + +

com m u ni ty. M os t of i t com es from th e m oderated U s enet g rou p s
comp.lang.c++.moderated and comp.std.c++. W e are th erefore es p eci ally
i ndebted to th e acti v e m oderators of th os e g rou p s , wh o k eep th e di s cu s s i ons
u s efu l and cons tru cti v e. W e als o m u ch ap p reci ate all th os e wh o ov er th e years
h av e tak en th e ti m e to des cri be and ex p lai n th ei r i deas for u s all to s h are.

T h e A ddi s on-W es ley team di d anoth er g reat j ob. W e are m os t i ndebted to D ebbi e
L afferty (ou r edi tor) for h er g entle p roddi ng , g ood adv i ce, and relentles s h ard
work i n s u p p ort of th i s book . T h ank s als o g o to T yrrell A lbau g h , B u nny A m es ,
M elani e B u ck , J acq u elyn D ou cette, C h anda L eary-C ou tu , C ath eri ne O h ala, and
M arty R abi nowi tz . W e' re g ratefu l as well to M ari na L ang , wh o fi rs t s p ons ored th i s
book wi th i n A ddi s on-W es ley. Su s an W i ner contri bu ted an early rou nd of edi ti ng
th at h elp ed s h ap e ou r later work .
Nico's Acknowledgments

M y fi rs t p ers onal th ank s g o wi th a lot of k i s s es to m y fam i ly: U lli , L u cas , A ni ca,

and F rederi c s u p p orted th i s book wi th a lot of p ati ence, cons i derati on, and
encou rag em ent.

I n addi ti on, I want to th ank D av i d. H i s ex p erti s e tu rned ou t to be i ncredi ble, bu t

h i s p ati ence was ev en better (s om eti m es I as k really s i lly q u es ti ons ). I t i s a lot of
fu n to work wi th h i m .
David's Acknowledgments

M y wi fe, K ari na, h as been i ns tru m ental i n th i s book com i ng to a conclu s i on, and I
am i m m ens ely g ratefu l for th e role th at s h e p lays i n m y li fe. W ri ti ng " i n you r
s p are ti m e" q u i ck ly becom es errati c wh en m any oth er acti v i ti es v i e for you r
s ch edu le. K ari na h elp ed m e to m anag e th at s ch edu le, tau g h t m e to s ay " no" i n
order to m ak e th e ti m e needed to m ak e reg u lar p rog res s i n th e wri ti ng p roces s ,
and abov e all was am az i ng ly s u p p orti v e of th i s p roj ect. I th ank G od ev ery day for
h er fri ends h i p and lov e.

I 'm als o trem endou s ly g ratefu l to h av e been able to work wi th N i co. B es i des h i s
di rectly v i s i ble contri bu ti ons to th e tex t, h i s ex p eri ence and di s ci p li ne m ov ed u s
from m y p i ti fu l doodli ng to a well-org ani z ed p rodu cti on.

J oh n " M r. T em p late" Sp i cer and Stev e " M r. O v erload" A dam cz yk are wonderfu l
fri ends and colleag u es , bu t i n m y op i ni on th ey are (tog eth er) als o th e u lti m ate
au th ori ty reg ardi ng th e core C + + lang u ag e. T h ey clari fi ed m any of th e tri ck i er
i s s u es des cri bed i n th i s book , and s h ou ld you fi nd an error i n th e des cri p ti on of a
C + + lang u ag e elem ent, i t i s alm os t certai nly attri bu table to m y fai li ng to cons u lt
wi th th em .

F i nally, I want to ex p res s m y ap p reci ati on to th os e wh o were s u p p orti v e of th i s

p roj ect wi th ou t neces s ari ly contri bu ti ng to i t di rectly (th e p ower of ch eer cannot
be u nders tated). F i rs t, m y p arents : T h ei r lov e for m e and th ei r encou rag em ent
m ade all th e di fference. A nd th en th ere are th e nu m erou s fri ends i nq u i ri ng : " H ow
i s th e book g oi ng ? " T h ey, too, were a s ou rce of encou rag em ent: M i ch ael
B eck m ann, B rett and J u li e B eene, J arran C arr, Si m on C h ang , H o and Sarah C h o,
C h ri s top h e D e D i nech i n, E wa D eelm an, N ei l E berle, Sas s an H az eg h i , V i k ram
K u m ar, J i m and L i nds ay L ong , R .J . M org an, M i k e P u ri tano, R ag u R ag h av endra,
J im and P h u ong Sh arp , G reg g V au g h n, and J oh n W i eg ley.
Chapter 1. About This Book

A lth ou g h tem p lates h av e been p art of C + + for well ov er a decade (and av ai lable
i n v ari ou s form s for alm os t as long ), th ey s ti ll lead to m i s u nders tandi ng , m i s u s e,
or controv ers y. A t th e s am e ti m e, th ey are i ncreas i ng ly fou nd to be p owerfu l
i ns tru m ents for th e dev elop m ent of cleaner, fas ter, and s m arter s oftware.
I ndeed, tem p lates h av e becom e th e corners tone of s ev eral new C + +
p rog ram m i ng p aradi g m s .

Y et we h av e fou nd th at m os t ex i s ti ng book s and arti cles are at bes t s u p erfi ci al i n

th ei r treatm ent of th e th eory and ap p li cati on of C + + tem p lates . E v en th os e few
book s th at do an ex cellent j ob of s u rv eyi ng v ari ou s tem p late-bas ed tech ni q u es
fai l to des cri be accu rately h ow th es e tech ni q u es are s u p p orted by th e lang u ag e.
A s a res u lt, beg i nni ng and adv anced C + + p rog ram m ers ali k e are fi ndi ng
th em s elv es wres tli ng wi th tem p lates , attem p ti ng to deci de wh y th ei r code i s
h andled u nex p ectedly.

T h i s obs erv ati on was one of th e m ai n m oti v ati ons for u s to wri te th i s book .
H owev er, we both cam e u p wi th th e top i c i ndep endently and h ad s om ewh at
di s ti nct ap p roach es i n m i nd:

• D av i d' s g oal was to p rov i de a com p lete reference to th e detai ls of th e C + +

tem p late lang u ag e m ech ani s m and th e m aj or adv anced p rog ram m i ng
tech ni q u es th at tem p lates enable. H i s focu s was on p reci s i on and
com p letenes s .
• N i co' s i nteres t was to h av e a book th at h elp s h i m s elf and oth ers u s e
tem p lates i n th e day-to-day li fe of a p rog ram m er. T h i s i m p li es th at th e
book s h ou ld p res ent th e m ateri al i n an i ntu i ti v e m anner, wh i le deali ng wi th
th e p racti cal as p ects of tem p lates .

I n a s ens e, you cou ld s ee u s as a s ci enti s t-eng i neer p ai r: W e both deal wi th th e

s am e di s ci p li ne, bu t ou r em p h as i s i s s om ewh at di fferent (wi th m u ch ov erlap , of
cou rs e).

A ddi s on-W es ley brou g h t u s tog eth er and as a res u lt you g et wh at we th i nk i s a

s oli d com bi nati on of a carefu l C + + tem p late tu tori al wi th a detai led reference.
T h e tu tori al as p ect cov ers not only an i ntrodu cti on to th e lang u ag e elem ents , bu t
als o ai m s at dev elop i ng a s ens e for des i g n m eth ods th at lead to p racti cal
s olu ti ons . Si m i larly, th e book i s not only a reference for th e detai ls of C + +
tem p late s yntax and s em anti cs , bu t als o a com p endi u m of well-k nown and les s er
k nown i di om s and tech ni q u es .
1.1 What You Should Know Before Reading This Book

T o g et th e m os t from th i s book you s h ou ld already k now C + + : W e des cri be th e

detai ls of a p arti cu lar lang u ag e featu re, not th e fu ndam entals of th e lang u ag e
i ts elf. Y ou s h ou ld be fam i li ar wi th th e concep ts of clas s es and i nh eri tance, and
you s h ou ld be able to wri te C + + p rog ram s u s i ng com p onents s u ch as I O s tream s
and contai ners from th e C + + s tandard li brary. I n addi ti on, we rev i ew m ore s u btle
i s s u es as th e need ari s es , ev en wh en s u ch i s s u es aren' t di rectly related to
tem p lates . T h i s ens u res th at th e tex t i s acces s i ble to ex p erts and i nterm edi ate
p rog ram m ers ali k e.

W e deal m os tly wi th th e C + + lang u ag e as s tandardi z ed i n 19 9 8 (s ee

[Standard9 8 ] ), p lu s th e clari fi cati ons p rov i ded by th e C + + Standardi z ati on
C om m i ttee i n i ts fi rs t tec hn i c al c or r i g en d u m (s ee [Standard02] ). I f you feel you r
u nders tandi ng of th e bas i cs of C + + i s ru s ty or ou t-of-date, we recom m end
[Strou s tru p C + + P L ] , [J os u tti s O O P ] , and [J os u tti s StdL i b] to refres h you r
k nowledg e. T h es e book s are ex cellent i ntrodu cti ons to th e m odern lang u ag e and
i ts s tandard li brary. A ddi ti onal p u bli cati ons are li s ted i n A p p endi x B .3 .5 .
1.2 Overall Structure of the Book

O u r g oal i s to p rov i de th e i nform ati on neces s ary for s tarti ng to u s e tem p lates and
benefi t from th ei r p ower, as well as to p rov i de i nform ati on th at wi ll enable
ex p eri enced p rog ram m ers to p u s h th e li m i ts of th e s tate-of-th e-art. T o ach i ev e
th i s , we deci ded to org ani z e ou r tex t i n par ts:

• P art I i ntrodu ces th e bas i c concep ts u nderlyi ng tem p lates . I t i s wri tten i n a
tu tori al s tyle.
• P art I I p res ents th e lang u ag e detai ls and i s a h andy reference to tem p late-
related cons tru cts .
• P art I I I ex p lai ns fu ndam ental des i g n tech ni q u es s u p p orted by C + +
tem p lates . T h ey rang e from near-tri v i al i deas to s op h i s ti cated i di om s th at
m ay not h av e been p u bli s h ed els ewh ere.
• P art I V bu i lds on th e p rev i ou s two p arts and adds a di s cu s s i on of v ari ou s
p op u lar ap p li cati ons for tem p lates .

E ach of th es e p arts cons i s ts of s ev eral ch ap ters . I n addi ti on, we p rov i de a few

ap p endi x es th at cov er m ateri al not ex clu s i v ely related to tem p lates (for ex am p le,
an ov erv i ew of ov erload res olu ti on i n C + + ).

T h e ch ap ters of P art I are m eant to be read i n s eq u ence. F or ex am p le, C h ap ter 3

bu i lds on th e m ateri al cov ered i n C h ap ter 2. I n th e oth er p arts , h owev er, th e
connecti on between ch ap ters i s cons i derably loos er. F or ex am p le, i t wou ld be
enti rely natu ral to read th e ch ap ter abou t f u n c tor s (C h ap ter 22) before th e
ch ap ter abou t smar t poi n ter s (C h ap ter 20).

L as t, we p rov i de a rath er com p lete i ndex th at encou rag es addi ti onal ways to read
th i s book ou t of s eq u ence.
1.3 How to Read This Book

I f you are a C + + p rog ram m er wh o wants to learn or rev i ew th e concep ts of

tem p lates , carefu lly read P art I , T h e B as i cs . E v en i f you ' re q u i te fam i li ar wi th
tem p lates already, i t m ay h elp to s k i m th rou g h th i s p art q u i ck ly to fam i li ari z e
you rs elf wi th th e s tyle and term i nolog y th at we u s e. T h i s p art als o cov ers s om e of
th e log i s ti cal as p ects of org ani z i ng you r s ou rce code wh en i t contai ns tem p lates .

D ep endi ng on you r p referred learni ng m eth od, you m ay deci de to abs orb th e
m any detai ls of tem p lates i n P art I I , or i ns tead you cou ld read abou t p racti cal
codi ng tech ni q u es i n P art I I I (and refer back to P art I I for th e m ore s u btle
lang u ag e i s s u es ). T h e latter ap p roach i s p robably p arti cu larly u s efu l i f you bou g h t
th i s book wi th concrete day-to-day ch alleng es i n m i nd. P art I V i s s om ewh at
s i m i lar to P art I I I , bu t th e em p h as i s i s on u nders tandi ng h ow tem p lates can
contri bu te to s p eci fi c ap p li cati ons rath er th an des i g n tech ni q u es . I t i s th erefore
p robably bes t to fam i li ari z e you rs elf wi th th e top i cs of P art I I I before delv i ng i nto
P art I V .

T h e ap p endi x es contai n m u ch u s efu l i nform ati on th at i s often referred to i n th e

m ai n tex t. W e h av e als o tri ed to m ak e th em i nteres ti ng i n th ei r own ri g h t.

I n ou r ex p eri ence, th e bes t way to learn s om eth i ng new i s to look at ex am p les .

T h erefore, you ' ll fi nd a lot of ex am p les th rou g h ou t th e book . Som e are j u s t a few
li nes of code i llu s trati ng an abs tract concep t, wh ereas oth ers are com p lete
p rog ram s th at p rov i de a concrete ap p li cati on of th e m ateri al. T h e latter k i nd of
ex am p les wi ll be i ntrodu ced by a C + + com m ent des cri bi ng th e fi le contai ni ng th e
p rog ram code. Y ou can fi nd th es e fi les at th e W eb s i te of th i s book at
h ttp ://www.j os u tti s .com /tm p lbook /.
1.4 Some Remarks About Programming Style

C p rog ram m ers u s e di fferent p rog ram m i ng s tyles , and s o do we: T h e u s u al

q u es ti ons abou t wh ere to p u t wh i tes p ace, deli m i ters (braces , p arenth es es ), and
s o forth cam e u p . W e tri ed to be cons i s tent i n g eneral, alth ou g h we occas i onally
m ak e conces s i ons to th e top i c at h and. F or ex am p le, i n tu tori al s ecti ons we m ay
p refer g enerou s u s e of wh i tes p ace and concrete nam es to h elp v i s u ali z e code,
wh ereas i n m ore adv anced di s cu s s i ons a m ore com p act s tyle cou ld be m ore
ap p rop ri ate.

W e do want to draw you r attenti on to one s li g h tly u ncom m on deci s i on reg ardi ng
th e declarati on of typ es , p aram eters , and v ari ables . C learly, s ev eral s tyles are
p os s i ble:

void foo (const int &x);

void foo (const int& x);
void foo (int const &x);
void foo (int const& x);

A lth ou g h i t i s a bi t les s com m on, we deci ded to u s e th e order int const rath er
th an const int for " cons tant i nteg er." W e h av e two reas ons for th i s . F i rs t, i t
p rov i des for an eas i er ans wer to th e q u es ti on, " W hat i s cons tant? " I t' s always
wh at i s i n front of th e const q u ali fi er. I ndeed, alth ou g h

const int N = 100;

i s eq u i v alent to

int const N = 100;

th ere i s no eq u i v alent form for

int* const bookmark; // the pointer cannot change, but the

// value pointed to can change

th at wou ld p lace th e const q u ali fi er before th e p oi nter op erator *. I n th i s

ex am p le, i t i s th e p oi nter i ts elf th at i s cons tant, not th e int to wh i ch i t p oi nts .

O u r s econd reas on h as to do wi th a s yntacti cal s u bs ti tu ti on p ri nci p le th at i s v ery

com m on wh en deali ng wi th tem p lates . C ons i der th e followi ng two typ e defi ni ti ons
[1]
[1]
:

[1]
N ote th at i n C a typ e defi ni ti on defi nes a " typ e ali as " rath er th an
a new typ e. F or ex am p le:

typedef int Length; // define Length as an alias for int

int i = 42;
Lengthl = 88;
i = l; // OK
l = i; // OK

typedef char* CHARS;

typedef CHARS const CPTR; // constant pointer to chars

T h e m eani ng of th e s econd declarati on i s p res erv ed wh en we tex tu ally rep lace

CHARS wi th wh at i t s tands for:

typedef char* const CPTR; // constant pointer to chars

H owev er, i f we wri te const b ef or e th e typ e i t q u ali fi es , th i s p ri nci p le does n' t

ap p ly. I ndeed, cons i der th e alternati v e to ou r fi rs t two typ e defi ni ti ons p res ented
earli er:

typedef char* CHARS;

typedef const CHARS CPTR; // constant pointer to chars

T ex tu ally rep laci ng CHARS res u lts i n a typ e wi th a di fferent m eani ng :

typedef const char* CPTR; // pointer to constant chars

T h e s am e obs erv ati on ap p li es to th e volatile s p eci fi er, of cou rs e.

R eg ardi ng wh i tes p aces , we deci ded to p u t th e s p ace between th e am p ers and and
th e p aram eter nam e:

void foo (int const& x);

B y doi ng th i s , we em p h as i z e th e s ep arati on between th e p aram eter typ e and th e

p aram eter nam e. T h i s i s adm i ttedly m ore confu s i ng for declarati ons s u ch as

char* a, b;

wh ere, accordi ng to th e ru les i nh eri ted from C , a i s a p oi nter bu t b i s an ordi nary

char. T o av oi d s u ch confu s i on, we s i m p ly av oi d declari ng m u lti p le enti ti es i n th i s
way.

T h i s i s not a book abou t th e C s tandard li brary, bu t we do m ak e u s e of th at

li brary i n s om e of ou r ex am p les . I n g eneral, we u s e th e C s p eci fi c h eaders (for
ex am p le, <iostream> rath er th an <stdio.h>). T h e ex cep ti on i s <stddef.h>.
W e u s e i t i ns tead of <cstddef> and th erefore do not q u ali fy size_t and
ptrdiff_t wi th th e std:: p refi x becau s e th i s i s s ti ll m ore p ortable and th ere i s
no adv antag e i n u s i ng std::size_t i ns tead of size_t.
1.5 The Standard versus Reality

T h eC + + s tandard h as been av ai lable s i nce late 19 9 8 . H owev er, i t was not u nti l
2002 th at a p u bli cally av ai lable com p i ler cou ld m ak e th e clai m to " conform fu lly
to th e s tandard." T h u s , com p i lers s ti ll di ffer i n th ei r s u p p ort of th e lang u ag e.
Sev eral wi ll com p i le m os t of th e code i n th i s book , bu t a few fai rly p op u lar
com p i lers m ay not be able to h andle m any of ou r ex am p les . W e often p res ent
alternati v e tech ni q u es th at m ay h elp cobble tog eth er a fu ll or p arti al s olu ti on for
th es e s u bs tandard C + + i m p lem entati ons , bu t s om e tech ni q u es are cu rrently
beyond th ei r reach . Sti ll, we ex p ect th at th i s p roblem wi ll larg ely be res olv ed as
p rog ram m ers ev erywh ere dem and s tandard s u p p ort from th ei r v endors .

E v en s o, th e C + + p rog ram m i ng lang u ag e i s li k ely to ev olv e as ti m e p as s es .

A lready th e ex p erts of th e C + + com m u ni ty (reg ardles s of wh eth er th ey
p arti ci p ate i n th e C + + Standardi z ati on C om m i ttee) are di s cu s s i ng v ari ou s ways to
i m p rov e th e lang u ag e, and s ev eral candi date i m p rov em ents affect tem p lates .
C h ap ter 13 p res ents s om e trends i n th i s area.
1.6 Example Code and Additional Informations

Y ou can acces s all ex am p le p rog ram s and fi nd m ore i nform ati on abou t th i s book
from i ts W eb s i te, wh i ch h as th e followi ng U R L :

h ttp ://www.j os u tti s .com /tm p lbook

A ls o, you can fi nd a lot of addi ti onal i nform ati on abou t th i s top i c at D av i d

V andev oorde' s W eb s i te at h ttp ://www.v andev oorde.com /T em p lates and on th e
W eb i n g eneral. See th e B i bli og rap h y on p ag e 4 9 9 for s u g g es ti ons on wh ere to
s tart.
1.7 Feedback

W e welcom e you r cons tru cti v e i np u t—both th e neg ati v e and th e p os i ti v e. W e

work ed v ery h ard to bri ng you wh at we h op e you ' ll fi nd to be an ex cellent book .
H owev er, at s om e p oi nt we h ad to s top wri ti ng , rev i ewi ng , and tweak i ng s o we
cou ld " releas e th e p rodu ct." Y ou m ay th erefore fi nd errors , i ncons i s tenci es , and
p res entati ons th at cou ld be i m p rov ed, or top i cs th at are m i s s i ng altog eth er. Y ou r
feedback g i v es u s a ch ance to i nform all readers th rou g h th e book ' s W eb s i te and
to i m p rov e any s u bs eq u ent edi ti ons .

T h e bes t way to reach u s i s by e-m ai l:

tm p lbook @ j os u tti s .com

B e s u re to ch eck th e book ' s W eb s i te for th e cu rrently k nown errata before

s u bm i tti ng rep orts .

M any th ank s .
Part I: The Basics

T h i s p art i ntrodu ces th e g eneral concep t and lang u ag e featu res of

C + + tem p lates . I t s tarts wi th a di s cu s s i on of th e g eneral g oals and
concep ts by s h owi ng ex am p les of fu ncti on tem p lates and clas s
tem p lates . I t conti nu es wi th s om e addi ti onal fu ndam ental tem p late
tech ni q u es s u ch as nontyp e tem p late p aram eters , th e k eyword
typename, and m em ber tem p lates . I t ends wi th s om e g eneral
h i nts reg ardi ng th e u s e and ap p li cati on of tem p lates i n p racti ce.

T h i s i ntrodu cti on to tem p lates i s als o p arti ally u s ed i n N i colai M .

J os u tti s ' s book O b j ec t-O r i en ted Pr og r ammi n g i n C++, p u bli s h ed by
J oh n W i ley and Sons L td, I SB N 0-4 7 0-8 4 3 9 9 -3 . T h i s book teach es
all lang u ag e featu res of C + + and th e C + + s tandard li brary and
ex p lai ns th ei r p racti cal u s ag e i n a s tep -by-s tep tu tori al.

Why Templates?

C + + req u i res u s to declare v ari ables , fu ncti ons , and m os t oth er

k i nds of enti ti es u s i ng s p eci fi c typ es . H owev er, a lot of code look s
th e s am e for di fferent typ es . E s p eci ally i f you i m p lem ent
alg ori th m s , s u ch as q u i c k sor t, or i f you i m p lem ent th e beh av i or of
data s tru ctu res , s u ch as a li nk ed li s t or a bi nary tree for di fferent
typ es , th e code look s th e s am e des p i te th e typ e u s ed.

I f you r p rog ram m i ng lang u ag e does n' t s u p p ort a s p eci al lang u ag e

featu re for th i s , you only h av e bad alternati v es :

1. Y o u c a n im p le m e n t t h e s a m e b e h a v io r a g a in a n d a g a in fo r e a c h ty p e t h a t n e e d s
th is b e h a v io r .
2 . Y o u c a n w r i t e g e n e r a l c o d e f o r a c o m m o n b a s e t y p e s u c h a s Object o r void*.
3 . Y o u c a n u s e s p e c ia l p r e p r o c e s s o r s .

I f you com e from C , J av a, or s i m i lar lang u ag es , you p robably h av e

done s om e or all of th i s before. H owev er, each of th es e ap p roach es
h as i ts drawback s :

1. If y o u i m p l e m e n t a b e h a v i o r a g a i n a n d a g a in , y o u r e in v e n t t h e w h e e l.Y o u m a k e
th e s a m e m is t a k e s a n d y o u t e n d to a v o id c o m p lic a te d b u t b e t t e r a lg o r ith m s
b e c a u s e t h e y le a d t o e v e n m o r e m is ta k e s .
2 . If y o u w r i t e g e n e r a l c o d e f o r a c o m m o n b a s e c l a s s y o u l o s e t h e b e n e f i t o f t y p e
c h e c k i n g . In a d d i t i o n , c l a s s e s m a y b e r e q u i r e d t o b e d e r i v e d f r o m s p e c ia l b a s e
c la s s e s , w h ic h m a k e s it m o r e d iffic u lt to m a in ta in y o u r c o d e .
3 . If y o u u s e a s p e c i a l p r e p r o c e s s o r s u c h a s t h e C / C + + p r e p r o c e s s o r , y o u lo s e th e
a d v a n t a g e o f fo r m a tt e d s o u r c e c o d e .C o d e is r e p la c e d b y s o m e " s tu p id t e x t
 r e p la c e m e n t m e c h a n is m " t h a t h a s n o id e a o f s c o p e a n d ty p e s .

T em p lates are a s olu ti on to th i s p roblem wi th ou t th es e drawback s .

T h ey are fu ncti ons or clas s es th at are wri tten for one or m ore typ es
not yet s p eci fi ed. W h en you u s e a tem p late, you p as s th e typ es as
arg u m ents , ex p li ci tly or i m p li ci tly. B ecau s e tem p lates are lang u ag e
featu res , you h av e fu ll s u p p ort of typ e ch eck i ng and s cop e.

I n today' s p rog ram s , tem p lates are u s ed a lot. F or ex am p le, i ns i de

th e C + + s tandard li brary alm os t all code i s tem p late code. T h e
li brary p rov i des s ort alg ori th m s to s ort obj ects and v alu es of a
s p eci fi ed typ e, data s tru ctu res (s o-called c on tai n er c lasses) to
m anag e elem ents of a s p eci fi ed typ e, s tri ng s for wh i ch th e typ e of
a ch aracter i s p aram eteri z ed, and s o on. H owev er, th i s i s only th e
beg i nni ng . T em p lates als o allow u s to p aram eteri z e beh av i or, to
op ti m i z e code, and to p aram eteri z e i nform ati on. T h i s i s cov ered i n
later ch ap ters . L et' s fi rs t s tart wi th s om e s i m p le tem p lates .
Chapter 2. Function Templates

T h i s ch ap ter i ntrodu ces fu ncti on tem p lates . F u ncti on tem p lates are fu ncti ons th at
are p aram eteri z ed s o th at th ey rep res ent a fam i ly of fu ncti ons .
2.1 A First Look at Function Templates

F u ncti on tem p lates p rov i de a fu ncti onal beh av i or th at can be called for di fferent
typ es . I n oth er words , a fu ncti on tem p late rep res ents a fam i ly of fu ncti ons . T h e
rep res entati on look s a lot li k e an ordi nary fu ncti on, ex cep t th at s om e elem ents of
th e fu ncti on are left u ndeterm i ned: T h es e elem ents are p aram eteri z ed. T o
i llu s trate, let' s look at a s i m p le ex am p le.

2.1.1 Defining the Template

T h e followi ng i s a fu ncti on tem p late th at retu rns th e m ax i m u m of two v alu es :

// basics/max.hpp

template <typename T>

inline T const& max (T const& a, T const& b)
{
// if a < b then use b else use a
return a<b?b:a;
}

T h i s tem p late defi ni ti on s p eci fi es a fam i ly of fu ncti ons th at retu rns th e m ax i m u m

of two v alu es , wh i ch are p as s ed as fu ncti on p aram eters a and b. T h e typ e of
th es e p aram eters i s left op en as template par ameter T. A s s een i n th i s ex am p le,
tem p late p aram eters m u s t be annou nced wi th s yntax of th e followi ng form :

template < comma-separated-list-of-parameters >

I n ou r ex am p le, th e li s t of p aram eters i s typename T. N ote h ow th e les s -th an

and th e g reater-th an s ym bols are u s ed as brack ets ; we refer to th es e as an g le
b r ac k ets. T h e k eyword typename i ntrodu ces a s o-called ty pe par ameter . T h i s i s
by far th e m os t com m on k i nd of tem p late p aram eter i n C + + p rog ram s , bu t oth er
p aram eters are p os s i ble, and we di s cu s s th em later (s ee C h ap ter 4 ).

H ere, th e typ e p aram eter i s T. Y ou can u s e any i denti fi er as a p aram eter nam e,
bu t u s i ng T i s th e conv enti on. T h e typ e p aram eter rep res ents an arbi trary typ e
th at i s s p eci fi ed by th e caller wh en th e caller calls th e fu ncti on. Y ou can u s e any
typ e (fu ndam ental typ e, clas s , and s o on) as long as i t p rov i des th e op erati ons
th at th e tem p late u s es . I n th i s cas e, typ e T h as to s u p p ort op erator < becau s e a
and b are com p ared u s i ng th i s op erator.

F or h i s tori cal reas ons , you can als o u s e class i ns tead of typename to defi ne a
typ e p aram eter. T h e k eyword typename cam e relati v ely late i n th e ev olu ti on of
th e C + + lang u ag e. P ri or to th at, th e k eyword class was th e only way to
i ntrodu ce a typ e p aram eter, and th i s rem ai ns a v ali d way to do s o. H ence, th e
tem p late max() cou ld be defi ned eq u i v alently as follows :

template <class T>

inline T const& max (T const& a, T const& b)
{
// if a < b then use b else use a
return a<b?b:a;
}

Sem anti cally th ere i s no di fference i n th i s contex t. So, ev en i f you u s e class

h ere, an y typ e m ay be u s ed for tem p late arg u m ents . H owev er, becau s e th i s u s e
of class can be m i s leadi ng (not only clas s typ es can be s u bs ti tu ted for T), you
s h ou ld p refer th e u s e of typename i n th i s contex t. N ote als o th at u nli k e clas s
typ e declarati ons , th e k eyword struct cannot be u s ed i n p lace of typename
wh en declari ng typ e p aram eters .

2.1.2 Using the Template

T h e followi ng p rog ram s h ows h ow to u s e th e max() fu ncti on tem p late:

// basics/max.cpp

#include <iostream>
#include <string>
#include "max.hpp"

int main()
{
int i = 42;
std::cout << "max(7,i): " << ::max(7,i) << std::endl;

double f1 = 3.4;
double f2 = -6.7;
std::cout << "max(f1,f2): " << ::max(f1,f2) << std::endl;

std::string s1 = "mathematics";
std::string s2 = "math";
std::cout << "max(s1,s2): " << ::max(s1,s2) << std::endl;
}

I ns i de th e p rog ram , max() i s called th ree ti m es : once for two ints , once for two
doubles , and once for two std::strings . E ach ti m e, th e m ax i m u m is
com p u ted. A s a res u lt, th e p rog ram h as th e followi ng ou tp u t:

max(7,i): 42
max(f1,f2): 3.4
max(s1,s2): mathematics
N ote th at each call of th e max() tem p late i s q u ali fi ed wi th ::. T h i s i s to m ak e
s u re th at ou r max() tem p late i s fou nd i n th e g lobal nam es p ace. T h ere i s als o an
std::max() tem p late i n th e s tandard li brary, wh i ch u nder s om e ci rcu m s tances
m ay be called or m ay lead to am bi g u i ty. [1]

[1]
F or ex am p le, i f one arg u m ent typ e i s defi ned i n nam es p ace std
(s u ch as s tri ng s ), accordi ng to th e look u p ru les of C + + , both th e
g lobal and th e std max() tem p late are fou nd.

N orm ally, tem p lates aren' t com p i led i nto s i ng le enti ti es th at can h andle any typ e.
I ns tead, di fferent enti ti es are g enerated from th e tem p late for ev ery typ e for
wh i ch th e tem p late i s u s ed. [2 ]
T h u s , max() i s com p i led for each of th es e th ree
typ es . F or ex am p le, th e fi rs t call of max()

[2 ]
T h e " one-enti ty-fi ts -all" alternati v e i s concei v able bu t rare i n
p racti ce. A ll lang u ag e ru les are bas ed on th e concep t th at di fferent
enti ti es are g enerated.

int i = 42;
… max(7,i) …

u s es th e fu ncti on tem p late wi th int as tem p late p aram eter T. T h u s , i t h as th e

s em anti cs of calli ng th e followi ng code:

inline int const& max (int const& a, int const& b)

{
// if a < b then use b else use a
return a<b?b:a;
}

T h e p roces s of rep laci ng tem p late p aram eters by concrete typ es i s called
i n stan ti ati on . I t res u lts i n an i n stan c e of a tem p late. U nfortu nately, th e term s
i n stan c e and i n stan ti ate are u s ed i n a di fferent contex t i n obj ect-ori ented
p rog ram m i ng —nam ely, for a concrete obj ect of a clas s . H owev er, becau s e th i s
book i s abou t tem p lates , we u s e th i s term for th e " u s e" of tem p lates u nles s
oth erwi s e s p eci fi ed.

N ote th at th e m ere u s e of a fu ncti on tem p late can tri g g er s u ch an i ns tanti ati on

p roces s . T h ere i s no need for th e p rog ram m er to req u es t th e i ns tanti ati on
s ep arately.

Si m i larly, th e oth er calls of max() i ns tanti ate th e max tem p late for double and
std::string as i f th ey were declared and i m p lem ented i ndi v i du ally:

const double& max (double const&, double const&);

const std::string& max (std::string const&, std::string const&);

A n attem p t to i ns tanti ate a tem p late for a typ e th at does n' t s u p p ort all th e
op erati ons u s ed wi th i n i t wi ll res u lt i n a com p i le-ti m e error. F or ex am p le:

std::complex<float> c1, c2; // doesn't provide operator <

…
max(c1,c2); // ERROR at compile time

T h u s , tem p lates are com p i led twi ce:

1. W ith o u t in s t a n t ia tio n , th e t e m p la te c o d e its e lf is c h e c k e d fo r c o r r e c t s y n t a x .S y n t a x e r r o r s a r e

d is c o v e r e d , s u c h a s m is s in g s e m ic o lo n s .
2 . A t t h e t i m e o f i n s t a n t i a t i o n , t h e t e m p l a t e c o d e i s c h e c k e d t o e n s u r e t h a t a l l c a l l s a r e v a l i d . In v a l i d
c a lls a r e d is c o v e r e d , s u c h a s u n s u p p o r t e d f u n c t io n c a lls .

T h i s leads to an i m p ortant p roblem i n th e h andli ng of tem p lates i n p racti ce: W h en

a fu ncti on tem p late i s u s ed i n a way th at tri g g ers i ts i ns tanti ati on, a com p i ler wi ll
(at s om e p oi nt) need to s ee th at tem p late' s defi ni ti on. T h i s break s th e u s u al
com p i le and li nk di s ti ncti on for ordi nary fu ncti ons , wh en th e declarati on of a
fu ncti on i s s u ffi ci ent to com p i le i ts u s e. M eth ods of h andli ng th i s p roblem are
di s cu s s ed i n C h ap ter 6. F or th e m om ent, let' s tak e th e s i m p les t ap p roach : E ach
tem p late i s i m p lem ented i ns i de a h eader fi le by u s i ng i nli ne fu ncti ons .
2.2 Argument Deduction

W h en we call a fu ncti on tem p late s u ch as max() for s om e arg u m ents , th e

tem p late p aram eters are determ i ned by th e arg u m ents we p as s . I f we p as s two
ints to th e p aram eter typ es T const&, th e C + + com p i ler m u s t conclu de th at T
m u s t be int. N ote th at no au tom ati c typ e conv ers i on i s allowed h ere. E ach T
m u s t m atch ex actly. F or ex am p le:

template <typename T>

inline T const& max (T const& a, T const& b);
…
max(4,7) // OK: T is int for both arguments
max(4,4.2) // ERROR: first T is int, second T is double

T h ere are th ree ways to h andle s u ch an error:

1. C a s t t h e a r g u m e n t s s o t h a t t h e y b o t h m a tc h :
2.
max(static_cast<double>(4),4.2) // OK

3 . S p e c ify ( o r q u a lify ) e x p lic it ly t h e t y p e o f T :

4.
max<double>(4,4.2) // OK

5 . S p e c ify th a t t h e p a r a m e t e r s m a y h a v e d iffe r e n t t y p e s .

F or a detai led di s cu s s i on of th es e top i cs , s ee th e nex t s ecti on.

2.3 Template Parameters

F u ncti on tem p lates h av e two k i nds of p aram eters :

1. Template parameters, w h i c h a r e d e c l a r e d i n a n g l e b r a c k e t s b e f o r e t h e f u n c t i o n t e m p l a t e n a m e :
2.
template <typename T> // T is template parameter

3 . C all parameters, w h i c h a r e d e c l a r e d i n p a r e n t h e s e s a f t e r t h e f u n c t i o n t e m p l a t e n a m e :
4.
… max (T const& a, T const& b) // a and b are call parameters

Y ou m ay h av e as m any tem p late p aram eters as you li k e. H owev er, i n fu ncti on

tem p lates (u nli k e clas s tem p lates ) no defau lt tem p late arg u m ents can be
s p eci fi ed. [3 ]
F or ex am p le, you cou ld defi ne th e max() tem p late for call
p aram eters of two di fferent typ es :

[3 ]
T h i s res tri cti on i s m ai nly th e res u lt of a h i s tori cal g li tch i n th e
dev elop m ent of fu ncti on tem p lates . T h ere are p robably no tech ni cal
h i ndrances to i m p lem enti ng s u ch a featu re i n m odern C + +
com p i lers , and i n th e fu tu re i t wi ll p robably be av ai lable (s ee
Secti on 13 .3 on p ag e 207 ).

template <typename T1, typename T2>

inline T1 max (T1 const& a, T2 const& b)
{
return a < b ? b : a;
}
…
max(4,4.2) // OK, but type of first argument defines return type

T h i s m ay ap p ear to be a g ood m eth od to enable p as s i ng two call p aram eters of

di fferent typ es to th e max() tem p late, bu t i n th i s ex am p le i t h as drawback s . T h e
p roblem i s th at th e retu rn typ e m u s t be declared. I f you u s e one of th e p aram eter
typ es , th e arg u m ent for th e oth er p aram eter m i g h t g et conv erted to th i s typ e,
reg ardles s of th e caller' s i ntenti on. C + + does not p rov i de a m eans to s p eci fy
ch oos i ng " th e m ore p owerfu l typ e" (h owev er, you can p rov i de th i s featu re by
s om e tri ck y tem p late p rog ram m i ng , s ee Secti on 15 .2.4 on p ag e 27 1). T h u s ,
dep endi ng on th e call arg u m ent order th e m ax i m u m of 4 2 and 66.66 m i g h t be
th e double 66.66 or th e int 66. A noth er drawback i s th at conv erti ng th e typ e of
th e s econd p aram eter i nto th e retu rn typ e creates a new, local tem p orary obj ect.
A s a cons eq u ence, you cannot retu rn th e res u lt by reference. [4 ]
I n ou r ex am p le,
th erefore, th e retu rn typ e h as to be T1 i ns tead of T1 const&.

Y ou are not allowed to retu rn v alu es by reference i f th ey are

[4 ]

local to a fu ncti on becau s e you ' d retu rn s om eth i ng th at does n' t

 ex i s t wh en th e p rog ram leav es th e s cop e of th i s fu ncti on.

B ecau s e th e typ es of th e call p aram eters are cons tru cted from th e tem p late
p aram eters , tem p late and call p aram eters are u s u ally related. W e call th i s
concep t f u n c ti on template ar g u men t d ed u c ti on . I t allows you to call a fu ncti on
tem p late as you wou ld an ordi nary fu ncti on.

H owev er, as m enti oned earli er, you can i ns tanti ate a tem p late ex p li ci tly for
certai n typ es :

template <typename T>

inline T const& max (T const& a, T const& b);
…
max<double>(4,4.2) // instantiate T as double

I n cas es wh en th ere i s no connecti on between tem p late and call p aram eters and
wh en tem p late p aram eters cannot be determ i ned, you m u s t s p eci fy th e tem p late
arg u m ent ex p li ci tly wi th th e call. F or ex am p le, you can i ntrodu ce a th i rd tem p late
arg u m ent typ e to defi ne th e retu rn typ e of a fu ncti on tem p late:

template <typename T1, typename T2, typename RT>

inline RT max (T1 const& a, T2 const& b);

H owev er, tem p late arg u m ent dedu cti on does not m atch u p retu rn typ es , [5 ]
and
RT does not ap p ear i n th e typ es of th e fu ncti on call p aram eters . T h erefore, RT
cannot be dedu ced. A s a cons eq u ence, you h av e to s p eci fy th e tem p late
arg u m ent li s t ex p li ci tly. F or ex am p le:

[5 ]
D edu cti on can be s een as p art of ov erload res olu ti on—a p roces s
th at i s not bas ed on s electi on of retu rn typ es ei th er. T h e s ole
ex cep ti on i s th e retu rn typ e of conv ers i on op erator m em bers .

template <typename T1, typename T2, typename RT>

inline RT max (T1 const& a, T2 const& b);
…
max<int,double,double>(4,4.2) // OK, but tedious

So far, we h av e look ed at cas es i n wh i ch ei th er all or none of th e fu ncti on

tem p late arg u m ents were m enti oned ex p li ci tly. A noth er ap p roach i s to s p eci fy
only th e fi rs t arg u m ents ex p li ci tly and to allow th e dedu cti on p roces s to deri v e
th e res t. I n g eneral, you m u s t s p eci fy all th e arg u m ent typ es u p to th e las t
arg u m ent typ e th at cannot be determ i ned i m p li ci tly. T h u s , i f you ch ang e th e
order of th e tem p late p aram eters i n ou r ex am p le, th e caller needs to s p eci fy only
th e retu rn typ e:

template <typename RT, typename T1, typename T2>

inline RT max (T1 const& a, T2 const& b);
…
max<double>(4,4.2) // OK: return type is double

I n th i s ex am p le, th e call to max<double> ex p li ci tly s ets RT to double, bu t th e

p aram eters T1 and T2 are dedu ced to be int and double from th e arg u m ents .

N ote th at all of th es e m odi fi ed v ers i ons of max() don' t lead to s i g ni fi cant

adv antag es . F or th e one-p aram eter v ers i on you can already s p eci fy th e
p aram eter (and retu rn) typ e i f two arg u m ents of a di fferent typ e are p as s ed.
T h u s , i t' s a g ood i dea to k eep i t s i m p le and u s e th e one-p aram eter v ers i on of
max() (as we do i n th e followi ng s ecti ons wh en di s cu s s i ng oth er tem p late
i s s u es ).

See C h ap ter 11 for detai ls of th e dedu cti on p roces s .

2.4 Overloading Function Templates

L i k e ordi nary fu ncti ons , fu ncti on tem p lates can be ov erloaded. T h at i s , you can
h av e di fferent fu ncti on defi ni ti ons wi th th e s am e fu ncti on nam e s o th at wh en th at
nam e i s u s ed i n a fu ncti on call, a C + + com p i ler m u s t deci de wh i ch one of th e
v ari ou s candi dates to call. T h e ru les for th i s deci s i on m ay becom e rath er
com p li cated, ev en wi th ou t tem p lates . I n th i s s ecti on we di s cu s s ov erloadi ng wh en
tem p lates are i nv olv ed. I f you are not fam i li ar wi th th e bas i c ru les of ov erloadi ng
wi th ou t tem p lates , p leas e look at A p p endi x B , wh ere we p rov i de a reas onably
detai led s u rv ey of th e ov erload res olu ti on ru les .

T h e followi ng s h ort p rog ram i llu s trates ov erloadi ng a fu ncti on tem p late:

// basics/max2.cpp

// maximum of two int values

inline int const& max (int const& a, int const& b)
{
return a<b?b:a;
}

// maximum of two values of any type

template <typename T>
inline T const& max (T const& a, T const& b)
{
return a<b?b:a;
}

// maximum of three values of any type

template <typename T>
inline T const& max (T const& a, T const& b, T const& c)
{
return max (max(a,b), c);
}

int main()
{
::max(7, 42, 68); // calls the template for three arguments
::max(7.0, 42.0); // calls max<double> (by argument
deduction)
::max('a', 'b'); // calls max<char> (by argument deduction)
::max(7, 42); // calls the nontemplate for two ints
::max<>(7, 42); // calls max<int> (by argument deduction)
::max<double>(7, 42); // calls max<double> (no argument
deduction)
::max('a', 42.7); // calls the nontemplate for two ints
}

A s th i s ex am p le s h ows , a nontem p late fu ncti on can coex i s t wi th a fu ncti on

tem p late th at h as th e s am e nam e and can be i ns tanti ated wi th th e s am e typ e. A ll
oth er factors bei ng eq u al, th e ov erload res olu ti on p roces s norm ally p refers th i s
nontem p late ov er one g enerated from th e tem p late. T h e fou rth call falls u nder
th i s ru le:

max(7, 42) // both int values match the nontemplate function

perfectly

I f th e tem p late can g enerate a fu ncti on wi th a better m atch , h owev er, th en th e

tem p late i s s elected. T h i s i s dem ons trated by th e s econd and th i rd call of max():

max(7.0, 42.0) // calls the max<double> (by argument deduction)

max('a', 'b'); // calls the max<char> (by argument deduction)

I t i s als o p os s i ble to s p eci fy ex p li ci tly an em p ty tem p late arg u m ent li s t. T h i s

s yntax i ndi cates th at only tem p lates m ay res olv e a call, bu t all th e tem p late
p aram eters s h ou ld be dedu ced from th e call arg u m ents :

max<>(7, 42) // calls max<int> (by argument deduction)

B ecau s e au tom ati c typ e conv ers i on i s not cons i dered for tem p lates bu t i s
cons i dered for ordi nary fu ncti ons , th e las t call u s es th e nontem p late fu ncti on
(wh i le 'a' and 42.7 both are conv erted to int):

max('a', 42.7) // only the nontemplate function allows different

argument types

A m ore u s efu l ex am p le wou ld be to ov erload th e m ax i m u m tem p late for p oi nters

and ordi nary C -s tri ng s :

// basics/max3.cpp

#include <iostream>
#include <cstring>
#include <string>

// maximum of two values of any type

template <typename T>
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}

// maximum of two pointers

template <typename T>
inline T* const& max (T* const& a, T* const& b)
{
return *a < *b ? b : a;
}
// maximum of two C-strings
inline char const* const& max (char const* const& a,
char const* const& b)
{
return std::strcmp(a,b) < 0 ? b : a;
}

int main ()
{
int a=7;
int b=42;
::max(a,b); // max() for two values of type int

std::string s="hey";
std::string t="you";
::max(s,t); // max() for two values of type std::string

int* p1 = &b;
int* p2 = &a;
::max(p1,p2); // max() for two pointers

char const* s1 = "David";

char const* s2 = "Nico";
::max(s1,s2); // max() for two C-strings
}

N ote th at i n all ov erloaded i m p lem entati ons , we p as s all arg u m ents by reference.
I n g eneral, i t i s a g ood i dea not to ch ang e m ore th an neces s ary wh en ov erloadi ng
fu ncti on tem p lates . Y ou s h ou ld li m i t you r ch ang es to th e nu m ber of p aram eters
or to s p eci fyi ng tem p late p aram eters ex p li ci tly. O th erwi s e, u nex p ected effects
m ay h ap p en. F or ex am p le, i f you ov erload th e max() tem p late, wh i ch p as s es th e
arg u m ents by reference, for two C -s tri ng s p as s ed by v alu e, you can' t u s e th e
th ree-arg u m ent v ers i on to com p u te th e m ax i m u m of th ree C -s tri ng s :

// basics/max3a.cpp

#include <iostream>
#include <cstring>
#include <string>

// maximum of two values of any type (call-by-reference)

template <typename T>
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}

// maximum of two C-strings (call-by-value)

inline char const* max (char const* a, char const* b)
{
return std::strcmp(a,b) < 0 ? b : a;
}

// maximum of three values of any type (call-by-reference)

template <typename T>
inline T const& max (T const& a, T const& b, T const& c)
{
return max (max(a,b), c); // error, if max(a,b) uses call-by-
value
}

int main ()
{
::max(7, 42, 68); // OK

const char* s1 = "frederic";

const char* s2 = "anica";
const char* s3 = "lucas";
::max(s1, s2, s3); // ERROR

T h e p roblem i s th at i f you call max() for th ree C -s tri ng s , th e s tatem ent

return max (max(a,b), c);

becom es an error. T h i s i s becau s e for C -s tri ng s , max(a,b) creates a new,

tem p orary local v alu e th at m ay be retu rned by th e fu ncti on by reference.

T h i s i s only one ex am p le of code th at m i g h t beh av e di fferently th an ex p ected as a

res u lt of detai led ov erload res olu ti on ru les . F or ex am p le, th e fact th at not all
ov erloaded fu ncti ons are v i s i ble wh en a corres p ondi ng fu ncti on call i s m ade m ay
or m ay not m atter. I n fact, defi ni ng a th ree-arg u m ent v ers i on of max() wi th ou t
h av i ng s een th e declarati on of a s p eci al two-arg u m ent v ers i on of max() for ints
cau s es th e two-arg u m ent tem p late to be u s ed by th e th ree-arg u m ent v ers i on:

// basics/max4.cpp

// maximum of two values of any type

template <typename T>
inline T const& max (T const& a, T const& b)
{
return a<b?b:a;
}

// maximum of three values of any type

template <typename T>
inline T const& max (T const& a, T const& b, T const& c)
{
return max (max(a,b), c); // uses the template version even for
ints
} // because the following declaration
comes
// too late:
// maximum of two int values
inline int const& max (int const& a, int const& b)
{
return a<b?b:a;
}
W e di s cu s s detai ls i n Secti on 9 .2 on p ag e 121, bu t for th e m om ent, as a ru le of
th u m b you s h ou ld always h av e all ov erloaded v ers i ons of a fu ncti on declared
before th e fu ncti on i s called.
2.5 Summary

• T em p late fu ncti ons defi ne a fam i ly of fu ncti ons for di fferent tem p late
arg u m ents .
• W h en you p as s tem p late arg u m ents , fu ncti on tem p lates are i ns tanti ated
for th es e arg u m ent typ es .
• Y ou can ex p li ci tly q u ali fy th e tem p late p aram eters .
• Y ou can ov erload fu ncti on tem p lates .
• W h en you ov erload fu ncti on tem p lates , li m i t you r ch ang es to s p eci fyi ng
tem p late p aram eters ex p li ci tly.
• M ak e s u re you s ee all ov erloaded v ers i ons of fu ncti on tem p lates before
you call th em .
Chapter 3. Class Templates

Si m i lar to fu ncti ons , clas s es can als o be p aram eteri z ed wi th one or m ore typ es .
C ontai ner clas s es , wh i ch are u s ed to m anag e elem ents of a certai n typ e, are a
typ i cal ex am p le of th i s featu re. B y u s i ng clas s tem p lates , you can i m p lem ent s u ch
contai ner clas s es wh i le th e elem ent typ e i s s ti ll op en. I n th i s ch ap ter we u s e a
s tack as an ex am p le of a clas s tem p late.
3.1 Implementation of Class Template Stack

A s we di d wi th fu ncti on tem p lates , we declare and defi ne clas s Stack<> i n a

h eader fi le as follows (we di s cu s s th e s ep arati on of declarati on and defi ni ti on i n
di fferent fi les i n Secti on 7 .3 on p ag e 8 9 ):

// basics/stack1.hpp

#include <vector>
#include <stdexcept>

template <typename T>

class Stack {
private:
std::vector<T> elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};
template <typename T>
void Stack<T>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

template<typename T>
void Stack<T>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}

template <typename T>

T Stack<T>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}

A s you can s ee, th e clas s tem p late i s i m p lem ented by u s i ng a clas s tem p late of
th e C + + s tandard li brary: vector<>. A s a res u lt, we don' t h av e to i m p lem ent
m em ory m anag em ent, cop y cons tru ctor, and as s i g nm ent op erator, s o we can
concentrate on th e i nterface of th i s clas s tem p late.

3.1.1 Declaration of Class Templates

D eclari ng clas s tem p lates i s s i m i lar to declari ng fu ncti on tem p lates : B efore th e
declarati on, a s tatem ent declares an i denti fi er as a typ e p aram eter. A g ai n, T i s
u s u ally u s ed as an i denti fi er:

template <typename T>

class Stack {
…
};

H ere ag ai n, th e k eyword class can be u s ed i ns tead of typename:

template <class T>

class Stack {
…
};

I ns i de th e clas s tem p late, T can be u s ed j u s t li k e any oth er typ e to declare

m em bers and m em ber fu ncti ons . I n th i s ex am p le, T i s u s ed to declare th e typ e of
th e elem ents as v ector of Ts , to declare push() as a m em ber fu ncti on th at g ets
a cons tant T reference as an arg u m ent, and to declare top() as a fu ncti on th at
retu rns a T:

template <typename T>

class Stack {
private:
std::vector<T> elems; // elements

public:
Stack(); // constructor
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
};

T h e typ e of th i s clas s i s Stack<T>, wi th T bei ng a tem p late p aram eter. T h u s , you

h av e to u s e Stack<T> wh enev er you u s e th e typ e of th i s clas s i n a declarati on.
I f, for ex am p le, you h av e to declare you r own cop y cons tru ctor and as s i g nm ent
op erator, i t look s li k e th i s [1]
:

[1]
A ccordi ng to th e s tandard, th ere are s om e ex cep ti ons to th i s ru le
(s ee Secti on 9 .2.3 on p ag e 126). H owev er, to be s u re, you s h ou ld
always wri te th e fu ll typ e wh en th e typ e i s req u i red.

template <typename T>

class Stack {
…
Stack (Stack<T> const&); // copy constructor
Stack<T>& operator= (Stack<T> const&); // assignment operator
…
};

H owev er, wh en th e nam e and not th e typ e of th e clas s i s req u i red, only Stack
h as to be u s ed. T h i s i s th e cas e wh en you s p eci fy th e nam e of th e clas s , th e
cons tru ctors , and th e des tru ctor.

3.1.2 Implementation of Member Functions

T o defi ne a m em ber fu ncti on of a clas s tem p late, you h av e to s p eci fy th at i t i s a

fu ncti on tem p late, and you h av e to u s e th e fu ll typ e q u ali fi cati on of th e clas s
tem p late. T h u s , th e i m p lem entati on of th e m em ber fu ncti on push() for typ e
Stack<T> look s li k e th i s :

template <typename T>

void Stack<T>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

I n th i s cas e, push_back() of th e elem ent v ector i s called, wh i ch ap p ends th e

elem ent at th e end of th e v ector.

N ote th at pop_back() of a v ector rem ov es th e las t elem ent bu t does n' t retu rn i t.
T h e reas on for th i s beh av i or i s ex cep ti on s afety. I t i s i m p os s i ble to i m p lem ent a
com p letely ex cep ti on-s afe v ers i on of pop() th at retu rns th e rem ov ed elem ent
(th i s top i c was fi rs t di s cu s s ed by T om C arg i ll i n [C arg i llE x cep ti onSafety] and i s
di s cu s s ed as I tem 10 i n [Su tterE x cep ti onal] ). H owev er, i g nori ng th i s dang er, we
cou ld i m p lem ent a pop() th at retu rns th e elem ent j u s t rem ov ed. T o do th i s , we
s i m p ly u s e T to declare a local v ari able of th e elem ent typ e:

template<typename T>
T Stack<T>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
T elem = elems.back(); // save copy of last element
elems.pop_back(); // remove last element
return elem; // return copy of saved element
}

B ecau s e th e v ectors back() (wh i ch retu rns th e las t elem ent) and pop_back()
(wh i ch rem ov es th e las t elem ent) h av e u ndefi ned beh av i or wh en th ere i s no
elem ent i n th e v ector, we h av e to ch eck wh eth er th e s tack i s em p ty. I f i t i s
em p ty, we th row an ex cep ti on of typ e std::out_of_range. T h i s i s als o done i n
top(), wh i ch retu rns bu t does not rem ov e th e top elem ent:

template<typename T>
T Stack<T>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}

O f cou rs e, as for any m em ber fu ncti on, you can als o i m p lem ent m em ber
fu ncti ons of clas s tem p lates as an i nli ne fu ncti on i ns i de th e clas s declarati on. F or
ex am p le:

template <typename T>

class Stack {
…
void push (T const& elem) {
elems.push_back(elem); // append copy of passed elem
}
…
};
3.2 Use of Class Template Stack

T o u s e an obj ect of a clas s tem p late, you m u s t s p eci fy th e tem p late arg u m ents
ex p li ci tly. T h e followi ng ex am p le s h ows h ow to u s e th e clas s tem p late Stack<>:

// basics/stack1test.cpp

#include <iostream>
#include <string>
#include <cstdlib>
#include "stack1.hpp"

int main()
{
try {
Stack<int> intStack; // stack of ints
Stack<std::string> stringStack; // stack of strings

// manipulate int stack

intStack.push(7);
std::cout << intStack.top() << std::endl;

// manipulate string stack

stringStack.push("hello");
std::cout << stringStack.top() << std::endl;
stringStack.pop();
stringStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
return EXIT_FAILURE; // exit program with ERROR status
}
}

B y declari ng typ e Stack<int>, int i s u s ed as typ e T i ns i de th e clas s tem p late.

T h u s , intStack i s created as an obj ect th at u s es a v ector of ints as elem ents
and, for all m em ber fu ncti ons th at are called, code for th i s typ e i s i ns tanti ated.
Si m i larly, by declari ng and u s i ng Stack<std::string>, an obj ect th at u s es a
v ector of s tri ng s as elem ents i s created, and for all m em ber fu ncti ons th at are
called, code for th i s typ e i s i ns tanti ated.

N ote th at code i s i ns tanti ated only for memb er f u n c ti on s that ar e c alled . F or clas s
tem p lates , m em ber fu ncti ons are i ns tanti ated only wh en th ey are u s ed. T h i s , of
cou rs e, s av es ti m e and s p ace. I t h as th e addi ti onal benefi t th at you can
i ns tanti ate a clas s ev en for th os e typ es th at cannot p erform all th e op erati ons of
all th e m em ber fu ncti ons , as long as th es e m em ber fu ncti ons are not called. A s
an ex am p le, cons i der a clas s i n wh i ch s om e m em ber fu ncti ons u s e th e op erator <
to s ort elem ents . I f you refrai n from calli ng th es e m em ber fu ncti ons , you can
i ns tanti ate th e clas s tem p late for typ es for wh i ch op erator < i s not defi ned.

I n th i s ex am p le, th e defau lt cons tru ctor, push(), and top() are i ns tanti ated for
both int and s tri ng s . H owev er, pop() i s i ns tanti ated only for s tri ng s . I f a clas s
tem p late h as s tati c m em bers , th es e are i ns tanti ated once for each typ e.

Y ou can u s e a typ e of an i ns tanti ated clas s tem p late as any oth er typ e, as long as
th e op erati ons are s u p p orted:

void foo (Stack<int> const& s) // parameter s is int stack

{
Stack<int> istack[10]; // istack is array of 10 int
stacks
…
}

B y u s i ng a typ e defi ni ti on, you can m ak e u s i ng a clas s tem p late m ore conv eni ent:

typedef Stack<int> IntStack;

void foo (IntStack const& s) // s is stack of ints

{
IntStack istack[10]; // istack is array of 10 stacks of
ints
…
}

N ote th at i n C + + a typ e defi ni ti on does defi ne a " typ e ali as " rath er th an a new
typ e. T h u s , after th e typ e defi ni ti on

typedef Stack<int> IntStack;

IntStack and Stack<int> are th e s am e typ e and can be u s ed for and as s i g ned
to each oth er.

T em p late arg u m ents m ay be any typ e, s u ch as p oi nters to floats or ev en s tack s

of ints :

Stack<float*> floatPtrStack; // stack of float pointers

Stack<Stack<int> > intStackStack; // stack of stack of ints

T h e only req u i rem ent i s th at any op erati on th at i s called i s p os s i ble accordi ng to

th i s typ e.

N ote th at you h av e to p u t wh i tes p ace between th e two clos i ng tem p late brack ets .
I f you don' t do th i s , you are u s i ng op erator >>, wh i ch res u lts i n a s yntax error:

Stack<Stack<int>> intStackStack; // ERROR: >> is not allowed

3.3 Specializations of Class Templates

Y ou can s p eci ali z e a clas s tem p late for certai n tem p late arg u m ents . Si m i lar to th e
ov erloadi ng of fu ncti on tem p lates (s ee p ag e 15 ), s p eci ali z i ng clas s tem p lates
allows you to op ti m i z e i m p lem entati ons for certai n typ es or to fi x a m i s beh av i or
of certai n typ es for an i ns tanti ati on of th e clas s tem p late. H owev er, i f you
s p eci ali z e a clas s tem p late, you m u s t als o s p eci ali z e all m em ber fu ncti ons .
A lth ou g h i t i s p os s i ble to s p eci ali z e a s i ng le m em ber fu ncti on, once you h av e
done s o, you can no long er s p eci ali z e th e wh ole clas s .

T o s p eci ali z e a clas s tem p late, you h av e to declare th e clas s wi th a leadi ng

template<> and a s p eci fi cati on of th e typ es for wh i ch th e clas s tem p late i s
s p eci ali z ed. T h e typ es are u s ed as a tem p late arg u m ent and m u s t be s p eci fi ed
di rectly followi ng th e nam e of th e clas s :

template<>
class Stack<std::string> {
…
};

F or th es e s p eci ali z ati ons , any defi ni ti on of a m em ber fu ncti on m u s t be defi ned as
an " ordi nary" m em ber fu ncti on, wi th each occu rrence of T bei ng rep laced by th e
s p eci ali z ed typ e:

void Stack<std::string>::push (std::string const& elem)

{
elems.push_back(elem); // append copy of passed elem
}

H ere i s a com p lete ex am p le of a s p eci ali z ati on of Stack<> for typ e

std::string:

// basics/stack2.hpp

#include <deque>
#include <string>
#include <stdexcept>
#include "stack1.hpp"

template<>
class Stack<std::string> {
private:
std::deque<std::string> elems; // elements

public:
void push(std::string const&); // push element
 void pop(); // pop element
std::string top() const; // return top element
bool empty() const { // return whether the stack is
empty
return elems.empty();
}
};

void Stack<std::string>::push (std::string const& elem)

{
elems.push_back(elem); // append copy of passed elem
}

void Stack<std::string>::pop ()
{
if (elems.empty()) {
throw std::out_of_range
("Stack<std::string>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}

std::string Stack<std::string>::top () const

{
if (elems.empty()) {
throw std::out_of_range
("Stack<std::string>::top(): empty stack");
}
return elems.back(); // return copy of last element
}

I n th i s ex am p le, a deq u e i ns tead of a v ector i s u s ed to m anag e th e elem ents

i ns i de th e s tack . A lth ou g h th i s h as no p arti cu lar benefi t h ere, i t does dem ons trate
th at th e i m p lem entati on of a s p eci ali z ati on m i g h t look v ery di fferent from th e
i m p lem entati on of th e p ri m ary tem p late. [2 ]

[2 ]
I n fact, th ere i s a benefi t for u s i ng a deq u e i ns tead of a v ector to
i m p lem ent a s tack : A deq u e frees m em ory wh en elem ents are
rem ov ed, and i t can' t h ap p en th at elem ents h av e to be m ov ed as a
res u lt of reallocati on. H owev er, th i s i s no p arti cu lar benefi t for
s tri ng s . F or th i s reas on i t i s p robably a g ood i dea to u s e a deq u e i n
th e p ri m ary clas s tem p late (as i s th e cas e i n clas s std::stack<>
of th e C + + s tandard li brary).
3.4 Partial Specialization

C las s tem p lates can be p arti ally s p eci ali z ed. Y ou can s p eci fy s p eci al
i m p lem entati ons for p arti cu lar ci rcu m s tances , bu t s om e tem p late p aram eters
m u s t s ti ll be defi ned by th e u s er. F or ex am p le, for th e followi ng clas s tem p late

template <typename T1, typename T2>

class MyClass {
…
};

th e followi ng p arti al s p eci ali z ati ons are p os s i ble:

// partial specialization: both template parameters have same type

template <typename T>
class MyClass<T,T> {
…
};

// partial specialization: second type is int

template <typename T>
class MyClass<T,int> {
…
};

// partial specialization: both template parameters are pointer types

template <typename T1, typename T2>
class MyClass<T1*,T2*> {
…
};

T h e followi ng ex am p le s h ows wh i ch tem p late i s u s ed by wh i ch declarati on:

MyClass<int,float> mif; // uses MyClass<T1,T2>

MyClass<float,float> mff; // uses MyClass<T,T>
MyClass<float,int> mfi; // uses MyClass<T,int>
MyClass<int*,float*> mp; // uses MyClass<T1*,T2*>

I f m ore th an one p arti al s p eci ali z ati on m atch es eq u ally well, th e declarati on i s
am bi g u ou s :

MyClass<int,int> m; // ERROR: matches MyClass<T,T>

// and MyClass<T,int>
MyClass<int*,int*> m; // ERROR: matches MyClass<T,T>
// and MyClass<T1*,T2*>

T o res olv e th e s econd am bi g u i ty, you can p rov i de an addi ti onal p arti al
s p eci ali z ati on for p oi nters of th e s am e typ e:

template <typename T>

class MyClass<T*,T*> {
…
};

F or detai ls , s ee Secti on 12.4 on p ag e 200.

3.5 Default Template Arguments

F or clas s tem p lates you can als o defi ne defau lt v alu es for tem p late p aram eters .
T h es e v alu es are called d ef au lt template ar g u men ts. T h ey m ay ev en refer to
p rev i ou s tem p late p aram eters . F or ex am p le, i n clas s Stack<> you can defi ne th e
contai ner th at i s u s ed to m anag e th e elem ents as a s econd tem p late p aram eter,
u s i ng std::vector<> as th e defau lt v alu e:

// basics/stack3.hpp

#include <vector>
#include <stdexcept>

template <typename T, typename CONT = std::vector<T> >

class Stack {
private:
CONT elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};

template <typename T, typename CONT>

void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

template <typename T, typename CONT>

void Stack<T,CONT>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}

template <typename T, typename CONT>

T Stack<T,CONT>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}

N ote th at we now h av e two tem p late p aram eters , s o each defi ni ti on of a m em ber
fu ncti on m u s t be defi ned wi th th es e two p aram eters :

template <typename T, typename CONT>

void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

Y ou can u s e th i s s tack th e s am e way i t was u s ed before. T h u s , i f you p as s a fi rs t

and only arg u m ent as an elem ent typ e, a v ector i s u s ed to m anag e th e elem ents
of th i s typ e:

template <typename T, typename CONT = std::vector<T> >

class Stack {
private:
CONT elems; // elements
…
};

I n addi ti on, you cou ld s p eci fy th e contai ner for th e elem ents wh en you declare a
Stack obj ect i n you r p rog ram :

// basics/stack3test.cpp

#include <iostream>
#include <deque>
#include <cstdlib>
#include "stack3.hpp"

int main()
{
try {
// stack of ints:
Stack<int> intStack;

// stack of doubles which uses a std::deque<> to mange the

elements
Stack<double,std::deque<double> > dblStack;

// manipulate int stack

intStack.push(7);
std::cout << intStack.top() << std::endl;
intStack.pop();

// manipulate double stack

dblStack.push(42.42);
std::cout << dblStack.top() << std::endl;
dblStack.pop();
dblStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
return EXIT_FAILURE; // exit program with ERROR status
}
}

W i th

Stack<double,std::deque<double> >

you declare a s tack for doubles th at u s es a std::deque<> to m anag e th e

elem ents i nternally.
3.6 Summary

• A clas s tem p late i s a clas s th at i s i m p lem ented wi th one or m ore typ e

p aram eters left op en.
• T o u s e a clas s tem p late, you p as s th e op en typ es as tem p late arg u m ents .
T h e clas s tem p late i s th en i ns tanti ated (and com p i led) for th es e typ es .
• F or clas s tem p lates , only th os e m em ber fu ncti ons th at are called are
i ns tanti ated.
• Y ou can s p eci ali z e clas s tem p lates for certai n typ es .
• Y ou can p arti ally s p eci ali z e clas s tem p lates for certai n typ es .
• Y ou can defi ne defau lt v alu es for clas s tem p late p aram eters . T h es e m ay
refer to p rev i ou s tem p late p aram eters .
Chapter 4. Nontype Template Parameters

F or fu ncti on and clas s tem p lates , tem p late p aram eters don' t h av e to be typ es .
T h ey can als o be ordi nary v alu es . A s wi th tem p lates u s i ng typ e p aram eters , you
defi ne code for wh i ch a certai n detai l rem ai ns op en u nti l th e code i s u s ed.
H owev er, th e detai l th at i s op en i s a v alu e i ns tead of a typ e. W h en u s i ng s u ch a
tem p late, you h av e to s p eci fy th i s v alu e ex p li ci tly. T h e res u lti ng code th en g ets
i ns tanti ated. T h i s ch ap ter i llu s trates th i s featu re for a new v ers i on of th e s tack
clas s tem p late. I n addi ti on, we s h ow an ex am p le of nontyp e fu ncti on tem p late
p aram eters and di s cu s s s om e res tri cti ons to th i s tech ni q u e.
4.1 Nontype Class Template Parameters

I n contras t to th e s am p le i m p lem entati ons of a s tack i n p rev i ou s ch ap ters , you

can als o i m p lem ent a s tack by u s i ng a fi x ed-s i z e array for th e elem ents . A n
adv antag e of th i s m eth od i s th at th e m em ory m anag em ent ov erh ead, wh eth er
p erform ed by you or by a s tandard contai ner, i s av oi ded. H owev er, determ i ni ng
th e bes t s i z e for s u ch a s tack can be ch alleng i ng . T h e s m aller th e s i z e you
s p eci fy, th e m ore li k ely i t i s th at th e s tack wi ll g et fu ll. T h e larg er th e s i z e you
s p eci fy, th e m ore li k ely i t i s th at m em ory wi ll be res erv ed u nneces s ari ly. A g ood
s olu ti on i s to let th e u s er of th e s tack s p eci fy th e s i z e of th e array as th e
m ax i m u m s i z e needed for s tack elem ents .

T o do th i s , defi ne th e s i z e as a tem p late p aram eter:

// basics/stack4.hpp

#include <stdexcept>

template <typename T, int MAXSIZE>

class Stack {
private:
T elems[MAXSIZE]; // elements
int numElems; // current number of elements
public:
Stack(); // constructor
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return numElems == 0;
}
bool full() const { // return whether the stack is full
return numElems == MAXSIZE;
}
};

// constructor
template <typename T, int MAXSIZE>
Stack<T,MAXSIZE>::Stack ()
: numElems(0) // start with no elements
{
// nothing else to do
}

template <typename T, int MAXSIZE>

void Stack<T,MAXSIZE>::push (T const& elem)
{
if (numElems == MAXSIZE) {
throw std::out_of_range("Stack<>::push(): stack is full");
}
elems[numElems] = elem; // append element
 ++numElems; // increment number of elements
}

template<typename T, int MAXSIZE>

void Stack<T,MAXSIZE>::pop ()
{
if (numElems <= 0) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
--numElems; // decrement number of elements
}

template <typename T, int MAXSIZE>

T Stack<T,MAXSIZE>::top () const
{
if (numElems <= 0) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems[numElems-1]; // return last element
}

T h e new s econd tem p late p aram eter, MAXSIZE, i s of typ e int. I t s p eci fi es th e
s i z e of th e array of s tack elem ents :

template <typename T, int MAXSIZE>

class Stack {
private:
T elems[MAXSIZE]; // elements
…
};

I n addi ti on, i t i s u s ed i n push() to ch eck wh eth er th e s tack i s fu ll:

template <typename T, int MAXSIZE>

void Stack<T,MAXSIZE>::push (T const& elem)
{
if (numElems == MAXSIZE) {
throw "Stack<>::push(): stack is full";
}
elems[numElems] = elem; // append element
++numElems; // increment number of elements
}

T o u s e th i s clas s tem p late you h av e to s p eci fy both th e elem ent typ e and th e
m ax i m u m s i z e:

// basics/stack4test.cpp

#include <iostream>
#include <string>
#include <cstdlib>
#include "stack4.hpp"

int main()
{
try {
Stack<int,20> int20Stack; // stack of up to 20
ints
Stack<int,40> int40Stack; // stack of up to 40
ints
Stack<std::string,40> stringStack; // stack of up to 40
strings

// manipulate stack of up to 20 ints

int20Stack.push(7);
std::cout << int20Stack.top() << std::endl;
int20Stack.pop();

// manipulate stack of up to 40 strings

stringStack.push("hello");
std::cout << stringStack.top() << std::endl;
stringStack.pop();
stringStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
return EXIT_FAILURE; // exit program with ERROR status
}
}

N ote th at each tem p late i ns tanti ati on i s i ts own typ e. T h u s , int20Stack and
int40Stack are two di fferent typ es , and no i m p li ci t or ex p li ci t typ e conv ers i on
between th em i s defi ned. T h u s , one cannot be u s ed i ns tead of th e oth er, and you
cannot as s i g n one to th e oth er.

A g ai n, defau lt v alu es for th e tem p late p aram eters can be s p eci fi ed:

template <typename T = int, int MAXSIZE = 100>

class Stack {
…
};

H owev er, from a p ers p ecti v e of g ood des i g n, th i s m ay not be ap p rop ri ate i n th i s
ex am p le. D efau lt v alu es s h ou ld be i ntu i ti v ely correct. B u t nei th er typ e int nor a
m ax i m u m s i z e of 100 s eem s i ntu i ti v e for a g eneral s tack typ e. T h u s , i t i s better
wh en th e p rog ram m er h as to s p eci fy both v alu es ex p li ci tly s o th at th es e two
attri bu tes are always docu m ented du ri ng a declarati on.
4.2 Nontype Function Template Parameters

Y ou can als o defi ne nontyp e p aram eters for fu ncti on tem p lates . F or ex am p le, th e
followi ng fu ncti on tem p late defi nes a g rou p of fu ncti ons for wh i ch a certai n v alu e
can be added:

// basics/addval.hpp

template <typename T, int VAL>

T addValue (T const& x)
{
return x + VAL;
}

T h es e k i nds of fu ncti ons are u s efu l i f fu ncti ons or op erati ons i n g eneral are u s ed
as p aram eters . F or ex am p le, i f you u s e th e Standard T em p late L i brary (ST L ) you
can p as s an i ns tanti ati on of th i s fu ncti on tem p late to add a v alu e to each elem ent
of a collecti on:

std::transform (source.begin(), source.end(), // start and end of

source
dest.begin(), // start of
destination
addValue<int,5>); // operation

T h e las t arg u m ent i ns tanti ates th e fu ncti on tem p late addValue() to add 5 to an
int v alu e. T h e res u lti ng fu ncti on i s called for each elem ent i n th e s ou rce
collecti on source, wh i le i t i s trans lated i nto th e des ti nati on collecti on dest.

N ote th at th ere i s a p roblem wi th th i s ex am p le: addValue<int,5> i s a fu ncti on

tem p late, and fu ncti on tem p lates are cons i dered to nam e a s et of ov erloaded
fu ncti ons (ev en i f th e s et h as only one m em ber). H owev er, accordi ng to th e
cu rrent s tandard, s ets of ov erloaded fu ncti ons cannot be u s ed for tem p late
p aram eter dedu cti on. T h u s , you h av e to cas t to th e ex act typ e of th e fu ncti on
tem p late arg u m ent:

std::transform (source.begin(), source.end(), // start and end of

source
dest.begin(), // start of
destination
(int(*)(int const&)) addValue<int,5>); // operation

T h ere i s a p rop os al for th e s tandard to fi x th i s beh av i or s o th at th e cas t i s n' t

neces s ary i n th i s contex t (s ee [C oreI s s u e115 ] for detai ls ), bu t u nti l th en th e cas t
m ay be neces s ary to be p ortable.
4.3 Restrictions for Nontype Template Parameters

N ote th at nontyp e tem p late p aram eters carry s om e res tri cti ons . I n g eneral, th ey
m ay be cons tant i nteg ral v alu es (i nclu di ng enu m erati ons ) or p oi nters to obj ects
wi th ex ternal li nk ag e.

F loati ng -p oi nt nu m bers and clas s -typ e obj ects are not allowed as nontyp e
tem p late p aram eters :

template <double VAT> // ERROR: floating-point values are not

double process (double v) // allowed as template parameters
{
return v * VAT;
}

template <std::string name> // ERROR: class-type objects are not

class MyClass { // allowed as template parameters
…
};

N ot bei ng able to u s e floati ng -p oi nt li terals (and s i m p le cons tant floati ng -p oi nt

ex p res s i ons ) as tem p late arg u m ents h as h i s tori cal reas ons . B ecau s e th ere are no
s eri ou s tech ni cal ch alleng es , th i s m ay be s u p p orted i n fu tu re v ers i ons of C + +
(s ee Secti on 13 .4 on p ag e 210).

B ecau s e s tri ng li terals are obj ects wi th i nternal li nk ag e (two s tri ng li terals wi th
th e s am e v alu e bu t i n di fferent m odu les are di fferent obj ects ), you can' t u s e th em
as tem p late arg u m ents ei th er:

template <char const* name>

class MyClass {
…
};

MyClass<"hello"> x; // ERROR: string literal "hello" not allowed

Y ou cannot u s e a g lobal p oi nter ei th er:

template <char const* name>

class MyClass {
…
};

char const* s = "hello";

MyClass<s> x; // ERROR: s is pointer to object with internal

linkage
H owev er, th e followi ng i s p os s i ble:

template <char const* name>

class MyClass {
…
};

extern char const s[] = "hello";

MyClass<s> x; // OK

T h e g lobal ch aracter array s i s i ni ti ali z ed by "hello" s o th at s i s an obj ect wi th

ex ternal li nk ag e.

See Secti on 8 .3 .3 on p ag e 109 for a detai led di s cu s s i on and Secti on 13 .4 on p ag e

209 for a di s cu s s i on of p os s i ble fu tu re ch ang es i n th i s area.
4.4 Summary

• T em p lates can h av e tem p late p aram eters th at are v alu es rath er th an

typ es .
• Y ou cannot u s e floati ng -p oi nt nu m bers , clas s -typ e obj ects , and obj ects
wi th i nternal li nk ag e (s u ch as s tri ng li terals ) as arg u m ents for nontyp e
tem p late p aram eters .
Chapter 5. Tricky Basics

T h i s ch ap ter cov ers s om e fu rth er bas i c as p ects of tem p lates th at are relev ant to
th e p racti cal u s e of tem p lates : an addi ti onal u s e of th e typename k eyword,
defi ni ng m em ber fu ncti ons and nes ted clas s es as tem p lates , tem p late tem p late
p aram eters , z ero i ni ti ali z ati on, and s om e detai ls abou t u s i ng s tri ng li terals as
arg u m ents for fu ncti on tem p lates . T h es e as p ects can be tri ck y at ti m es , bu t ev ery
day-to-day p rog ram m er s h ou ld h av e h eard of th em .
5.1 Keyword typename

T h e k eyword typename was i ntrodu ced du ri ng th e s tandardi z ati on of C + + to

clari fy th at an i denti fi er i ns i de a tem p late i s a typ e. C ons i der th e followi ng
ex am p le:

template <typename T>

class MyClass {
typename T::SubType * ptr;
…
};

H ere, th e s econd typename i s u s ed to clari fy th at SubType i s a typ e defi ned

wi th i n clas s T. T h u s , ptr i s a p oi nter to th e typ e T::SubType.

W i th ou t typename, SubType wou ld be cons i dered a s tati c m em ber. T h u s , i t

wou ld be a concrete v ari able or obj ect. A s a res u lt, th e ex p res s i on

T::SubType * ptr

wou ld be a m u lti p li cati on of th e s tati c SubType m em ber of clas s T wi th ptr.

I n g eneral, typename h as to be u s ed wh enev er a nam e th at dep ends on a

tem p late p aram eter i s a typ e. T h i s i s di s cu s s ed i n detai l i n Secti on 9 .3 .2 on p ag e
13 0.

A typ i cal ap p li cati on of typename i s th e acces s to i terators of ST L contai ners i n

tem p late code:

// basics/printcoll.hpp

#include <iostream>

// print elements of an STL container

template <typename T>
void printcoll (T const& coll)
{
typename T::const_iterator pos; // iterator to iterate over coll
typename T::const_iterator end(coll.end()); // end position

for (pos=coll.begin(); pos!=end; ++pos) {

std::cout << *pos << ' ';
}
std::cout << std::endl;
}
I n th i s fu ncti on tem p late, th e call p aram eter i s an ST L contai ner of typ e T. T o
i terate ov er all elem ents of th e contai ner, th e i terator typ e of th e contai ner i s
u s ed, wh i ch i s declared as typ e const_iterator i ns i de each ST L contai ner
clas s :

class stlcontainer {
…
typedef … iterator; // iterator for read/write access
typedef … const_iterator; // iterator for read access
…
};

T h u s , to acces s typ e const_iterator of tem p late typ e T, you h av e to q u ali fy i t

wi th a leadi ng typename:

typename T::const_iterator pos;

The .template Construct

A v ery s i m i lar p roblem was di s cov ered after th e i ntrodu cti on of typename.
C ons i der th e followi ng ex am p le u s i ng th e s tandard bitset typ e:

template<int N>
void printBitset (std::bitset<N> const& bs)
{
std::cout << bs.template to_string<char,char_traits<char>,
allocator<char> >();
}

T h e s trang e cons tru ct i n th i s ex am p le i s .template. W i th ou t th at ex tra u s e of

template, th e com p i ler does not k now th at th e les s -th an tok en (<) th at follows
i s not really " les s th an" bu t th e beg i nni ng of a tem p late arg u m ent li s t. N ote th at
th i s i s a p roblem only i f th e cons tru ct before th e p eri od dep ends on a tem p late
p aram eter. I n ou r ex am p le, th e p aram eter bs dep ends on th e tem p late
p aram eter N.

I n conclu s i on, th e .template notati on (and s i m i lar notati ons s u ch as -

>template) s h ou ld be u s ed only i ns i de tem p lates and only i f th ey follow
s om eth i ng th at dep ends on a tem p late p aram eter. See Secti on 9 .3 .3 on p ag e 13 2
for detai ls .
5.2 Using this->

F or clas s tem p lates wi th bas e clas s es , u s i ng a nam e x by i ts elf i s not always

eq u i v alent to this->x, ev en th ou g h a m em ber x i s i nh eri ted. F or ex am p le:

template <typename T>

class Base {
public:
void exit();
};

template <typename T>

class Derived : Base<T> {
public:
void foo() {
exit(); // calls external exit() or error
}
};

I n th i s ex am p le, for res olv i ng th e s ym bol exit i ns i de foo(), exit() defi ned i n
Base i s n ev er cons i dered. T h erefore, ei th er you h av e an error, or anoth er
exit() (s u ch as th e s tandard exit()) i s called.

W e di s cu s s th i s i s s u e i n Secti on 9 .4 .2 on p ag e 13 6 i n detai l. F or th e m om ent, as

a ru le of th u m b, we recom m end th at you always q u ali fy any s ym bol th at i s
declared i n a bas e th at i s s om eh ow dep endent on a tem p late p aram eter wi th
this-> or Base<T>::. I f you want to av oi d all u ncertai nty, you m ay cons i der
q u ali fyi ng all m em ber acces s es (i n tem p lates ).
5.3 Member Templates

C las s m em bers can als o be tem p lates . T h i s i s p os s i ble for both nes ted clas s es and
m em ber fu ncti ons . T h e ap p li cati on and adv antag e of th i s abi li ty can ag ai n be
dem ons trated wi th th e Stack<> clas s tem p late. N orm ally you can as s i g n s tack s
to each oth er only wh en th ey h av e th e s am e typ e, wh i ch i m p li es th at th e
elem ents h av e th e s am e typ e. H owev er, you can' t as s i g n a s tack wi th elem ents of
any oth er typ e, ev en i f th ere i s an i m p li ci t typ e conv ers i on for th e elem ent typ es
defi ned:

Stack<int> intStack1, intStack2; // stacks for ints

Stack<float> floatStack; // stack for floats
…
intStack1 = intStack2; // OK: stacks have same type
floatStack = intStack1; // ERROR: stacks have different types

T h e defau lt as s i g nm ent op erator req u i res th at both s i des of th e as s i g nm ent

op erator h av e th e s am e typ e, wh i ch i s not th e cas e i f s tack s h av e di fferent
elem ent typ es .

B y defi ni ng an as s i g nm ent op erator as a tem p late, h owev er, you can enable th e
as s i g nm ent of s tack s wi th elem ents for wh i ch an ap p rop ri ate typ e conv ers i on i s
defi ned. T o do th i s you h av e to declare Stack<> as follows :

// basics/stack5decl.hpp

template <typename T>

class Stack {
private:
std::deque<T> elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}

// assign stack of elements of type T2

template <typename T2>
Stack<T>& operator= (Stack<T2> const&);
};

T h e followi ng two ch ang es h av e been m ade:

1. W e a d d e d a d e c l a r a t i o n o f a n a s s i g n m e n t o p e r a t o r f o r s t a c k s o f e l e m e n t s o f a n o t h e r t y p e T2.
 2 . T h e s t a c k n o w u s e s a d e q u e a s a n in t e r n a l c o n t a in e r fo r t h e e le m e n ts .A g a in , th is is a c o n s e q u e n c e
o f th e im p le m e n t a tio n o f t h e n e w a s s ig n m e n t o p e r a to r .

T h e i m p lem entati on of th e new as s i g nm ent op erator look s li k e th i s :

// basics/stack5assign.hpp

template <typename T>

template <typename T2>
Stack<T>& Stack<T>::operator= (Stack<T2> const& op2)
{
if ((void*)this == (void*)&op2) { // assignment to itself?
return *this;
}

Stack<T2> tmp(op2); // create a copy of the assigned

stack

elems.clear(); // remove existing elements

while (!tmp.empty()) { // copy all elements
elems.push_front(tmp.top());
tmp.pop();
}
return *this;
}

F i rs t let' s look at th e s yntax to defi ne a m em ber tem p late. I ns i de th e tem p late

wi th tem p late p aram eter T, an i nner tem p late wi th tem p late p aram eter T2 i s
defi ned:

template <typename T>

template <typename T2>
…

I ns i de th e m em ber fu ncti on you m ay ex p ect s i m p ly to acces s all neces s ary data

for th e as s i g ned s tack op2. H owev er, th i s s tack h as a di fferent typ e (i f you
i ns tanti ate a clas s tem p late for two di fferent typ es , you g et two di fferent typ es ),
s o you are res tri cted to u s i ng th e p u bli c i nterface. I t follows th at th e only way to
acces s th e elem ents i s by calli ng top(). H owev er, each elem ent h as to becom e a
top elem ent, th en. T h u s , a cop y of op2 m u s t fi rs t be m ade, s o th at th e elem ents
are tak en from th at cop y by calli ng pop(). B ecau s e top() retu rns th e las t
elem ent p u s h ed onto th e s tack , we h av e to u s e a contai ner th at s u p p orts th e
i ns erti on of elem ents at th e oth er end of th e collecti on. F or th i s reas on, we u s e a
deq u e, wh i ch p rov i des push_front() to p u t an elem ent on th e oth er s i de of th e
collecti on.

H av i ng th i s m em ber tem p late, you can now as s i g n a s tack of ints to a s tack of

floats :
Stack<int> intStack; // stack for ints
Stack<float> floatStack; // stack for floats
…
floatStack = intStack; // OK: stacks have different types,
// but int converts to float

O f cou rs e, th i s as s i g nm ent does not ch ang e th e typ e of th e s tack and i ts

elem ents . A fter th e as s i g nm ent, th e elem ents of th e floatStack are s ti ll
floats and th erefore pop() s ti ll retu rns a float.

I t m ay ap p ear th at th i s fu ncti on wou ld di s able typ e ch eck i ng s u ch th at you cou ld

as s i g n a s tack wi th elem ents of any typ e, bu t th i s i s not th e cas e. T h e neces s ary
typ e ch eck i ng occu rs wh en th e elem ent of th e (cop y of th e) s ou rce s tack i s
m ov ed to th e des ti nati on s tack :

elems.push_front(tmp.top());

I f, for ex am p le, a s tack of s tri ng s g ets as s i g ned to a s tack of floats , th e

com p i lati on of th i s li ne res u lts i n an error m es s ag e s tati ng th at th e s tri ng
retu rned by tmp.top() cannot be p as s ed as an arg u m ent to
elems.push_front() (th e m es s ag e v ari es dep endi ng on th e com p i ler, bu t th i s
i s th e g i s t of wh at i s m eant):

Stack<std::string> stringStack; // stack of ints

Stack<float> floatStack; // stack of floats
…
floatStack = stringStack; // ERROR: std::string doesn't convert to
float

N ote th at a tem p late as s i g nm ent op erator does n' t rep lace th e defau lt as s i g nm ent
op erator. F or as s i g nm ents of s tack s of th e s am e typ e, th e defau lt as s i g nm ent
op erator i s s ti ll called.

A g ai n, you cou ld ch ang e th e i m p lem entati on to p aram eteri z e th e i nternal

contai ner typ e:

// basics/stack6decl.hpp

template <typename T, typename CONT = std::deque<T> >

class Stack {
private:
CONT elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
 }

// assign stack of elements of type T2

template <typename T2, typename CONT2>
Stack<T,CONT>& operator= (Stack<T2,CONT2> const&);
};

T h en th e tem p late as s i g nm ent op erator i s i m p lem ented li k e th i s :

// basics/stack6assign.hpp

template <typename T, typename CONT>

template <typename T2, typename CONT2>
Stack<T,CONT>&
Stack<T,CONT>::operator= (Stack<T2,CONT2> const& op2)
{
if ((void*)this == (void*)&op2) { // assignment to itself?
return *this;
}

Stack<T2> tmp(op2); // create a copy of the assigned

stack

elems.clear(); // remove existing elements

while (!tmp.empty()) { // copy all elements
elems.push_front(tmp.top());
tmp.pop();
}
return *this;
}

R em em ber, for clas s tem p lates , only th os e m em ber fu ncti ons th at are called are
i ns tanti ated. T h u s , i f you av oi d as s i g ni ng a s tack wi th elem ents of a di fferent
typ e, you cou ld ev en u s e a v ector as an i nternal contai ner:

// stack for ints using a vector as an internal container

Stack<int,std::vector<int> > vStack;
…
vStack.push(42);
vStack.push(7);
std::cout << vStack.pop() << std::endl;

B ecau s e th e as s i g nm ent op erator tem p late i s n' t neces s ary, no error m es s ag e of a

m i s s i ng m em ber fu ncti on push_front() occu rs and th e p rog ram i s fi ne.

F or th e com p lete i m p lem entati on of th e las t ex am p le, s ee all th e fi les wi th a

nam e th at s tarts wi th " stack6" i n th e s u bdi rectory basics. [1]

[1]
D on' t be s u rp ri s ed i f you r com p i ler rep orts errors wi th th es e
s am p le fi les . I n th e s am p les , we u s e alm os t ev ery i m p ortant
tem p late featu re. T h u s , you need a com p i ler th at conform s clos ely
to th e s tandard.
5.4 Template Template Parameters

I t can be u s efu l to allow a tem p late p aram eter i ts elf to be a clas s tem p late.
A g ai n, ou r s tack clas s tem p late can be u s ed as an ex am p le.

T o u s e a di fferent i nternal contai ner for s tack s , th e ap p li cati on p rog ram m er h as

to s p eci fy th e elem ent typ e twi ce. T h u s , to s p eci fy th e typ e of th e i nternal
contai ner, you h av e to p as s th e typ e of th e contai ner an d th e typ e of i ts elem ents
ag ai n:

Stack<int,std::vector<int> > vStack; // integer stack that uses a

vector

U s i ng tem p late tem p late p aram eters allows you to declare th e Stack clas s
tem p late by s p eci fyi ng th e typ e of th e contai ner wi th ou t res p eci fyi ng th e typ e of
i ts elem ents :

stack<int,std::vector> vStack; // integer stack that uses a

vector

T o do th i s you m u s t s p eci fy th e s econd tem p late p aram eter as a tem p late

tem p late p aram eter. I n p ri nci p le, th i s look s as follows [2 ]
:

[2 ]
T h ere i s a p roblem wi th th i s v ers i on th at we ex p lai n i n a m i nu te.
H owev er, th i s p roblem affects only th e defau lt v alu e std::deque.
T h u s , we can i llu s trate th e g eneral featu res of tem p late tem p late
p aram eters wi th th i s ex am p le.

// basics/stack7decl.hpp

template <typename T,
template <typename ELEM> class CONT = std::deque >
class Stack {
private:
CONT<T> elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};

T h e di fference i s th at th e s econd tem p late p aram eter i s declared as bei ng a clas s

tem p late:

template <typename ELEM> class CONT

T h e defau lt v alu e h as ch ang ed from std::deque<T> to std::deque. T h i s

p aram eter h as to be a clas s tem p late, wh i ch i s i ns tanti ated for th e typ e th at i s
p as s ed as th e fi rs t tem p late p aram eter:

CONT<T> elems;

T h i s u s e of th e fi rs t tem p late p aram eter for th e i ns tanti ati on of th e s econd

tem p late p aram eter i s p arti cu lar to th i s ex am p le. I n g eneral, you can i ns tanti ate
a tem p late tem p late p aram eter wi th any typ e i ns i de a clas s tem p late.

A s u s u al, i ns tead of typename you cou ld u s e th e k eyword class for tem p late
p aram eters . H owev er, CONT i s u s ed to defi ne a clas s and m u s t be declared by
u s i ng th e k eyword class. T h u s , th e followi ng i s fi ne:

template <typename T,
template <class ELEM> class CONT = std::deque> // OK
class Stack {
…
};

bu t th e followi ng i s not:

template <typename T,
template <typename ELEM> typename CONT = std::deque>
class Stack { // ERROR
…
};

B ecau s e th e tem p late p aram eter of th e tem p late tem p late p aram eter i s not u s ed,
you can om i t i ts nam e:

template <typename T,
template <typename> class CONT = std::deque >
class Stack {
…
};

M em ber fu ncti ons m u s t be m odi fi ed accordi ng ly. T h u s , you h av e to s p eci fy th e

s econd tem p late p aram eter as th e tem p late tem p late p aram eter. T h e s am e
ap p li es to th e i m p lem entati on of th e m em ber fu ncti on. T h e push() m em ber
fu ncti on, for ex am p le, i s i m p lem ented as follows :
template <typename T, template <typename> class CONT>
void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

T em p late tem p late p aram eters for fu ncti on tem p lates are not allowed.

Template Template Argument Matching

I f you try to u s e th e new v ers i on of Stack, you g et an error m es s ag e s ayi ng th at

th e defau lt v alu e std::deque i s not com p ati ble wi th th e tem p late tem p late
p aram eter CONT. T h e p roblem i s th at a tem p late tem p late arg u m ent m u s t be a
tem p late wi th p aram eters th at ex ac tly m atch th e p aram eters of th e tem p late
tem p late p aram eter i t s u bs ti tu tes . D efau lt tem p late arg u m ents of tem p late
tem p late arg u m ents are not cons i dered, s o th at a m atch cannot be ach i ev ed by
leav i ng ou t arg u m ents th at h av e defau lt v alu es .

T h e p roblem i n th i s ex am p le i s th at th e std::deque tem p late of th e s tandard

li brary h as m ore th an one p aram eter: T h e s econd p aram eter (wh i ch des cri bes a
s o-called alloc ator ) h as a defau lt v alu e, bu t th i s i s not cons i dered wh en m atch i ng
std::deque to th e CONT p aram eter.

T h ere i s a work arou nd, h owev er. W e can rewri te th e clas s declarati on s o th at th e
CONT p aram eter ex p ects contai ners wi th two tem p late p aram eters :

template <typename T,
template <typename ELEM,
typename ALLOC = std::allocator<ELEM> >
class CONT = std::deque>
class Stack {
private:
CONT<T> elems; // elements
…
};

A g ai n, you can om i t ALLOC becau s e i t i s not u s ed.

T h e fi nal v ers i on of ou r Stack tem p late (i nclu di ng m em ber tem p lates for
as s i g nm ents of s tack s of di fferent elem ent typ es ) now look s as follows :

// basics/stack8.hpp

#ifndef STACK_HPP
#define STACK_HPP

#include <deque>
#include <stdexcept>
#include <allocator>

template <typename T,
template <typename ELEM,
typename = std::allocator<ELEM> >
class CONT = std::deque>
class Stack {
private:
CONT<T> elems; // elements

public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}

// assign stack of elements of type T2

template<typename T2,
template<typename ELEM2,
typename = std::allocator<ELEM2>
>class CONT2>
Stack<T,CONT>& operator= (Stack<T2,CONT2> const&);
};

template <typename T, template <typename,typename> class CONT>

void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}

template<typename T, template <typename,typename> class CONT>

void Stack<T,CONT>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}

template <typename T, template <typename,typename> class CONT>

T Stack<T,CONT>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}
template <typename T, template <typename,typename> class CONT>
template <typename T2, template <typename,typename> class CONT2>
Stack<T,CONT>&
Stack<T,CONT>::operator= (Stack<T2,CONT2> const& op2)
{
if ((void*)this == (void*)&op2) { // assignment to itself?
return *this;
}

Stack<T2> tmp(op2); // create a copy of the assigned

stack
 elems.clear(); // remove existing elements
while (!tmp.empty()) { // copy all elements
elems.push_front(tmp.top());
tmp.pop();
}
return *this;
}

#endif // STACK_HPP

T h e followi ng p rog ram u s es all featu res of th i s fi nal v ers i on:

// basics/stack8test.cpp

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include "stack8.hpp"

int main()
{
try {
Stack<int> intStack; // stack of ints
Stack<float> floatStack; // stack of floats

// manipulate int stack

intStack.push(42);
intStack.push(7);

// manipulate float stack

floatStack.push(7.7);

// assign stacks of different type

floatStack = intStack;

// print float stack

std::cout << floatStack.top() << std::endl;
floatStack.pop();
std::cout << floatStack.top() << std::endl;
floatStack.pop();
std::cout << floatStack.top() << std::endl;
floatStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
}

// stack for ints using a vector as an internal container

Stack<int,std::vector> vStack;
…
vStack.push(42);
vStack.push(7);
std::cout << vStack.top() << std::endl;
vStack.pop();
}
T h e p rog ram h as th e followi ng ou tp u t:

7
42
Exception: Stack<>::top(): empty stack
7

N ote th at tem p late tem p late p aram eters are one of th e m os t recent featu res
req u i red for com p i lers to conform to th e s tandard. T h u s , th i s p rog ram i s a g ood
ev alu ati on of th e conform i ty of you r com p i ler reg ardi ng tem p late featu res .

F or fu rth er di s cu s s i ons and ex am p les of tem p late tem p late p aram eters , s ee
Secti on 8 .2.3 on p ag e 102 and Secti on 15 .1.6 on p ag e 25 9 .
5.5 Zero Initialization

F or fu ndam ental typ es s u ch as int, double, or p oi nter typ es , th ere i s no defau lt

cons tru ctor th at i ni ti ali z es th em wi th a u s efu l defau lt v alu e. I ns tead, any
noni ni ti ali z ed local v ari able h as an u ndefi ned v alu e:

void foo()
{
int x; // x has undefined value
int* ptr; // ptr points to somewhere (instead of nowhere)
}

N ow i f you wri te tem p lates and want to h av e v ari ables of a tem p late typ e
i ni ti ali z ed by a defau lt v alu e, you h av e th e p roblem th at a s i m p le defi ni ti on
does n' t do th i s for bu i lt-i n typ es :

template <typename T>

void foo()
{
T x; // x has undefined value if T is built-in type
}

F or th i s reas on, i t i s p os s i ble to call ex p li ci tly a defau lt cons tru ctor for bu i lt-i n
typ es th at i ni ti ali z es th em wi th z ero (or false for bool). T h at i s , int() yi elds
z ero. A s a cons eq u ence you can ens u re p rop er defau lt i ni ti ali z ati on ev en for bu i lt-
i n typ es by wri ti ng th e followi ng :

template <typename T>

void foo()
{
T x = T(); // x is zero (or false)ifT is a built-in type
}

T o m ak e s u re th at a m em ber of a clas s tem p late, for wh i ch th e typ e i s

p aram eteri z ed, g ets i ni ti ali z ed, you h av e to defi ne a defau lt cons tru ctor th at u s es
an i ni ti ali z er li s t to i ni ti ali z e th e m em ber:

template <typename T>

class MyClass {
private:
T x;
public:
MyClass() : x() { // ensures that x is initialized even for
built-in types
}
…
};
5.6 Using String Literals as Arguments for Function Templates

P as s i ng s tri ng li teral arg u m ents for reference p aram eters of fu ncti on tem p lates
s om eti m es fai ls i n a s u rp ri s i ng way. C ons i der th e followi ng ex am p le:

// basics/max5.cpp

#include <string>

// note: reference parameters

template <typename T>
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}

int main()
{
std::string s;

::max("apple","peach"); // OK: same type

::max("apple","tomato"); // ERROR: different types
::max("apple",s); // ERROR: different types
}

T h e p roblem i s th at s tri ng li terals h av e di fferent array typ es dep endi ng on th ei r

leng th s . T h at i s , "apple" and "peach" h av e typ e char const[6] wh ereas
"tomato" h as typ e char const[7]. O nly th e fi rs t call i s p os s i ble becau s e th e
tem p late ex p ects both p aram eters to h av e th e s am e typ e. H owev er, i f you
declare nonreference p aram eters , you can s u bs ti tu te th em wi th s tri ng li terals of
di fferent s i z e:

// basics/max6.cpp

#include <string>

// note: nonreference parameters

template <typename T>
inline T max (T a, T b)
{
return a < b ? b : a;
}
int main()
{
std::string s;

::max("apple","peach"); // OK: same type

::max("apple","tomato"); // OK: decays to same type
::max("apple",s); // ERROR: different types
}
T h e ex p lanati on for th i s beh av i or i s th at du ri ng arg u m ent dedu cti on array-to-
p oi nter conv ers i on (often called d ec ay ) occu rs only i f th e p aram eter does not
h av e a reference typ e. T h i s i s dem ons trated by th e followi ng p rog ram :

// basics/refnonref.cpp

#include <typeinfo>
#include <iostream>

template <typename T>

void ref (T const& x)
{
std::cout << "x in ref(T const&): "
<< typeid(x).name() << '\n';
}

template <typename T>

void nonref (T x)
{
std::cout << "x in nonref(T): "
<< typeid(x).name() << '\n';
}

int main()
{
ref("hello");
nonref("hello");
}

T h e ex am p le p as s es a s tri ng li teral to fu ncti on tem p lates th at declare th ei r

p aram eter to be a reference or nonreference res p ecti v ely. B oth fu ncti on
tem p lates u s e th e typeid op erator to p ri nt th e typ e of th e i ns tanti ated
p aram eters . T h e typeid op erator retu rns an lv alu e of typ e std::type_info,
wh i ch encap s u lates a rep res entati on of th e typ e of th e ex p res s i on p as s ed to th e
typeid op erator. T h e m em ber fu ncti on name() of std::type_info i s i ntended
to retu rn a h u m an-readable tex t rep res entati on of th e latter typ e. T h e C + +
s tandard does n' t actu ally s ay th at name() m u s t retu rn s om eth i ng m eani ng fu l,
bu t on g ood C + + i m p lem entati ons , you s h ou ld g et a s tri ng th at g i v es a g ood
des cri p ti on of th e typ e of th e ex p res s i on p as s ed to typeid (wi th s om e
i m p lem entati ons th i s s tri ng i s man g led , bu t a d eman g ler i s av ai lable to tu rn i t
i nto h u m an-readable tex t). F or ex am p le, th e ou tp u t m i g h t be as follows :

x in ref(T const&): char [6]

x in nonref(T): const char *

I f you encou nter a p roblem i nv olv i ng a m i s m atch between an array of ch aracters

and a p oi nter to ch aracters , you m i g h t h av e s tu m bled on th i s s om ewh at
s u rp ri s i ng p h enom enon. [3 ]
T h ere i s u nfortu nately no g eneral s olu ti ons to addres s
th i s p roblem . D ep endi ng on th e contex t, you can

[3 ]
I n fact, th i s i s th e reas on th at you cannot create a p ai r of v alu es
i ni ti ali z ed wi th s tri ng li terals u s i ng th e ori g i nal C + + s tandard li brary
(s ee [Standard9 8 ] ):

std::make_pair("key","value") // ERROR according to

[Standard98]

T h i s was fi x ed wi th th e fi rs t tech ni cal corri g endu m by rep laci ng th e

reference p aram eters of make_pair() by nonreference
p aram eters (s ee [Standard02] ).

• u s e nonreferences i ns tead of references (h owev er, th i s can lead to

u nneces s ary cop yi ng )
• ov erload u s i ng both reference and nonreference p aram eters (h owev er,
th i s m i g h t lead to am bi g u i ti es ; s ee Secti on B .2.2 on p ag e 4 9 2)
• ov erload wi th concrete typ es (s u ch as std::string)
• ov erload wi th array typ es , for ex am p le:
•
• template <typename T, int N, int M>
• T const* max (T const (&a)[N], T const (&b)[M])
• {
• return a < b ? b : a;
}

• force ap p li cati on p rog ram m ers to u s e ex p li ci t conv ers i ons

I n th i s ex am p le i t i s bes t to ov erload max() for s tri ng s (s ee Secti on 2.4 on p ag e

16). T h i s i s neces s ary anyway becau s e wi th ou t ov erloadi ng i n cas es wh ere th e
call to max() i s v ali d for s tri ng li terals , th e op erati on th at i s p erform ed i s a
p oi nter com p ari s on: a<bcom p ares th e addres s es of th e two s tri ng li terals and h as
noth i ng to do wi th lex i cog rap h i cal order. T h i s i s anoth er reas on wh y i t i s u s u ally
p referable to u s e a s tri ng clas s s u ch as std::string i ns tead of C -s tyle s tri ng s .

See Secti on 11.1 on p ag e 168 for detai ls .

5.7 Summary

• T o acces s a typ e nam e th at dep ends on a tem p late p aram eter, you h av e
to q u ali fy th e nam e wi th a leadi ng typename.
• N es ted clas s es and m em ber fu ncti ons can als o be tem p lates . O ne
ap p li cati on i s th e abi li ty to i m p lem ent g eneri c op erati ons wi th i nternal typ e
conv ers i ons . H owev er, typ e ch eck i ng s ti ll occu rs .
• T em p late v ers i ons of as s i g nm ent op erators don' t rep lace defau lt
as s i g nm ent op erators .
• Y ou can als o u s e clas s tem p lates as tem p late p aram eters , as s o-called
template template par ameter s.
• T em p late tem p late arg u m ents m u s t m atch ex actly. D efau lt tem p late
arg u m ents of tem p late tem p late arg u m ents are i g nored.
• B y ex p li ci tly calli ng a defau lt cons tru ctor, you can m ak e s u re th at
v ari ables and m em bers of tem p lates are i ni ti ali z ed by a defau lt v alu e ev en
i f th ey are i ns tanti ated wi th a bu i lt-i n typ e.
• F or s tri ng li terals th ere i s an array-to-p oi nter conv ers i on du ri ng arg u m ent
dedu cti on i f and only i f th e p aram eter i s not a reference.
Chapter 6. Using Templates in Practice

T em p late code i s a li ttle di fferent from ordi nary code. I n s om e ways tem p lates li e
s om ewh ere between m acros and ordi nary (nontem p late) declarati ons . A lth ou g h
th i s m ay be an ov ers i m p li fi cati on, i t h as cons eq u ences not only for th e way we
wri te alg ori th m s and data s tru ctu res u s i ng tem p lates , bu t als o for th e day-to-day
log i s ti cs of ex p res s i ng and analyz i ng p rog ram s i nv olv i ng tem p lates .

I n th i s ch ap ter we addres s s om e of th es e p racti cali ti es wi th ou t neces s ari ly delv i ng

i nto th e tech ni cal detai ls th at u nderli e th em . M any of th es e detai ls are ex p lored i n
C h ap ter 10. T o k eep th e di s cu s s i on s i m p le, we as s u m e th at ou r C + + com p i lati on
s ys tem s cons i s t of fai rly tradi ti onal com p i lers and li nk ers (C + + s ys tem s th at don' t
fall i n th i s categ ory are q u i te rare).
6.1 The Inclusion Model

T h ere are s ev eral ways to org ani z e tem p late s ou rce code. T h i s s ecti on p res ents
th e m os t p op u lar ap p roach as of th e ti m e of th i s wri ti ng : th e i nclu s i on m odel.

6.1.1 Linker Errors

M os t C and C + + p rog ram m ers org ani z e th ei r nontem p late code larg ely as
follows :

• C las s es and oth er typ es are enti rely p laced i n head er f i les. T yp i cally, th i s
i s a fi le wi th a .hpp (or .H, .h, .hh, .hxx) fi lenam e ex tens i on.
• F or g lobal v ari ables and (noni nli ne) fu ncti ons , only a declarati on i s p u t i n a
h eader fi le, and th e defi ni ti on g oes i nto a s o-called d ot-C f i le. T yp i cally,
th i s i s a fi le wi th a .cpp (or .C, .c, .cc, or .hxx) fi lenam e ex tens i on.

T h i s work s well: I t m ak es th e needed typ e defi ni ti on eas i ly av ai lable th rou g h ou t

th e p rog ram and av oi ds du p li cate defi ni ti on errors on v ari ables and fu ncti ons
from th e li nk er.

W i th th es e conv enti ons i n m i nd, a com m on error abou t wh i ch beg i nni ng tem p late
p rog ram m ers com p lai n i s i llu s trated by th e followi ng (erroneou s ) li ttle p rog ram .
A s u s u al for " ordi nary code, " we declare th e tem p late i n a h eader fi le:

// basics/myfirst.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

// declaration of template
template <typename T>
void print_typeof (T const&);

#endif // MYFIRST_HPP

print_typeof() i s th e declarati on of a s i m p le au x i li ary fu ncti on th at p ri nts

s om e typ e i nform ati on. T h e i m p lem entati on of th e fu ncti on i s p laced i n a dot-C
fi le:

// basics/myfirst.cpp

#include <iostream>
#include <typeinfo>
#include "myfirst.hpp"
// implementation/definition of template
template <typename T>
void print_typeof (T const& x)
{
std::cout << typeid(x).name() << std::endl;
}

T h e ex am p le u s es th e typeid op erator to p ri nt a s tri ng th at des cri bes th e typ e of

th e ex p res s i on p as s ed to i t (s ee Secti on 5 .6 on p ag e 5 8 ).

F i nally, we u s e th e tem p late i n anoth er dot-C fi le, i nto wh i ch ou r tem p late

declarati on i s #included:

// basics/myfirstmain.cpp

#include "myfirst.hpp"

// use of the template

int main()
{
double ice = 3.0;
print_typeof(ice); // call function template for type double
}

A C + + com p i ler wi ll m os t li k ely accep t th i s p rog ram wi th ou t any p roblem s , bu t

th e li nk er wi ll p robably rep ort an error, i m p lyi ng th at th ere i s no defi ni ti on of th e
fu ncti on print_typeof().

T h e reas on for th i s error i s th at th e defi ni ti on of th e fu ncti on tem p late

print_typeof() h as not been i ns tanti ated. I n order for a tem p late to be
i ns tanti ated, th e com p i ler m u s t k now wh i ch defi ni ti on s h ou ld be i ns tanti ated and
for wh at tem p late arg u m ents i t s h ou ld be i ns tanti ated. U nfortu nately, i n th e
p rev i ou s ex am p le, th es e two p i eces of i nform ati on are i n fi les th at are com p i led
s ep arately. T h erefore, wh en ou r com p i ler s ees th e call to print_typeof() bu t
h as no defi ni ti on i n s i g h t to i ns tanti ate th i s fu ncti on for double, i t j u s t as s u m es
th at s u ch a defi ni ti on i s p rov i ded els ewh ere and creates a reference (for th e li nk er
to res olv e) to th at defi ni ti on. O n th e oth er h and, wh en th e com p i ler p roces s es th e
fi le myfirst.cpp, i t h as no i ndi cati on at th at p oi nt th at i t m u s t i ns tanti ate th e
tem p late defi ni ti on i t contai ns for s p eci fi c arg u m ents .

6.1.2 Templates in Header Files

T h e com m on s olu ti on to th e p rev i ou s p roblem i s to u s e th e s am e ap p roach th at

we wou ld tak e wi th m acros or wi th i nli ne fu ncti ons : W e i nclu de th e defi ni ti ons of
a tem p late i n th e h eader fi le th at declares th at tem p late. F or ou r ex am p le, we
can do th i s by addi ng

#include "myfirst.cpp"
at th e end of myfirst.hpp or by i nclu di ng myfirst.cpp i n ev ery dot-C fi le th at
u s es th e tem p late. A th i rd way, of cou rs e, i s to do away enti rely wi th
myfirst.cpp and rewri te myfirst.hpp s o th at i t contai ns all tem p late
declarati ons an d tem p late defi ni ti ons :

// basics/myfirst2.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

#include <iostream>
#include <typeinfo>

// declaration of template
template <typename T>
void print_typeof (T const&);

// implementation/definition of template
template <typename T>
void print_typeof (T const& x)
{
std::cout << typeid(x).name() << std::endl;
}

#endif // MYFIRST_HPP

T h i s way of org ani z i ng tem p lates i s called th e i n c lu si on mod el. W i th th i s i n p lace,

you s h ou ld fi nd th at ou r p rog ram now correctly com p i les , li nk s , and ex ecu tes .

T h ere are a few obs erv ati ons we can m ak e at th i s p oi nt. T h e m os t notable i s th at
th i s ap p roach h as cons i derably i ncreas ed th e cos t of i nclu di ng th e h eader fi le
myfirst.hpp. I n th i s ex am p le, th e cos t i s not th e res u lt of th e s i z e of th e
tem p late defi ni ti on i ts elf, bu t th e res u lt of th e fact th at we m u s t als o i nclu de th e
h eaders u s ed by th e defi ni ti on of ou r tem p late—i n th i s cas e <iostream> and
<typeinfo>. Y ou m ay fi nd th at th i s am ou nts to tens of th ou s ands of li nes of
code becau s e h eaders li k e <iostream> contai n s i m i lar tem p late defi ni ti ons .

T h i s i s a real p roblem i n p racti ce becau s e i t cons i derably i ncreas es th e ti m e

needed by th e com p i ler to com p i le s i g ni fi cant p rog ram s . W e wi ll th erefore
ex am i ne s om e p os s i ble ways to ap p roach th i s p roblem i n u p com i ng s ecti ons .
H owev er, real-world p rog ram s q u i ck ly end u p tak i ng h ou rs to com p i le and li nk
(we h av e been i nv olv ed i n s i tu ati ons i n wh i ch i t li terally took days to bu i ld a
p rog ram com p letely from i ts s ou rce code).

D es p i te th i s bu i ld-ti m e i s s u e, we do recom m end followi ng th i s i nclu s i on m odel to

org ani z e you r tem p lates wh en p os s i ble. W e ex am i ne two alternati v es , bu t i n ou r
op i ni on th ei r eng i neeri ng defi ci enci es are m ore s eri ou s th an th e bu i ld-ti m e i s s u e
di s cu s s ed h ere. T h ey m ay h av e oth er adv antag es not di rectly related to th e
eng i neeri ng as p ects of s oftware dev elop m ent, h owev er.

A noth er (m ore s u btle) obs erv ati on abou t th e i nclu s i on ap p roach i s th at noni nli ne
fu ncti on tem p lates are di s ti nct from i nli ne fu ncti ons and m acros i n an i m p ortant
way: T h ey are not ex p anded at th e call s i te. I ns tead, wh en th ey are i ns tanti ated,
th ey create a new cop y of a fu ncti on. B ecau s e th i s i s an au tom ati c p roces s , a
com p i ler cou ld end u p creati ng two cop i es i n two di fferent fi les , and s om e li nk ers
cou ld i s s u e errors wh en th ey fi nd two di s ti nct defi ni ti ons for th e s am e fu ncti on. I n
th eory, th i s s h ou ld not be a concern of ou rs : I t i s a p roblem for th e C + +
com p i lati on s ys tem to accom m odate. I n p racti ce, th i ng s work well m os t of th e
ti m e, and we don' t need to deal wi th th i s i s s u e at all. F or larg e p roj ects th at
create th ei r own li brary of code, h owev er, p roblem s occas i onally s h ow u p . A
di s cu s s i on of i ns tanti ati on s ch em es i n C h ap ter 10 and a clos e s tu dy of th e
docu m entati on th at cam e wi th th e C + + trans lati on s ys tem (com p i ler) s h ou ld h elp
addres s th es e p roblem s .

F i nally, we need to p oi nt ou t th at wh at ap p li es to th e ordi nary fu ncti on tem p late

i n ou r ex am p le als o ap p li es to m em ber fu ncti ons and s tati c data m em bers of
clas s tem p lates , as well as to m em ber fu ncti on tem p lates .
6.2 Explicit Instantiation

T h e i nclu s i on m odel ens u res th at all th e needed tem p lates are i ns tanti ated. T h i s
h ap p ens becau s e th e C + + com p i lati on s ys tem au tom ati cally g enerates th os e
i ns tanti ati ons as th ey are needed. T h e C + + s tandard als o offers a cons tru ct to
i ns tanti ate tem p lates m anu ally: th e ex pli c i t i n stan ti ati on d i r ec ti v e.

6.2.1 Example of Explicit Instantiation

T o i llu s trate m anu al i ns tanti ati on, let' s rev i s i t ou r ori g i nal ex am p le th at leads to a
li nk er error (s ee p ag e 62). T o av oi d th i s error we add th e followi ng fi le to ou r
p rog ram :

// basics/myfirstinst.cpp

#include "myfirst.cpp"

// explicitly instantiate print_typeof() for type double

template void print_typeof<double>(double const&);

T h e ex p li ci t i ns tanti ati on di recti v e cons i s ts of th e k eyword template followed by

th e fu lly s u bs ti tu ted declarati on of th e enti ty we want to i ns tanti ate. I n ou r
ex am p le, we do th i s wi th an ordi nary fu ncti on, bu t i t cou ld be a m em ber fu ncti on
or a s tati c data m em ber. F or ex am p le:

// explicitly instantiate a constructor of MyClass<> for int

template MyClass<int>::MyClass();

// explicitly instantiate a function template max() for int

template int const& max (int const&, int const&);

Y ou can als o ex p li ci tly i ns tanti ate a clas s tem p late, wh i ch i s s h ort for req u es ti ng
th e i ns tanti ati on of all i ts i ns tanti atable m em bers . T h i s ex clu des m em bers th at
were p rev i ou s ly s p eci ali z ed as well as th os e th at were already i ns tanti ated:

// explicitly instantiate class Stack<> for int:

template class Stack<int>;

// explicitly instantiate some member functions of Stack<> for

strings:
template Stack<std::string>::Stack();
template void Stack<std::string>::push(std::string const&);
template std::string Stack<std::string>::top();

// ERROR: can't explicitly instantiate a member function of a

// class that was itself explicitly instantiated:
template Stack<int>::Stack();
T h ere s h ou ld be, at m os t, one ex p li ci t i ns tanti ati on of each di s ti nct enti ty i n a
p rog ram . I n oth er words , you cou ld ex p li ci tly i ns tanti ate both
print_typeof<int> and print_typeof<double>, bu t each di recti v e s h ou ld
ap p ear only once i n a p rog ram . N ot followi ng th i s ru le u s u ally res u lts i n li nk er
errors th at rep ort du p li cate defi ni ti ons of th e i ns tanti ated enti ti es .

M anu al i ns tanti ati on h as a clear di s adv antag e: W e m u s t carefu lly k eep track of
wh i ch enti ti es to i ns tanti ate. F or larg e p roj ects th i s q u i ck ly becom es an ex ces s i v e
bu rden; h ence we do not recom m end i t. W e h av e work ed on s ev eral p roj ects th at
i ni ti ally u nderes ti m ated th i s bu rden, and we cam e to reg ret ou r deci s i on as th e
code m atu red.

H owev er, ex p li ci t i ns tanti ati on als o h as a few adv antag es becau s e th e

i ns tanti ati on can be tu ned to th e needs of th e p rog ram . C learly, th e ov erh ead of
larg e h eaders i s av oi ded. T h e s ou rce code of tem p late defi ni ti on can be k ep t
h i dden, bu t th en no addi ti onal i ns tanti ati ons can be created by a cli ent p rog ram .
F i nally, for s om e ap p li cati ons i t can be u s efu l to control th e ex act locati on (th at i s ,
th e obj ect fi le) of a tem p late i ns tance. W i th au tom ati c i ns tanti ati on, th i s m ay not
be p os s i ble (s ee C h ap ter 10 for detai ls ).

6.2.2 Combining the Inclusion Model and Explicit Instantiation

T o k eep th e deci s i on op en wh eth er to u s e th e i nclu s i on m odel or ex p li ci t

i ns tanti ati on, we can p rov i de th e declarati on and th e defi ni ti on of tem p lates i n
two di fferent fi les . I t i s com m on p racti ce to h av e both fi les nam ed as h eader fi les
(u s i ng an ex tens i on ordi nari ly u s ed for fi les th at are i ntended to be #included),
and i t i s p robably wi s e to s ti ck to th i s conv enti on. (T h u s , myfirst.cpp of ou r
m oti v ati ng ex am p le becom es myfirstdef.hpp, wi th p rep roces s or g u ards
arou nd th e code i ns erted.) F i g u re 6.1 dem ons trates th i s for a Stack<> clas s
tem p late.

Figu r e 6 . 1 . S e p a r a t io n o f t e m p la t e d e c l a r a t io n a n d d e f in it io n
N ow i f we want to u s e th e i nclu s i on m odel, we can s i m p ly i nclu de th e defi ni ti on
h eader fi le stackdef.hpp. A lternati v ely, i f we want to i ns tanti ate th e tem p lates
ex p li ci tly, we can i nclu de th e declarati on h eader stack.hpp and p rov i de a dot-C
fi le wi th th e neces s ary ex p li ci t i ns tanti ati on di recti v es (s ee F i g u re 6.2).

Figu r e 6 . 2 . E x p l ic it in s t a n t ia t io n w it h t w o t e m p l a t e h e a d e r f il e s
6.3 The Separation Model

B oth ap p roach es adv ocated i n th e p rev i ou s s ecti ons work well and conform
enti rely to th e C + + s tandard. H owev er, th i s s am e s tandard als o p rov i des th e
alternati v e m ech ani s m of ex por ti n g tem p lates . T h i s ap p roach i s s om eti m es called
th e C + + tem p late separ ati on mod el.

6.3.1 The Keyword export

I n p ri nci p le, i t i s q u i te s i m p le to m ak e u s e of th e export faci li ty: D efi ne th e

tem p late i n j u s t one fi le, and m ark th at defi ni ti on and all i ts nondefi ni ng
declarati ons wi th th e k eyword export. F or th e ex am p le i n th e p rev i ou s s ecti on,
th i s res u lts i n th e followi ng fu ncti on tem p late declarati on:

// basics/myfirst3.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

// declaration of template
export
template <typename T>
void print_typeof (T const&);

#endif // MYFIRST_HPP

E x p orted tem p lates can be u s ed wi th ou t th ei r defi ni ti on bei ng v i s i ble. I n oth er

words , th e p oi nt wh ere a tem p late i s bei ng u s ed and th e p oi nt wh ere i t i s defi ned
can be i n two di fferent trans lati on u ni ts . I n ou r ex am p le, th e fi le myfirst.hpp
now contai ns only th e d ec lar ati on of th e m em ber fu ncti ons of th e clas s tem p late,
and th i s i s s u ffi ci ent to u s e th os e m em bers . C om p ari ng th i s wi th th e ori g i nal code
th at was tri g g eri ng li nk er errors , we h ad to add only one export k eyword i n ou r
code and th i ng s now work j u s t fi ne.

W i th i n a p rep roces s ed fi le (th at i s , wi th i n a trans lati on u ni t), i t i s s u ffi ci ent to

m ark th e fi rs t declarati on of a tem p late wi th export. L ater redeclarati ons ,
i nclu di ng defi ni ti ons , i m p li ci tly k eep th at attri bu te. T h i s i s wh y myfirst.cpp
does not need to be m odi fi ed i n ou r ex am p le. T h e defi ni ti ons i n th i s fi le are
i m p li ci tly ex p orted becau s e th ey were s o declared i n th e #included h eader fi le.
O n th e oth er h and, i t i s p erfectly accep table to p rov i de redu ndant export
k eywords on tem p late defi ni ti ons , and doi ng s o m ay i m p rov e th e readabi li ty of
th e code.

T h e k eyword export really ap p li es to fu ncti on tem p lates , m em ber fu ncti ons of

clas s tem p lates , m em ber fu ncti on tem p lates , and s tati c data m em bers of clas s
tem p lates . export can als o be ap p li ed to a clas s tem p late declarati on. I t i m p li es
th at ev ery one of i ts ex p ortable m em bers i s ex p orted, bu t clas s tem p lates
th em s elv es are not actu ally ex p orted (h ence, th ei r defi ni ti ons s ti ll ap p ear i n
h eader fi les ). Y ou can s ti ll h av e i m p li ci tly or ex p li ci tly defi ned i nli ne m em ber
fu ncti ons . H owev er, th es e i nli ne fu ncti ons are not ex p orted:

export template <typename T>

class MyClass {
public:
void memfun1(); // exported
void memfun2() { // not exported because implicitly inline
…
}
void memfun3(); // not exported because explicitly inline
…
};

template <typename T>

inline void MyClass<T>::memfun3 ()
{
…
}

H owev er, note th at th e k eyword export cannot be com bi ned wi th inline and
m u s t always p recede th e k eyword template. T h e followi ng i s i nv ali d:

template <typename T>

class Invalid {
public:
export void wrong(T); // ERROR: export not followed by
template
};

export template<typename T> // ERROR: both export and inline

inline void Invalid<T>::wrong(T)
{
}

export inline T const& max (T const&a, T const& b)

{ // ERROR: both export and inline
return a < b ? b : a;
}

6.3.2 Limitations of the Separation Model

A t th i s p oi nt i t i s reas onable to wonder wh y we' re s ti ll adv ocati ng th e i nclu s i on

ap p roach wh en ex p orted tem p lates s eem to offer j u s t th e ri g h t m ag i c to m ak e
th i ng s work . T h ere are a few di fferent as p ects to th i s ch oi ce.

F i rs t, ev en fou r years after th e s tandard cam e ou t, only one com p any h as actu ally
i m p lem ented s u p p ort for th e export k eyword. [1]
T h erefore, ex p eri ence wi th th i s
featu re i s not as wi des p read as oth er C + + featu res . C learly, th i s als o m eans th at
at th i s p oi nt ex p eri ence wi th ex p orted tem p lates i s fai rly li m i ted, and all ou r
obs erv ati ons wi ll u lti m ately h av e to be tak en wi th a g rai n of s alt. I t i s p os s i ble
th at s om e of ou r m i s g i v i ng s wi ll be addres s ed i n th e fu tu re (and we s h ow h ow to
p rep are for th at ev entu ali ty).

[1]
A s far as we k now, E di s on D es i g n G rou p , I nc. (E D G ) i s s ti ll th at
com p any (s ee [E D G ] ). T h ei r tech nolog y i s av ai lable th rou g h oth er
v endors , h owev er.

Second, alth ou g h export m ay s eem q u as i -m ag i cal, i t i s not ac tu ally m ag i cal.

U lti m ately, th e i ns tanti ati on p roces s h as to deal wi th both th e p lace wh ere a
tem p late i s i ns tanti ated and th e p lace wh ere i ts defi ni ti on ap p ears . H ence,
alth ou g h th es e two s eem neatly decou p led i n th e s ou rce code, th ere i s an
i nv i s i ble cou p li ng th at th e s ys tem es tabli s h es beh i nd th e s cenes . T h i s m ay m ean,
for ex am p le, th at i f th e fi le contai ni ng th e defi ni ti on ch ang es , both th at fi le and all
th e fi les th at i ns tanti ate th e tem p lates i n th at fi le m ay need to be recom p i led.
T h i s i s not s u bs tanti ally di fferent from th e i nclu s i on ap p roach , bu t i t i s no long er
obv i ou s ly v i s i ble i n th e s ou rce code. A s a cons eq u ence, dep endency m anag em ent
tools (s u ch as th e p op u lar make and nmake p rog ram s ) th at u s e tradi ti onal
s ou rce-bas ed tech ni q u es no long er work . I t als o m eans th at q u i te a few bi ts of
ex tra p roces s i ng by th e com p i ler are needed to k eep all th e book k eep i ng s trai g h t;
and i n th e end, th e bu i ld ti m es m ay not be better th an th os e of th e i nclu s i on
ap p roach .

F i nally, ex p orted tem p lates m ay lead to s u rp ri s i ng s em anti c cons eq u ences , th e

detai ls of wh i ch are ex p lai ned i n C h ap ter 10.

A com m on m i s concep ti on i s th at th e export m ech ani s m offers th e p otenti al of

bei ng able to s h i p li brari es of tem p lates wi th ou t rev eali ng th e s ou rce code for
th ei r defi ni ti ons (j u s t li k e li brari es of nontem p late enti ti es ). [2 ]
T h is is a
m i s concep ti on i n th e s ens e th at h i di ng code i s not a lang u ag e i s s u e: I t wou ld be
eq u ally p os s i ble to p rov i de a m ech ani s m to h i de i nclu ded tem p late defi ni ti ons as
to h i de ex p orted tem p late defi ni ti ons . A lth ou g h th i s m ay be feas i ble (th e cu rrent
i m p lem entati ons do not s u p p ort th i s m odel), i t u nfortu nately creates new
ch alleng es i n deali ng wi th tem p late com p i lati on errors th at need to refer to th e
h i dden s ou rce code.

[2 ]
N ot ev erybody cons i ders th i s c losed -sou r c e ap p roach a p lu s .

6.3.3 Preparing for the Separation Model

O ne work able i dea i s to p rep are ou r s ou rces i n s u ch a way th at we can eas i ly

s wi tch between th e i nclu s i on and ex p ort m odels u s i ng a h arm les s dos e of
p rep roces s or di recti v es . H ere i s h ow i t can be done for ou r s i m p le ex am p le:

// basics/myfirst4.hpp

#ifndef MYFIRST_HPP
#define MYFIRST_HPP

// use export if USE_EXPORT is defined

#if defined(USE_EXPORT)
#define EXPORT export
#else
#define EXPORT
#endif

// declaration of template
EXPORT
template <typename T>
void print_typeof (T const&);

// include definition if USE_EXPORT is not defined

#if !defined(USE_EXPORT)
#include "myfirst.cpp"
#endif

#endif // MYFIRST_HPP

B y defi ni ng or om i tti ng th e p rep roces s or s ym bol USE_EXPORT, we can now s elect

between th e two m odels . I f a p rog ram defi nes USE_EXPORT before i t i nclu des
myfirst.hpp, th e s ep arati on m odel i s u s ed:

// use separation model:

#define USE_EXPORT
#include "myfirst.hpp"
…

I f a p rog ram does not defi ne USE_EXPORT, th e i nclu s i on m odel i s u s ed becau s e i n

th i s cas e myfirst.hpp au tom ati cally i nclu des th e defi ni ti ons i n myfirst.cpp:

// use inclusion model:

#include "myfirst.hpp"
…

D es p i te th i s flex i bi li ty, we s h ou ld rei terate th at bes i des th e obv i ou s log i s ti cal

di fferences , th ere can be s u btle s em anti c di fferences between th e two m odels .

N ote th at we can als o ex p li ci tly i ns tanti ate ex p orted tem p lates . I n th i s cas e th e
tem p late defi ni ti on can be i n anoth er fi le. T o be able to ch oos e between th e
i nclu s i on m odel, th e s ep arati on m odel, and ex p li ci t i ns tanti on, we can com bi ne
th e org ani z ati on controlled by USE_EXPORT wi th th e conv enti ons des cri bed i n
Secti on 6.2.2 on p ag e 67 .
6.4 Templates and inline

D eclari ng s h ort fu ncti ons to be i nli ne i s a com m on tool to i m p rov e th e ru nni ng

ti m e of p rog ram s . T h e inline s p eci fi er i ndi cates to th e i m p lem entati on th at
i nli ne s u bs ti tu ti on of th e fu ncti on body at th e p oi nt of call i s p referred ov er th e
u s u al fu ncti on call m ech ani s m . H owev er, an i m p lem entati on i s not req u i red to
p erform th i s i nli ne s u bs ti tu ti on at th e p oi nt of call.

B oth fu ncti on tem p lates and i nli ne fu ncti ons can be defi ned i n m u lti p le trans lati on
u ni ts . T h i s i s u s u ally ach i ev ed by p laci ng th e defi ni ti on i n a h eader fi le th at i s
i nclu ded by m u lti p le dot-C fi les .

T h i s m ay lead to th e i m p res s i on th at fu ncti on tem p lates are i nli ne by defau lt.

H owev er, th ey' re not. I f you wri te fu ncti on tem p lates th at s h ou ld be h andled as
i nli ne fu ncti ons , you s h ou ld u s e th e inline s p eci fi er (u nles s th e fu ncti on i s i nli ne
already becau s e i t i s defi ned i ns i de a clas s defi ni ti on).

T h erefore, m any s h ort tem p late fu ncti ons th at are not p art of a clas s defi ni ti on
s h ou ld be declared wi th inline. [3 ]

[3 ]
W e m ay not always ap p ly th i s ru le of th u m b becau s e i t m ay
di s tract from th e top i c at h and.
6.5 Precompiled Headers

E v en wi th ou t tem p lates , C + + h eader fi les can becom e v ery larg e and th erefore
tak e a long ti m e to com p i le. T em p lates add to th i s tendency, and th e ou tcry of
wai ti ng p rog ram m ers h as i n m any cas es dri v en v endors to i m p lem ent a s ch em e
u s u ally k nown as pr ec ompi led head er s. T h i s s ch em e op erates ou ts i de th e s cop e
of th e s tandard and reli es on v endor-s p eci fi c op ti ons . A lth ou g h we leav e th e
detai ls on h ow to create and u s e p recom p i led h eader fi les to th e docu m entati on
of th e v ari ou s C + + com p i lati on s ys tem s th at h av e th i s featu re, i t i s u s efu l to g ai n
s om e u nders tandi ng of h ow i t work s .

W h en a com p i ler trans lates a fi le, i t does s o s tarti ng from th e beg i nni ng of th e fi le
and work s th rou g h to th e end. A s i t p roces s es each tok en from th e fi le (wh i ch
m ay com e from #included fi les ), i t adap ts i ts i nternal s tate, i nclu di ng s u ch
th i ng s as addi ng entri es to a table of s ym bols s o th ey m ay be look ed u p later.
W h i le doi ng s o, th e com p i ler m ay als o g enerate code i n obj ect fi les .

T h e p recom p i led h eader s ch em e reli es on th e fact th at code can be org ani z ed i n

s u ch a m anner th at m any fi les s tart wi th th e s am e li nes of code. L et' s as s u m e for
th e s ak e of arg u m ent th at ev ery fi le to be com p i led s tarts wi th th e s am e N li nes
of code. W e cou ld com p i le th es e N li nes and s av e th e com p lete s tate of th e
com p i ler at th at p oi nt i n a s o-called pr ec ompi led head er . T h en, for ev ery fi le i n
ou r p rog ram , we cou ld reload th e s av ed s tate and s tart com p i lati on at li ne N+1 .
A t th i s p oi nt i t i s worth wh i le to note th at reloadi ng th e s av ed s tate i s an op erati on
th at can be orders of m ag ni tu de fas ter th an actu ally com p i li ng th e fi rs t N li nes .
H owev er, s av i ng th e s tate i n th e fi rs t p lace i s typ i cally m ore ex p ens i v e th an j u s t
com p i li ng th e N li nes . T h e i ncreas e i n cos t v ari es rou g h ly from 20 to 200 p ercent.

T h e k ey to m ak i ng effecti v e u s e of p recom p i led h eaders i s to ens u re th at—as

m u ch as p os s i ble— fi les s tart wi th a m ax i m u m nu m ber of com m on li nes of code.
I n p racti ce th i s m eans th e fi les m u s t s tart wi th th e s am e #include di recti v es ,
wh i ch (as m enti oned earli er) cons u m e a s u bs tanti al p orti on of ou r bu i ld ti m e.
H ence, i t can be v ery adv antag eou s to p ay attenti on to th e order i n wh i ch
h eaders are i nclu ded. F or ex am p le, th e followi ng two fi les

#include <iostream>
#include <vector>
#include <list>
…

and
#include <list>
#include <vector>
…

i nh i bi t th e u s e of p recom p i led h eaders becau s e th ere i s no com m on i ni ti al s tate i n

th e s ou rces .

Som e p rog ram m ers deci de th at i t i s better to #include s om e ex tra u nneces s ary
h eaders th an to p as s on an op p ortu ni ty to accelerate th e trans lati on of a fi le
u s i ng a p recom p i led h eader. T h i s deci s i on can cons i derably eas e th e m anag em ent
of th e i nclu s i on p oli cy. F or ex am p le, i t i s u s u ally relati v ely s trai g h tforward to
create a h eader fi le nam ed std.hpp th at i nclu des all th e s tandard h eaders [4 ]
:

[4 ]
I n th eory, th e s tandard h eaders do not actu ally need to
corres p ond to p h ys i cal fi les . I n p racti ce, h owev er, th ey do, and th e
fi les are v ery larg e.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
…

T h i s fi le can th en be p recom p i led, and ev ery p rog ram fi le th at m ak es u s e of th e

s tandard li brary can th en s i m p ly be s tarted as follows :

#include "std.hpp"
…

N orm ally th i s wou ld tak e a wh i le to com p i le, bu t g i v en a s ys tem wi th s u ffi ci ent

m em ory, th e p recom p i led h eader s ch em e allows i t to be p roces s ed s i g ni fi cantly
fas ter th an alm os t any s i ng le s tandard h eader wou ld req u i re wi th ou t
p recom p i lati on. T h e s tandard h eaders are p arti cu larly conv eni ent i n th i s way
becau s e th ey rarely ch ang e, and h ence th e p recom p i led h eader for ou r std.hpp
fi le can be bu i lt once. [5 ]
O th erwi s e, p recom p i led h eaders are typ i cally p art of th e
dep endency confi g u rati on of a p roj ect (for ex am p le, th ey are u p dated as needed
by th e p op u lar make tool).

[5 ]
Som e com m i ttee m em bers fi nd th e concep t of a com p reh ens i v e
std.hpp h eader s o conv eni ent th at th ey h av e s u g g es ted
i ntrodu ci ng i t as a s tandard h eader. W e wou ld th en be able to wri te
#include <std>. Som e ev en s u g g es t th at i t s h ou ld be i m p li ci tly
i nclu ded s o th at all th e s tandard li brary faci li ti es becom e av ai lable
wi th ou t #include.

O ne attracti v e ap p roach to m anag e p recom p i led h eaders i s to create lay er s of

p recom p i led h eaders th at g o from th e m os t wi dely u s ed and s table h eaders (for
ex am p le, ou r std.hpp h eader) to h eaders th at aren' t ex p ected to ch ang e all th e
ti m e and th erefore are s ti ll worth p recom p i li ng . H owev er, i f h eaders are u nder
h eav y dev elop m ent, creati ng p recom p i led h eaders for th em can tak e m ore ti m e
th an wh at i s s av ed by reu s i ng th em . A k ey concep t to th i s ap p roach i s th at a
p recom p i led h eader for a m ore s table layer can be reu s ed to i m p rov e th e
p recom p i lati on ti m e of a les s s table h eader. F or ex am p le, s u p p os e th at i n addi ti on
to ou r std.hpp h eader (wh i ch we h av e p recom p i led), we als o defi ne a core.hpp
h eader th at i nclu des addi ti onal faci li ti es th at are s p eci fi c to ou r p roj ect bu t
noneth eles s ach i ev e a certai n lev el of s tabi li ty:

#include "std.hpp"
#include "core_data.hpp"
#include "core_algos.hpp"
…

B ecau s e th i s fi le s tarts wi th #include "std.hpp", th e com p i ler can load th e

as s oci ated p recom p i led h eader and conti nu e wi th th e nex t li ne wi th ou t
recom p i li ng all th e s tandard h eaders . W h en th e fi le i s com p letely p roces s ed, a
new p recom p i led h eader can be p rodu ced. A p p li cati ons can th en u s e #include
"core.hpp" to p rov i de acces s q u i ck ly to larg e am ou nts of fu ncti onali ty becau s e
th e com p i ler can load th e latter p recom p i led h eader.
6.6 Debugging Templates

T em p lates rai s e two clas s es of ch alleng es wh en i t com es to debu g g i ng th em . O ne s et of

ch alleng es i s defi ni tely a p roblem for wri ters of tem p lates : H ow can we ens u re th at th e
tem p lates we wri te wi ll fu ncti on for an y tem p late arg u m ents th at s ati s fy th e condi ti ons we
docu m ent? T h e oth er clas s of p roblem s i s alm os t ex actly th e op p os i te: H ow can a u s er of a
tem p late fi nd ou t wh i ch of th e tem p late p aram eter req u i rem ents i t v i olated wh en th e tem p late
does not beh av e as docu m ented?

B efore we di s cu s s th es e i s s u es i n dep th , i t i s u s efu l to contem p late th e k i nds of cons trai nts

th at m ay be i m p os ed on tem p late p aram eters . I n th i s s ecti on we deal m os tly wi th th e
cons trai nts th at lead to com p i lati on errors wh en v i olated, and we call th es e cons trai nts
sy n tac ti c c on str ai n ts. Syntacti c cons trai nts can i nclu de th e need for a certai n k i nd of
cons tru ctor to ex i s t, for a p arti cu lar fu ncti on call to be u nam bi g u ou s , and s o forth . T h e oth er
k i nd of cons trai nt we call seman ti c c on str ai n ts. T h es e cons trai nts are m u ch h arder to v eri fy
m ech ani cally. I n th e g eneral cas e, i t m ay not ev en be p racti cal to do s o. F or ex am p le, we m ay
req u i re th at th ere be a < op erator defi ned on a tem p late typ e p aram eter (wh i ch i s a s yntacti c
cons trai nt), bu t u s u ally we' ll als o req u i re th at th e op erator actu ally defi nes s om e s ort of
orderi ng on i ts dom ai n (wh i ch i s a s em anti c cons trai nt).

T h e term c on c ept i s often u s ed to denote a s et of cons trai nts th at i s rep eatedly req u i red i n a
tem p late li brary. F or ex am p le, th e C + + s tandard li brary reli es on s u ch concep ts as r an d om
ac c ess i ter ator and d ef au lt c on str u c ti b le. C oncep ts can form h i erarch i es i n th e s ens e th at one
concep t can be a refi nem ent of anoth er. T h e m ore refi ned concep t i nclu des all th e cons trai nts
of th e oth er concep t bu t adds a few m ore. F or ex am p le, th e concep t r an d om ac c ess i ter ator
refi nes th e concep t b i d i r ec ti on al i ter ator i n th e C + + s tandard li brary. W i th th i s term i nolog y i n
p lace, we can s ay th at debu g g i ng tem p late code i nclu des a s i g ni fi cant am ou nt of determ i ni ng
h ow concep ts are v i olated i n th e tem p late i m p lem entati on and i n th ei r u s e.

6.6.1 Decoding the Error Novel

O rdi nary com p i lati on errors are norm ally q u i te s u cci nct and to th e p oi nt. F or ex am p le, wh en a
com p i ler s ays " class X has no member 'fun', " i t u s u ally i s n' t too h ard to fi g u re ou t wh at
i s wrong i n ou r code (for ex am p le, we m i g h t h av e m i s typ ed run as fun). N ot s o wi th
tem p lates . C ons i der th e followi ng relati v ely s i m p le code ex cerp t u s i ng th e C + + s tandard
li brary. I t contai ns a fai rly s m all m i s tak e: list<string> i s u s ed, bu t we are s earch i ng u s i ng
a greater<int> fu ncti on obj ect, wh i ch s h ou ld h av e been a greater<string> obj ect:

std::list<std::string> coll;
…
// Find the first element greater than "A"
std::list<std::string>::iterator pos;
 pos = std::find_if(coll.begin(),coll.end(), // range
std::bind2nd(std::greater<int>(),"A")); // criterion

T h i s s ort of m i s tak e com m only h ap p ens wh en cu tti ng and p as ti ng s om e code and forg etti ng to
adap t p arts of i t.

A v ers i on of th e p op u lar G N U C + + com p i ler rep orts th e followi ng error:

/local/include/stl/_algo.h: In function 'struct _STL::_List_iterator<_STL::basic

_string<char,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Nonconst_tra
its<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > > >
_STL::find_if<_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<cha
r>,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::
char_traits<char>,_STL::allocator<char> > > >, _STL::binder2nd<_STL::greater<int
> > >(_STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char>,_STL:
:allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_tra
its<char>,_STL::allocator<char> > > >, _STL::_List_iterator<_STL::basic_string<c
har,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL:
:basic_string<char,_STL::char_traits<char>,_STL::allocator<char> > > >, _STL::bi
nder2nd<_STL::greater<int> >, _STL::input_iterator_tag)':
/local/include/stl/_algo.h:115: instantiated from '_STL::find_if<_STL::_List_i
terator<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> >,
_STL::_Nonconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::all
ocator<char> > > >, _STL::binder2nd<_STL::greater<int> > >(_STL::_List_iterator<
_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<char> >,_STL::_N
onconst_traits<_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<c
har> > > >, _STL::_List_iterator<_STL::basic_string<char,_STL::char_traits<char>
,_STL::allocator<char> >,_STL::_Nonconst_traits<_STL::basic_string<char,_STL::ch
ar_traits<char>,_STL::allocator<char> > > >, _STL::binder2nd<_STL::greater<int>
>)'
testprog.cpp:18: instantiated from here
/local/include/stl/_algo.h:78: no match for call to '(_STL::binder2nd<_STL::grea
ter<int> >) (_STL::basic_string<char,_STL::char_traits<char>,_STL::allocator<cha
r> > &)'
/local/include/stl/_function.h:261: candidates are: bool _STL::binder2nd<_STL::g
reater<int> >::operator ()(const int &) const

A m es s ag e li k e th i s s tarts look i ng m ore li k e a nov el th an a di ag nos ti c. I t can als o be

ov erwh elm i ng to th e p oi nt of di s cou rag i ng nov i ce tem p late u s ers . H owev er, wi th s om e
p racti ce, m es s ag es li k e th i s becom e m anag eable, and th e errors are relati v ely eas i ly located.

T h e fi rs t p art of th i s error m es s ag e s ays th at an error occu rred i n a fu ncti on tem p late i ns tance
(wi th a h orri bly long nam e) deep i ns i de th e /local/include/stl/_algo.h h eader. N ex t,
th e com p i ler rep orts wh y i t i ns tanti ated th at p arti cu lar i ns tance. I n th i s cas e i t all s tarted on
li ne 18 of testprog.cpp (wh i ch i s th e fi le contai ni ng ou r ex am p le code), wh i ch cau s ed th e
i ns tanti ati on of a find_if tem p late on li ne 115 of th e _algo.h h eader. T h e com p i ler rep orts
all th i s i n cas e we s i m p ly were not ex p ecti ng all th es e tem p lates to be i ns tanti ated. I t allows
u s to determ i ne th e ch ai n of ev ents th at cau s ed th e i ns tanti ati ons .

H owev er, i n ou r ex am p le we' re wi lli ng to beli ev e th at all k i nds of tem p lates needed to be
i ns tanti ated, and we j u s t wonder wh y i t di dn' t work . T h i s i nform ati on com es i n th e las t p art of
th e m es s ag e: T h e p art th at s ays " no match for call" i m p li es th at a fu ncti on call cou ld not
be res olv ed becau s e th e typ es of th e arg u m ents and th e p aram eter typ es di dn' t m atch .
F u rth erm ore, j u s t after th i s , th e li ne contai ni ng " candidates are" ex p lai ns th at th ere was a
s i ng le candi date typ e ex p ecti ng an i nteg er typ e (p aram eter typ e const int&). L ook i ng back
at li ne 18 of th e p rog ram , we s ee std::bind2nd(std::greater<int>(),"A"), wh i ch does
i ndeed contai n an i nteg er typ e (<int>) th at i s not com p ati ble wi th th e s tri ng typ e obj ects for
wh i ch we' re look i ng i n ou r ex am p le. R ep laci ng <int> wi th <std::string> m ak es th e
p roblem g o away.

T h ere i s no dou bt th at th e error m es s ag e cou ld be better s tru ctu red. T h e actu al p roblem cou ld
be om i tted before th e h i s tory of th e i ns tanti ati on, and i ns tead of u s i ng fu lly ex p anded
tem p late i ns tanti ati on nam es li k e MyTemplate<YourTemplate<int> >, decom p os i ng th e
i ns tance as i n MyTemplate<T> with T=YourTemplate<int> can redu ce th e ov erwh elm i ng
leng th of nam es . H owev er, i t i s als o tru e th at all th e i nform ati on i n th i s di ag nos ti c cou ld be
u s efu l i n s om e s i tu ati ons . I t i s th erefore not s u rp ri s i ng th at oth er com p i lers p rov i de s i m i lar
i nform ati on (alth ou g h s om e u s e th e s tru ctu ri ng tech ni q u es m enti oned).

6.6.2 Shallow Instantiation

D i ag nos ti cs s u ch as th os e di s cu s s ed earli er ari s e wh en errors are fou nd after a long ch ai n of

i ns tanti ati ons . T o i llu s trate th i s , cons i der th e followi ng s om ewh at contri v ed code:

template <typename T>

void clear (T const& p)
{
*p=0; // assumes T is a pointer-like type
}

template <typename T>

void core (T const& p)
{
clear(p);
}

template <typename T>

void middle (typename T::Index p)
{
core(p);
}

template <typename T>

void shell (T const& env)
{
typename T::Index i;
middle<T>(i);
}

class Client {
public:
typedef int Index;
};

Client main_client;
int main()
{
shell(main_client);
}

T h i s ex am p le i llu s trates th e typ i cal layeri ng of s oftware dev elop m ent: H i g h -lev el fu ncti on
tem p lates li k e shell() rely on com p onents li k e middle(), wh i ch th em s elv es m ak e u s e of
bas i c faci li ti es li k e core(). W h en we i ns tanti ate shell(), all th e layers below i t als o need to
be i ns tanti ated. I n th i s ex am p le, a p roblem i s rev ealed i n th e deep es t layer: core() i s
i ns tanti ated wi th typ e int (from th e u s e of Client::Index i n middle()) and attem p ts to
dereference a v alu e of th at typ e, wh i ch i s an error. A g ood g eneri c di ag nos ti c i nclu des a trace
of all th e layers th at led to th e p roblem s , bu t we obs erv e th at s o m u ch i nform ati on can ap p ear
u nwi eldy.

A n ex cellent di s cu s s i on of th e core i deas s u rrou ndi ng th i s p roblem can be fou nd i n

[S tr ou str u pD n E ] , i n wh i ch B j arne Strou s tru p i denti fi es two clas s es of ap p roach es to determ i ne
earli er wh eth er tem p late arg u m ents s ati s fy a s et of cons trai nts : th rou g h a lang u ag e ex tens i on
or th rou g h earli er p aram eter u s e. W e cov er th e form er op ti on to s om e ex tent i n Secti on 13 .11
on p ag e 218 . T h e latter alternati v e cons i s ts of forci ng any errors i n shallow i n stan ti ati on s. T h i s
i s ach i ev ed by i ns erti ng u nu s ed code wi th no oth er p u rp os e th an to tri g g er an error i f th at
code i s i ns tanti ated wi th tem p late arg u m ents th at do not m eet th e req u i rem ents of deep er
lev els of tem p lates .

I n ou r p rev i ou s ex am p le we cou ld add code i n shell() th at attem p ts to dereference a v alu e

of typ e T::Index. F or ex am p le:

template <typename T>

inline void ignore(T const&)
{
}

template <typename T>

void shell (T const& env)
{
class ShallowChecks {
void deref(T::Index ptr) {
ignore(*ptr);
}
};
typename T::Index i;
middle(i);
}

I f T i s a typ e s u ch th at T::Index cannot be dereferenced, an error i s now di ag nos ed on th e

local clas s ShallowChecks. N ote th at becau s e th e local clas s i s not actu ally u s ed, th e added
code does not i m p act th e ru nni ng ti m e of th e shell() fu ncti on. U nfortu nately, m any
com p i lers wi ll warn abou t th e fact th at ShallowChecks i s not u s ed (and nei th er are i ts
 m em bers ). T ri ck s s u ch as th e u s e of th e ignore() tem p late can be u s ed to i nh i bi t s u ch
warni ng s , bu t th ey add to th e com p lex i ty of th e code.

C learly, th e dev elop m ent of th e du m m y code i n ou r ex am p le can becom e as com p lex as th e

code th at i m p lem ents th e actu al fu ncti onali ty of th e tem p late. T o control th i s com p lex i ty i t i s
natu ral to attem p t to collect v ari ou s s ni p p ets of du m m y code i n s om e s ort of li brary. F or
ex am p le, s u ch a li brary cou ld contai n m acros th at ex p and to code th at tri g g ers th e ap p rop ri ate
error wh en a tem p late p aram eter s u bs ti tu ti on v i olates th e concep t u nderlyi ng th at p arti cu lar
p aram eter. T h e m os t p op u lar s u ch li brary i s th e Con c ept Chec k L i b r ar y , wh i ch i s p art of th e
B oos t di s tri bu ti on (s ee [B C C L ] ).

U nfortu nately, th e tech ni q u e i s n' t p arti cu larly p ortable (th e way errors are di ag nos ed di ffers
cons i derably from one com p i ler to anoth er) and s om eti m es m as k s i s s u es th at cannot be
cap tu red at a h i g h er lev el.

6.6.3 Long Symbols

T h e error m es s ag e analyz ed i n Secti on 6.6.1 on p ag e 7 5 dem ons trates anoth er p roblem of

tem p lates : I ns tanti ated tem p late code can res u lt i n v ery long s ym bols . F or ex am p le, i n th e
i m p lem entati on u s ed earli er std::string i s ex p anded to

_STL::basic_string<char,_STL::char_traits<char>,
_STL::allocator<char> >

Som e p rog ram s th at u s e th e C + + s tandard li brary p rodu ce s ym bols th at contai n m ore th an

10, 000 ch aracters . T h es e v ery long s ym bols can als o cau s e errors or warni ng s i n com p i lers ,
li nk ers , and debu g g ers . M odern com p i lers u s e com p res s i on tech ni q u es to redu ce th i s p roblem ,
bu t i n error m es s ag es th i s i s not ap p arent.

6.6.4 Tracers

So far we h av e di s cu s s ed bu g s th at ari s e wh en com p i li ng or li nk i ng p rog ram s th at contai n

tem p lates . H owev er, th e m os t ch alleng i ng tas k of ens u ri ng th at a p rog ram beh av es correctly
at ru n ti m e often f ollow s a s u cces s fu l bu i ld. T em p lates can s om eti m es m ak e th i s tas k a li ttle
m ore di ffi cu lt becau s e th e beh av i or of g eneri c code rep res ented by a tem p late dep ends
u ni q u ely on th e cli ent of th at tem p late (certai nly m u ch m ore s o th an ordi nary clas s es and
fu ncti ons ). A tracer i s a s oftware dev i ce th at can allev i ate th at as p ect of debu g g i ng by
detecti ng p roblem s i n tem p late defi ni ti ons early i n th e dev elop m ent cycle.

A tracer i s a u s er-defi ned clas s th at can be u s ed as an arg u m ent for a tem p late to be tes ted.
O ften, i t i s wri tten j u s t to m eet th e req u i rem ents of th e tem p late and no m ore th an th os e
req u i rem ents . M ore i m p ortant, h owev er, a tracer s h ou ld g enerate a tr ac e of th e op erati ons
th at are i nv ok ed on i t. T h i s allows , for ex am p le, to v eri fy ex p eri m entally th e effi ci ency of
alg ori th m s as well as th e s eq u ence of op erati ons .
H ere i s an ex am p le of a tracer th at m i g h t be u s ed to tes t a s orti ng alg ori th m :

// basics/tracer.hpp

#include <iostream>

class SortTracer {
private:
int value; // integer value to be sorted
int generation; // generation of this tracer
static long n_created; // number of constructor calls
static long n_destroyed; // number of destructor calls
static long n_assigned; // number of assignments
static long n_compared; // number of comparisons
static long n_max_live; // maximum of existing objects

// recompute maximum of existing objects

static void update_max_live() {
if (n_created-n_destroyed > n_max_live) {
n_max_live = n_created-n_destroyed;
}
}

public:
static long creations() {
return n_created;
}
static long destructions() {
return n_destroyed;
}
static long assignments() {
return n_assigned;
}
static long comparisons() {
return n_compared;
}
static long max_live() {
return n_max_live;
}

public:
// constructor
SortTracer (intv=0):value(v), generation(1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", created generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}

// copy constructor
SortTracer (SortTracer const& b)
: value(b.value), generation(b.generation+1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", copied as generation " << generation
<< " (total: " << n_created - n_destroyed
 << ")\n";
}

// destructor
~SortTracer() {
++n_destroyed;
update_max_live();
std::cerr << "SortTracer generation " << generation
<< " destroyed (total: "
<< n_created - n_destroyed << ")\n";
}

// assignment
SortTracer& operator= (SortTracer const& b) {
++n_assigned;
std::cerr << "SortTracer assignment #" << n_assigned
<< " (generation " << generation
<< " = " << b.generation
<< ")\n";
value = b.value;
return *this;
}

// comparison
friend bool operator < (SortTracer const& a,
SortTracer const& b) {
++n_compared;
std::cerr << "SortTracer comparison #" << n_compared
<< " (generation " << a.generation
<< " < " << b.generation
<< ")\n";
return a.value < b.value;
}

int val() const {

return value;
}
};

I n addi ti on to th e v alu e to s ort, value, th e tracer p rov i des s ev eral m em bers to trace an actu al
s ort: generation traces for each obj ect h ow m any cop i es i t i s from th e ori g i nal. T h e oth er
s tati c m em bers trace th e nu m ber of creati ons (cons tru ctor calls ), des tru cti ons , as s i g nm ent
com p ari s ons , and th e m ax i m u m nu m ber of obj ects th at ev er ex i s ted.

T h e s tati c m em bers are defi ned i n a s ep arate dot-C fi le:

// basics/tracer.cpp

#include "tracer.hpp"

long SortTracer::n_created = 0;
long SortTracer::n_destroyed = 0;
long SortTracer::n_max_live = 0;
long SortTracer::n_assigned = 0;
long SortTracer::n_compared = 0;
T h i s p arti cu lar tracer allows u s to track th e p attern or enti ty creati on and des tru cti on as well
as as s i g nm ents and com p ari s ons p erform ed by a g i v en tem p late. T h e followi ng tes t p rog ram
i llu s trates th i s for th e std::sort alg ori th m of th e C + + s tandard li brary:

// basics/tracertest.cpp

#include <iostream>
#include <algorithm>
#include "tracer.hpp"

int main()
{
// prepare sample input:
SortTracer input[]={7,3,5,6,4,2,0,1,9,8};

// print initial values:

for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ' ';
}
std::cerr << std::endl;

// remember initial conditions:

long created_at_start = SortTracer::creations();
long max_live_at_start = SortTracer::max_live();
long assigned_at_start = SortTracer::assignments();
long compared_at_start = SortTracer::comparisons();

// execute algorithm:
std::cerr << "---[ Start std::sort() ]--------------------\n";
std::sort<>(&input[0], &input[9]+1);
std::cerr << "---[ End std::sort() ]----------------------\n";

// verify result:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ' ';
}
std::cerr << "\n\n";

// final report:
std::cerr << "std::sort() of 10 SortTracer's"
<< " was performed by:\n "
<< SortTracer::creations() - created_at_start
<< " temporary tracers\n "
<< "up to "
<< SortTracer::max_live()
<< " tracers at the same time ("
<< max_live_at_start << " before)\n "
<< SortTracer::assignments() - assigned_at_start
<< " assignments\n "
<< SortTracer::comparisons() - compared_at_start
<< " comparisons\n\n";
}

R u nni ng th i s p rog ram creates a cons i derable am ou nt of ou tp u t, bu t m u ch can be conclu ded

from th e " fi nal rep ort." F or one i m p lem entati on of th e std::sort() fu ncti on, we fi nd th e
followi ng :

std::sort() of 10 SortTracer's was performed by:

15 temporary tracers
up to 12 tracers at the same time (10 before)
33 assignments
27 comparisons

F or ex am p le, we s ee th at alth ou g h 15 tem p orary tracers were created i n ou r p rog ram wh i le

s orti ng , at m os t two addi ti onal tracers ex i s ted at any one ti m e.

O u r tracer th u s fu lfi lls two roles : I t p rov es th at th e s tandard sort() alg ori th m req u i res no
m ore fu ncti onali ty th an ou r tracer (for ex am p le, op erators == and > were not needed), and i t
g i v es u s a s ens e of th e cos t of th e alg ori th m . I t does not, h owev er, rev eal m u ch abou t th e
correctnes s of th e s orti ng tem p late.

6.6.5 Oracles

T racers are relati v ely s i m p le and effecti v e, bu t th ey allow u s to trace th e ex ecu ti on of

tem p lates only for s p eci fi c i np u t data and for a s p eci fi c beh av i or of i ts related fu ncti onali ty. W e
m ay wonder, for ex am p le, wh at condi ti ons m u s t be m et by th e com p ari s on op erator for th e
s orti ng alg ori th m to be m eani ng fu l (or correct), bu t i n ou r ex am p le we h av e only tes ted a
com p ari s on op erator th at beh av es ex actly li k e les s -th an for i nteg ers .

A n ex tens i on of tracers i s k nown i n s om e ci rcles as or ac les (or r u n -ti me an aly si s or ac les).

T h ey are tracers th at are connected to a s o-called i n f er en c e en g i n e—a p rog ram th at can
rem em ber as s erti ons and reas ons abou t th em to i nfer certai n conclu s i ons . O ne s u ch s ys tem
th at was ap p li ed to certai n p arts of a s tandard li brary i m p lem entati on i s called M E L AS and i s
di s cu s s ed i n [M u sser W an g D y n aV er i ] . [6 ]

[6 ]
O ne au th or, D av i d M u s s er, was als o a k ey fi g u re i n th e dev elop m ent of th e
C + + s tandard li brary. A m ong oth er th i ng s , h e des i g ned and i m p lem ented th e
fi rs t as s oci ati v e contai ners .

O racles allow u s , i n s om e cas es , to v eri fy tem p late alg ori th m s dynam i cally wi th ou t fu lly
s p eci fyi ng th e s u bs ti tu ti ng tem p late arg u m ents (th e oracles are th e arg u m ents ) or th e i np u t
data (th e i nference eng i ne m ay req u es t s om e s ort of i np u t as s u m p ti on wh en i t g ets s tu ck ).
H owev er, th e com p lex i ty of th e alg ori th m s th at can be analyz ed i n th i s way i s s ti ll m odes t
(becau s e of th e li m i tati ons of th e i nference eng i nes ), and th e am ou nt of work i s cons i derable.
F or th es e reas ons , we do not delv e i nto th e dev elop m ent of oracles , bu t th e i nteres ted reader
s h ou ld ex am i ne th e p u bli cati on m enti oned earli er (and th e references contai ned th erei n).

6.6.6 Archetypes

W e m enti oned earli er th at tracers often p rov i de an i nterface th at i s th e m i ni m al req u i rem ent
of th e tem p late th ey trace. W h en s u ch a m i ni m al tracer does not g enerate ru n-ti m e ou tp u t, i t
i s s om eti m es called an ar c hety pe. A n arch etyp e allows u s to v eri fy th at a tem p late
i m p lem entati on does not req u i re m ore s yntacti c cons trai nts th an i ntended. T yp i cally, a
tem p late i m p lem enter wi ll want to dev elop an arch etyp e for ev ery concep t i denti fi ed i n th e
tem p late li brary.
 6.7 Afternotes

T h e org ani z ati on of s ou rce code i n h eader fi les and dot-C fi les i s a p racti cal
cons eq u ence of v ari ou s i ncarnati ons of th e s o-called on e-d ef i n i ti on r u le or O D R .
A n ex tens i v e di s cu s s i on of th i s ru le i s p res ented i n A p p endi x A .

T h e i nclu s i on v ers u s s ep arati on m odel debate h as been a controv ers i al one. T h e

i nclu s i on m odel i s a p rag m ati c ans wer di ctated larg ely by ex i s ti ng p racti ce i n C + +
com p i ler i m p lem entati ons . H owev er, th e fi rs t C + + i m p lem entati on was di fferent:
T h e i nclu s i on of tem p late defi ni ti ons was i m p li ci t, wh i ch created a certai n i llu s i on
of separ ati on (s ee C h ap ter 10 for detai ls on th i s ori g i nal m odel).

[Strou s tru p D nE ] contai ns a g ood p res entati on of Strou s tru p ' s v i s i on for tem p late
code org ani z ati on and th e as s oci ated i m p lem entati on ch alleng es . I t clearly was n' t
th e i nclu s i on m odel. Y et, at s om e p oi nt i n th e s tandardi z ati on p roces s , i t s eem ed
as i f th e i nclu s i on m odel was th e only v i able ap p roach after all. A fter s om e
i ntens e debates , h owev er, th os e env i s i oni ng a m ore decou p led m odel g arnered
s u ffi ci ent s u p p ort for wh at ev entu ally becam e th e s ep arati on m odel. U nli k e th e
i nclu s i on m odel, th i s was a th eoreti cal m odel not bas ed on any ex i s ti ng
i m p lem entati on. I t took m ore th an fi v e years to s ee i ts fi rs t i m p lem entati on
p u bli s h ed (M ay 2002).

I t i s s om eti m es tem p ti ng to i m ag i ne ways of ex tendi ng th e concep t of

p recom p i led h eaders s o th at m ore th an one h eader cou ld be loaded for a s i ng le
com p i lati on. T h i s wou ld i n p ri nci p le allow for a fi ner g rai ned ap p roach to
p recom p i lati on. T h e obs tacle h ere i s m ai nly th e p rep roces s or: M acros i n one
h eader fi le can enti rely ch ang e th e m eani ng of s u bs eq u ent h eader fi les . H owev er,
once a fi le h as been p recom p i led, m acro p roces s i ng i s com p leted, and i t i s h ardly
p racti cal to attem p t to p atch a p recom p i led h eader for th e p rep roces s or effects
i ndu ced by oth er h eaders .

A fai rly s ys tem ati c attem p t to i m p rov e C + + com p i ler di ag nos ti cs by addi ng
du m m y code i n h i g h -lev el tem p lates can be fou nd i n J erem y Si ek ' s Con c ept
Chec k L i b r ar y (s ee [B C C L ] ). I t i s p art of th e B oos t li brary (s ee [B oos t] ).
6.8 Summary

• T em p lates ch alleng e th e clas s i c com p i ler-p lu s -li nk er m odel. T h erefore

th ere are di fferent ap p roach es to org ani z e tem p late code: th e i nclu s i on
m odel, ex p li ci t i ns tanti ati on, and th e s ep arati on m odel.
• U s u ally, you s h ou ld u s e th e i nclu s i on m odel (th at i s , p u t all tem p late code
i n h eader fi les ).
• B y s ep arati ng tem p late code i nto di fferent h eader fi les for declarati ons and
defi ni ti ons , you can m ore eas i ly s wi tch between th e i nclu s i on m odel and
ex p li ci t i ns tanti ati on.
• T h eC + + s tandard defi nes a s ep arate com p i lati on m odel for tem p lates
(u s i ng th e k eyword export). I t i s not yet wi dely av ai lable, h owev er.
• D ebu g g i ng code wi th tem p lates can be ch alleng i ng .
• T em p late i ns tances m ay h av e v ery long nam es .
• T o tak e adv antag e of p recom p i led h eaders , be s u re to k eep th e s am e
order for #include di recti v es .
Chapter 7. Basic Template Terminology

So far we h av e i ntrodu ced th e bas i c concep t of tem p lates i n C + + . B efore we g o

i nto detai ls , let' s look at th e term s of th e concep ts we u s e. T h i s i s neces s ary
becau s e, i ns i de th e C + + com m u ni ty (and ev en i n th e s tandard), th ere i s a lack of
p reci s i on reg ardi ng concep ts and term i nolog y.
7.1 "Class Template" or "Template Class"?

I n C + + , s tru cts , clas s es , and u ni ons are collecti v ely called c lass ty pes. W i th ou t
addi ti onal q u ali fi cati on, th e word " clas s " i n p lai n tex t typ e i s m eant to i nclu de
clas s typ es i ntrodu ced wi th ei th er th e k eyword class or th e k eyword struct. [1]

N ote s p eci fi cally th at " clas s typ e" i nclu des u ni ons , bu t " clas s " does not.

[1]
I n C + + , th e only di fference between class and struct i s th at
th e defau lt acces s for class i s private wh ereas th e defau lt
acces s for struct i s public. H owev er, we p refer to u s e class for
typ es th at u s e new C + + featu res , and we u s e struct for ordi nary
C data s tru ctu re th at can be u s ed as " p lai n old data" (P O D ).

T h ere i s s om e confu s i on abou t h ow a clas s th at i s a tem p late i s called:

• T h e term c lass template s tates th at th e clas s i s a tem p late. T h at i s , i t i s a

p aram eteri z ed des cri p ti on of a fam i ly of clas s es .
• T h e term template c lass on th e oth er h and h as been u s ed

- as a s ynonym for clas s tem p late.

- to refer to clas s es g enerated from tem p lates .

- to refer to clas s es wi th a nam e th at i s a tem p late-i d.

T h e di fference between th e s econd and th i rd m eani ng i s s om ewh at s u btle and

u ni m p ortant for th e rem ai nder of th e tex t.

B ecau s e of th i s i m p reci s i on, we av oi d th e term template c lass i n th i s book .

Si m i larly, we u s e f u n c ti on template and memb er f u n c ti on template, bu t av oi d

template f u n c ti on and template memb er f u n c ti on .
7.2 Instantiation and Specialization

T h e p roces s of creati ng a reg u lar clas s , fu ncti on, or m em ber fu ncti on from a
tem p late by s u bs ti tu ti ng actu al v alu es for i ts arg u m ents i s called template
i n stan ti ati on . T h i s res u lti ng enti ty (clas s , fu ncti on, or m em ber fu ncti on) i s
g eneri cally called a spec i ali z ati on .

H owev er, i n C + + th e i ns tanti ati on p roces s i s not th e only way to p rodu ce a

s p eci ali z ati on. A lternati v e m ech ani s m s allow th e p rog ram m er to s p eci fy ex p li ci tly
a declarati on th at i s ti ed to a s p eci al s u bs ti tu ti on of tem p late p aram eters . A s we
i ntrodu ced i n Secti on 3 .3 on p ag e 27 , s u ch a s p eci ali z ati on i s i ntrodu ced by
template<>:

template <typename T1, typename T2> // primary class template

class MyClass {
…
};

template<> // explicit specialization

class MyClass<std::string,float> {
…
};

Stri ctly s p eak i ng , th i s i s called a s o-called ex pli c i t spec i ali z ati on (as op p os ed to an
i n stan ti ated or g en er ated spec i ali z ati on ).

A s i ntrodu ced i n Secti on 3 .4 on p ag e 29 , s p eci ali z ati ons th at s ti ll h av e tem p late

p aram eters are called par ti al spec i ali z ati on s:

template <typename T> // partial specialization

class MyClass<T,T> {
…
};

template <typename T> // partial specialization

class MyClass<bool,T> {
…
};

W h en talk i ng abou t (ex p li ci t or p arti al) s p eci ali z ati ons , th e g eneral tem p late i s
als o called th e pr i mar y template.
 7.3 Declarations versus Definitions

So far, th e words d ec lar ati on and d ef i n i ti on h av e been u s ed only a few ti m es i n

th i s book . H owev er, th es e words carry wi th th em a rath er p reci s e m eani ng i n
s tandard C + + , and th at i s th e m eani ng th at we u s e.

A d ec lar ati on i s a C + + cons tru ct th at i ntrodu ces or rei ntrodu ces a nam e i nto a
C + + s cop e. T h i s i ntrodu cti on always i nclu des a p arti al clas s i fi cati on of th at nam e,
bu t th e detai ls are not req u i red to m ak e a v ali d declarati on. F or ex am p le:

class C; // a declaration of C as a class

void f(int p); // a declaration of f() as a function and p as a
named parameter
extern int v; // a declaration of v as a variable

N ote th at ev en th ou g h th ey h av e a " nam e, " m acro defi ni ti ons and goto labels are
not cons i dered declarati ons i n C + + .

D eclarati ons becom e d ef i n i ti on s wh en th e detai ls of th ei r s tru ctu re are m ade

k nown or, i n th e cas e of v ari ables , wh en s torag e s p ace m u s t be allocated. F or
clas s typ e and fu ncti on defi ni ti ons , th i s m eans a brace-enclos ed body m u s t be
p rov i ded. F or v ari ables , i ni ti ali z ati ons and a m i s s i ng extern lead to defi ni ti ons .
H ere are ex am p les th at com p lem ent th e p recedi ng nondefi ni ti on declarati ons :

class C {}; // definition (and declaration) of class C

void f(int p) { // definition (and declaration) of function f()

std::cout << p << std::endl;
}

extern int v = 1; // an initializer makes this a definition for v

int w; // global variable declarations not preceded by

// extern are also definitions

B y ex tens i on, th e declarati on of a clas s tem p late or fu ncti on tem p late i s called a
defi ni ti on i f i t h as a body. H ence,

template <typename T>

void func (T);

i s a declarati on th at i s not a defi ni ti on, wh ereas

template <typename T>

class S {};

i s i n fact a defi ni ti on.

7.4 The One-Definition Rule

T h eC + + lang u ag e defi ni ti on p laces s om e cons trai nts on th e redeclarati on of

v ari ou s enti ti es . T h e totali ty of th es e cons trai nts i s k nown as th e on e-d ef i n i ti on
r u le or O D R . T h e detai ls of th i s ru le are q u i te com p lex and s p an a larg e v ari ety of
s i tu ati ons . L ater ch ap ters i llu s trate th e v ari ou s res u lti ng facets i n each ap p li cable
contex t, and you can fi nd a com p lete des cri p ti on of th e O D R i n A p p endi x A . F or
now, i t s u ffi ces to rem em ber th e followi ng O D R bas i cs :

• N oni nli ne fu ncti ons and m em ber fu ncti ons , as well as g lobal v ari ables and
s tati c data m em bers s h ou ld be defi ned only once acros s th e wh ole
pr og r am.
• C las s typ es (i nclu di ng s tru cts and u ni ons ) and i nli ne fu ncti ons s h ou ld be
defi ned at m os t once p er tr an slati on u n i t, and all th es e defi ni ti ons s h ou ld
be i denti cal.

A tr an slati on u n i t i s wh at res u lts from p rep roces s i ng a s ou rce fi le; th at i s , i t

i nclu des th e contents nam ed by #include di recti v es .

I n th e rem ai nder of th i s book , li n k ab le en ti ty m eans one of th e followi ng : a

noni nli ne fu ncti on or m em ber fu ncti on, a g lobal v ari able or a s tati c data m em ber,
i nclu di ng any s u ch th i ng s g enerated from a tem p late.
7.5 Template Arguments versus Template Parameters

C om p are th e followi ng clas s tem p late

template <typename T, int N>

class ArrayInClass {
public:
T array[N];
};

wi th a s i m i lar p lai n clas s :

class DoubleArrayInClass {
public:
double array[10];
};

T h e latter becom es es s enti ally eq u i v alent to th e form er i f we rep lace th e

p aram eters T and N by double and 10 res p ecti v ely. I n C + + , th e nam e of th i s
rep lacem ent i s denoted as

ArrayInClass<double,10>

N ote h ow th e nam e of th e tem p late i s followed by s o-called template ar g u men ts

i n ang le brack ets .

R eg ardles s of wh eth er th es e arg u m ents are th em s elv es dep endent on tem p late
p aram eters , th e com bi nati on of th e tem p late nam e, followed by th e arg u m ents i n
ang le brack ets , i s called a template-i d .

T h i s nam e can be u s ed m u ch li k e a corres p ondi ng nontem p late enti ty wou ld be

u s ed. F or ex am p le:

int main()
{
ArrayInClass<double,10> ad;
ad.array[0] = 1.0;
}

I t i s es s enti al to di s ti ng u i s h between template par ameter s and template

ar g u men ts. I n s h ort, you can s ay th at you " p as s ar g u men ts to becom e
par ameter s." [2 ]
O r m ore p reci cely:

[2 ]
I n th e academ i c world, ar g u men ts are s om eti m es called ac tu al
 par ameter s wh ereas par ameter s are called f or mal par ameter s.

• Template par ameter s are th os e nam es th at are li s ted after th e k eyword

template i n th e tem p late declarati on or defi ni ti on (T and N i n ou r
ex am p le).
• Template ar g u men ts are th e i tem s th at are s u bs ti tu ted for tem p late
p aram eters (double and 10 i n ou r ex am p le). U nli k e tem p late p aram eters ,
tem p late arg u m ents can be m ore th an j u s t " nam es ."

T h e s u bs ti tu ti on of tem p late p aram eters by tem p late arg u m ents i s ex p li ci t wh en

i ndi cated wi th a tem p late-i d, bu t th ere are v ari ou s s i tu ati ons wh en th e
s u bs ti tu ti on i s i m p li ci t (for ex am p le, i f tem p late p aram eters are s u bs ti tu ted by
th ei r defau lt arg u m ents ).

A fu ndam ental p ri nci p le i s th at any tem p late arg u m ent m u s t be a q u anti ty or

v alu e th at can be determ i ned at com p i le ti m e. A s becom es clear later, th i s
req u i rem ent trans lates i nto dram ati c benefi ts for th e ru n-ti m e cos ts of tem p late
enti ti es . B ecau s e tem p late p aram eters are ev entu ally s u bs ti tu ted by com p i le-ti m e
v alu es , th ey can th em s elv es be u s ed to form com p i le-ti m e ex p res s i ons . T h i s was
ex p loi ted i n th e ArrayInClass tem p late to s i z e th e m em ber array array. T h e
s i z e of an array m u s t be a s o-called c on stan t-ex pr essi on , and th e tem p late
p aram eter N q u ali fi es as s u ch .

W e can p u s h th i s reas oni ng a li ttle fu rth er: B ecau s e tem p late p aram eters are
com p i le-ti m e enti ti es , th ey can als o be u s ed to create v ali d tem p late arg u m ents .
H ere i s an ex am p le:

template <typename T>

class Dozen {
public:
ArrayInClass<T,12> contents;
};

N ote h ow i n th i s ex am p le th e nam e T i s both a tem p late p aram eter and a

tem p late arg u m ent. T h u s , a m ech ani s m i s av ai lable to enable th e cons tru cti on of
m ore com p lex tem p lates from s i m p ler ones . O f cou rs e, th i s i s not fu ndam entally
di fferent from th e m ech ani s m s th at allow u s to as s em ble typ es and fu ncti ons .
Part II: Templates in Depth

T h e fi rs t p art of th i s book p rov i ded a tu tori al for m os t of th e

lang u ag e concep ts u nderlyi ng C + + tem p lates . T h at p res entati on i s
s u ffi ci ent to ans wer th e m aj ori ty of q u es ti ons th at m ay ari s e i n
ev eryday C + + p rog ram m i ng . T h e s econd p art of th i s book p rov i des
a reference th at ans wers ev en th e m ore u nu s u al q u es ti ons th at
ari s e wh en p u s h i ng th e env elop e of th e lang u ag e to ach i ev e s om e
adv anced s oftware effect. I f des i red, you can s k i p th i s p art on a
fi rs t read and retu rn to s p eci fi c top i cs as p rom p ted by references i n
later ch ap ters or after look i ng u p a concep t i n th e i ndex .

O u r g oal i s to be clear and com p lete, bu t als o to k eep th e

di s cu s s i on conci s e. T o th i s end, ou r ex am p les are s h ort and often
s om ewh at arti fi ci al. T h i s als o ens u res th at we don' t s tray from th e
top i c at h and to u nrelated i s s u es .

I n addi ti on, we look at p os s i ble fu tu re ch ang es and ex tens i ons for

th e tem p lates lang u ag e featu re i n C + + . T op i cs i nclu de:

• F u ndam ental tem p late declarati on i s s u es

• T h e m eani ng of nam es i n tem p lates
• T h eC + + tem p late i ns tanti ati on m ech ani s m s
• T h e tem p late arg u m ent dedu cti on ru les
• Sp eci ali z ati on and ov erloadi ng
• F u tu re p os s i bi li ti es
Chapter 8. Fundamentals in Depth

I n th i s ch ap ter we rev i ew s om e of th e fu ndam entals i ntrodu ced i n th e fi rs t p art of

th i s book i n d epth: th e declarati on of tem p lates , th e res tri cti ons on tem p late
p aram eters , th e cons trai nts on tem p late arg u m ents , and s o forth .
8.1 Parameterized Declarations

C + + cu rrently s u p p orts two fu ndam ental k i nds of tem p lates : clas s tem p lates and
fu ncti on tem p lates (s ee Secti on 13 .6 on p ag e 212 for a p os s i ble fu tu re ch ang e i n
th i s area). T h i s clas s i fi cati on i nclu des m em ber tem p lates . Su ch tem p lates are
declared m u ch li k e ordi nary clas s es and fu ncti ons , ex cep t for bei ng i ntrodu ced by
a par ameter i z ati on c lau se of th e form

template<… parameters here… >

or p erh ap s

export template<… parameters here… >

(s ee Secti on 6.3 on p ag e 68 and Secti on 10.3 .3 on p ag e 14 9 for a detai led

ex p lanati on of th e k eyword export).

W e' ll com e back to th e actu al tem p late p aram eter declarati ons i n a later s ecti on.
A n ex am p le i llu s trates th e two k i nds of tem p lates , both as clas s m em bers and as
ordi nary nam es p ace s cop e declarati ons :

template <typename T>

class List { // a namespace scope class template
public:
template <typename T2> // a member function template
List (List<T2> const&); // (constructor)
…
};
template <typename T>
template <typename T2>
List<T>::List (List<T2> const& b) // an out-of-class member function
{ // template definition
…
}

template <typename T>

int length (List<T> const&); // a namespace scope function
template

class Collection {
template <typename T> // an in-class member class
template
class Node { // definition
…
};

template <typename T> // another member class template,

class Handle; // without its definition
 template <typename T> // an in-class (and therefore
implicitly
T* alloc() { // inline) member function template
… // definition
}
…
};

template <typename T> // an out-of-class member class

class Collection::Node { // template definition
…
};

N ote h ow m em ber tem p lates defi ned ou ts i de th ei r enclos i ng clas s can h av e

m u lti p le template<…> p aram eteri z ati on clau s es : one for th e tem p late i ts elf and
one for ev ery enclos i ng clas s tem p late. T h e clau s es are li s ted s tarti ng from th e
ou term os t clas s tem p late.

U n i on templates are p os s i ble too (and th ey are cons i dered a k i nd of clas s

tem p late):

template <typename T>

union AllocChunk {
T object;
unsigned char bytes[sizeof(T)];
};

F u ncti on tem p lates can h av e defau lt call arg u m ents j u s t li k e ordi nary fu ncti on
declarati ons :

template <typename T>

void report_top (Stack<T> const&, int number = 10);

template <typename T>

void fill (Array<T>*, T const& = T()); // T() is zero for built-in
types

T h e latter declarati on s h ows th at a defau lt call arg u m ent cou ld dep end on a
tem p late p aram eter. W h en th e fill() fu ncti on i s called, th e defau lt arg u m ent i s
not i ns tanti ated i f a s econd fu ncti on call arg u m ent i s s u p p li ed. T h i s ens u res th at
no error i s i s s u ed i f th e defau lt call arg u m ent cannot be i ns tanti ated for a
p arti cu lar T. F or ex am p le:

class Value {
public:
Value(int); // no default constructor
};

void init (Array<Value>* array)

{
 Value zero(0);

fill(array, zero); // OK: = T() is not used

fill(array); // ERROR: = T() is used, but not valid for T
= Value
}

I n addi ti on to th e two fu ndam ental k i nds of tem p lates , th ree oth er k i nds of
declarati ons can be p aram eteri z ed u s i ng a s i m i lar notati on. A ll th ree corres p ond
to defi ni ti ons of m em bers of clas s tem p lates [1]
:

T h ey are m u ch li k e ordi nary clas s m em bers , bu t th ey are

[1]

occas i onally (erroneou s ly) referred to as memb er templates.

1. D e fin itio n s o f m e m b e r f u n c t io n s o f c la s s t e m p la t e s
2 . D e f in it io n s o f n e s t e d c la s s m e m b e r s o f c la s s t e m p la t e s
3 . D e fin itio n s o f s t a t ic d a t a m e m b e r s o f c la s s t e m p la t e s

A lth ou g h th ey can be p aram eteri z ed, s u ch defi ni ti ons aren' t q u i te fi rs t-clas s

tem p lates . T h ei r p aram eters are enti rely determ i ned by th e tem p late of wh i ch
th ey are m em bers . H ere i s an ex am p le of s u ch defi ni ti ons :

template <int I>

class CupBoard {
void open();
class Shelf;
static double total_weight;
…
};

template <int I>

void CupBoard<I>::open()
{
…
}

template <int I>

class CupBoard<I>::Shelf {
…
};

template <int I>

double CupBoard<I>::total_weight = 0.0;

A lth ou g h s u ch p aram eteri z ed defi ni ti ons are com m only called templates, th ere
are contex ts wh en th e term does n' t q u i te ap p ly to th em .

8.1.1 Virtual Member Functions

M em ber fu ncti on tem p lates cannot be declared v i rtu al. T h i s cons trai nt i s i m p os ed
becau s e th e u s u al i m p lem entati on of th e v i rtu al fu ncti on call m ech ani s m u s es a
fi x ed-s i z e table wi th one entry p er v i rtu al fu ncti on. H owev er, th e nu m ber of
i ns tanti ati ons of a m em ber fu ncti on tem p late i s not fi x ed u nti l th e enti re p rog ram
h as been trans lated. H ence, s u p p orti ng v i rtu al m em ber fu ncti on tem p lates wou ld
req u i re s u p p ort for a wh ole new k i nd of m ech ani s m inC + + com p i lers and li nk ers .

I n contras t, th e ordi nary m em bers of clas s tem p lates can be v i rtu al becau s e th ei r
nu m ber i s fi x ed wh en a clas s i s i ns tanti ated:

template <typename T>

class Dynamic {
public:
virtual ~Dynamic(); // OK: one destructor per instance of
Dynamic<T>

template <typename T2>

virtual void copy (T2 const&);
// ERROR: unknown number of instances of
copy()
// given an instance of Dynamic<T>
};

8.1.2 Linkage of Templates

E v ery tem p late m u s t h av e a nam e and th at nam e m u s t be u ni q u e wi th i n i ts

s cop e, ex cep t th at fu ncti on tem p lates can be ov erloaded (s ee C h ap ter 12). N ote
es p eci ally th at, u nli k e clas s typ es , clas s tem p lates cannot s h are a nam e wi th a
di fferent k i nd of enti ty:

int C;

class C; // OK: class names and nonclass names are in a different

''space''

int X;

template <typename T>

class X; // ERROR: conflict with variable X

struct S;

template <typename T>

class S; // ERROR: conflict with struct S

T em p late nam es h av e li nk ag e, bu t th ey cannot h av e C li n k ag e. N ons tandard

li nk ag es m ay h av e an i m p lem entati on-dep endent m eani ng (h owev er, we don' t
k now of an i m p lem entati on th at s u p p orts nons tandard nam e li nk ag es for
tem p lates ):

extern "C++" template <typename T>

void normal();
// this is the default: the linkage specification could be left
out

extern "C" template <typename T>

void invalid();
// invalid: templates cannot have C linkage

extern "Xroma" template <typename T>

void xroma_link();
// nonstandard, but maybe some compiler will some day
// support linkage compatible with the Xroma language

T em p lates u s u ally h av e ex ternal li nk ag e. T h e only ex cep ti ons are nam es p ace

s cop e fu ncti on tem p lates wi th th e static s p eci fi er:

template <typename T>

void external(); // refers to the same entity as a
declaration of
// the same name (and scope) in another file
template <typename T>
static void internal(); // unrelated to a template with the same
name in
// another file

N ote th at tem p lates cannot be declared i n a fu ncti on.

8.1.3 Primary Templates

N orm al declarati ons of tem p lates declare s o-called pr i mar y templates. Su ch

tem p late declarati ons are declared wi th ou t addi ng tem p late arg u m ents i n ang le
brack ets after th e tem p late nam e:

template<typename T> class Box; // OK: primary template

template<typename T> class Box<T>; // ERROR

template<typename T> void translate(T*); // OK: primary template

template<typename T> void translate<T>(T*); // ERROR

N onp ri m ary clas s tem p lates occu r wh en declari ng s o-called par ti al spec i ali z ati on s
wh i ch are di s cu s s ed i n C h ap ter 12. F u ncti on tem p lates m u s t always be p ri m ary
tem p lates (bu t s ee Secti on 13 .7 on p ag e 213 for a p otenti al fu tu re lang u ag e
ch ang e).
8.2 Template Parameters

T h ere are th ree k i nds of tem p late p aram eters :

1. Ty p e p a r a m e t e r s ( t h e s e a r e b y f a r t h e m o s t c o m m o n )
2 . N o n t y p e p a r a m e t e r s
3 . Te m p l a t e t e m p l a t e p a r a m e t e r s

T em p late p aram eters are declared i n th e i ntrodu ctory p aram eteri z ati on clau s e of
a tem p late declarati on. Su ch declarati ons do not neces s ari ly need to be nam ed:

template <typename, int>

class X;

A p aram eter nam e i s , of cou rs e, req u i red i f th e p aram eter i s referred to later i n
th e tem p late. N ote als o th at a tem p late p aram eter nam e can be referred to i n a
s u bs eq u ent p aram eter declarati on (bu t not before):

template <typename T, // the first parameter is used in

the
T* Root, // declaration of the second one
and
template<T*> class Buf> // the third one
class Structure;

8.2.1 Type Parameters

T yp e p aram eters are i ntrodu ced wi th ei th er th e k eyword typename or th e

k eyword class: T h e two are enti rely eq u i v alent. [2 ]
T h e k eyword m u s t be
followed by a s i m p le i denti fi er and th at i denti fi er m u s t be followed by a com m a to
denote th e s tart of th e nex t p aram eter declarati on, a clos i ng ang le brack et (>) to
denote th e end of th e p aram eteri z ati on clau s e, or an eq u al s i g n (=) to denote th e
beg i nni ng of a defau lt tem p late arg u m ent.

[2 ]
T h e k eyword class does n ot i m p ly th at th e s u bs ti tu ti ng
arg u m ent s h ou ld be a clas s typ e. I t cou ld be alm os t any acces s i ble
typ e. H owev er, clas s typ es th at are defi ned i n a fu ncti on (loc al
c lasses) cannot be u s ed as tem p late arg u m ents (i ndep endent of
wh eth er th e p aram eter was declared wi th typename or class).

W i th i n a tem p late declarati on, a typ e p aram eter acts m u ch li k e a ty ped ef n ame.
F or ex am p le, i t i s not p os s i ble to u s e an elaborated nam e of th e form class T
wh en T i s a tem p late p aram eter, ev en i f T were to be s u bs ti tu ted by a clas s typ e:
template <typename Allocator>
class List {
class Allocator* allocator; // ERROR
friend class Allocator; // ERROR
…
};

I t i s p os s i ble th at a m ech ani s m to enable s u ch a fri end declarati on wi ll be added

i n th e fu tu re.

8.2.2 Nontype Parameters

N ontyp e tem p late p aram eters s tand for cons tant v alu es th at can be determ i ned
at com p i le or li nk ti m e. [3 ]
T h e typ e of s u ch a p aram eter (i n oth er words , th e typ e
of th e v alu e for wh i ch i t s tands ) m u s t be one of th e followi ng :

T em p late tem p late p aram eters do not denote typ es ei th er;

[3 ]

h owev er, th ey are not cons i dered wh en talk i ng abou t n on ty pe

p aram eters .

• A n i nteg er typ e or an enu m erati on typ e

• A p oi nter typ e (i nclu di ng reg u lar obj ect p oi nter typ es , fu ncti on p oi nter
typ es , and p oi nter-to-m em ber typ es )
• A reference typ e (both references to obj ects and references to fu ncti ons
are accep table)

A ll oth er typ es are cu rrently ex clu ded (alth ou g h floati ng -p oi nt typ es m ay be

added i n th e fu tu re, s ee Secti on 13 .4 on p ag e 210).

P erh ap s s u rp ri s i ng ly, th e declarati on of a nontyp e tem p late p aram eter can i n

s om e cas es als o s tart wi th th e k eyword typename:

template<typename T, // a type parameter

typename T::Allocator* Allocator> // a nontype parameter
class List;

T h e two cas es are eas i ly di s ti ng u i s h ed becau s e th e fi rs t i s followed by a s i m p le

i denti fi er, wh ereas th e s econd i s followed by a q u ali f i ed n ame (i n oth er words , a
nam e contai ni ng a dou ble colon, ::). Secti on 1.1 on p ag e 4 3 and Secti on 9 .3 .2
on p ag e 13 0 ex p lai n th e need for th e k eyword typename i n th e nontyp e
p aram eter.

F u ncti on and array typ es can be s p eci fi ed, bu t th ey are i m p li ci tly adj u s ted to th e
p oi nter typ e to wh i ch th ey decay:

template<int buf[5]> class Lexer; // buf is really an int*

template<int* buf> class Lexer; // OK: this is a
redeclaration
N ontyp e tem p late p aram eters are declared m u ch li k e v ari ables , bu t th ey cannot
h av e nontyp e s p eci fi ers li k e static, mutable, and s o forth . T h ey can h av e
const and volatile q u ali fi ers , bu t i f s u ch a q u ali fi er ap p ears at th e ou term os t
lev el of th e p aram eter typ e, i t i s s i m p ly i g nored:

template<int const length> class Buffer; // const is useless here

template<int length> class Buffer; // same as previous
declaration

F i nally, nontyp e p aram eters are always r v alu es: T h ei r addres s cannot be tak en,
and th ey cannot be as s i g ned to.

8.2.3 Template Template Parameters

T em p late tem p late p aram eters are p laceh olders for clas s tem p lates . T h ey are
declared m u ch li k e clas s tem p lates , bu t th e k eywords struct and union cannot
be u s ed:

template <template<typename X> class C> // OK

void f(C<int>* p);

template <template<typename X> struct C> // ERROR: struct not valid

here
void f(C<int>* p);

template <template<typename X> union C> // ERROR: union not valid

here
void f(C<int>* p);

I n th e s cop e of th ei r declarati on, tem p late tem p late p aram eters are u s ed j u s t li k e
oth er clas s tem p lates .

T h e p aram eters of tem p late tem p late p aram eters can h av e defau lt tem p late
arg u m ents . T h es e defau lt arg u m ents ap p ly wh en th e corres p ondi ng p aram eters
are not s p eci fi ed i n u s es of th e tem p late tem p late p aram eter:

template <template<typename T,
typename A = MyAllocator> class Container>
class Adaptation {
Container<int> storage; // implicitly equivalent to
// Container<T, MyAllocator>
…
};

T h e nam e of a tem p late p aram eter of a tem p late tem p late p aram eter can be u s ed
only i n th e declarati on of oth er p aram eters of th at tem p late tem p late p aram eter.
T h e followi ng contri v ed tem p late i llu s trates th i s concep t:

template <template<typename T, T*> class Buf>

class Lexer {
static char storage[5];
Buf<char, &Lexer<Buf>::storage> buf;
…
};

template <template<typename T> class List>

class Node {
static T* storage; // ERROR: a parameter of a template template
// parameter cannot be used here
…
};

U s u ally h owev er, th e nam es of th e tem p late p aram eters of a tem p late tem p late
p aram eter are not u s ed. A s a res u lt, th e form er p aram eters are often left
u nnam ed altog eth er. F or ex am p le, ou r earli er Adaptation tem p late cou ld be
declared as follows :

template <template <typename,

typename = MyAllocator> class Container>
class Adaptation
{
Container<int> storage; // implicitly equivalent to
// Container<int, MyAllocator>
…
};

8.2.4 Default Template Arguments

C u rrently, only clas s tem p late declarati ons can h av e defau lt tem p late arg u m ents
(s ee Secti on 13 .3 on p ag e 207 for li k ely ch ang es i n th i s area). A ny k i nd of
tem p late p aram eter can be eq u i p p ed wi th a defau lt arg u m ent, alth ou g h i t m u s t
m atch th e corres p ondi ng p aram eter. C learly, a defau lt arg u m ent s h ou ld not
dep end on i ts own p aram eter. H owev er, i t m ay dep end on p rev i ou s p aram eters :

template <typename T, typename Allocator = allocator<T> >

class List;

Si m i lar to defau lt fu ncti on call arg u m ents , a tem p late p aram eter can h av e a
defau lt tem p late arg u m ent only i f defau lt arg u m ents were als o s u p p li ed for th e
s u bs eq u ent p aram eters . T h e s u bs eq u ent defau lt v alu es are u s u ally p rov i ded i n
th e s am e tem p late declarati on, bu t th ey cou ld als o h av e been declared i n a
p rev i ou s declarati on of th at tem p late. T h e followi ng ex am p le m ak es th i s clear:

template <typename T1, typename T2, typename T3,

typename T4 = char, typename T5 = char>
class Quintuple; // OK

template <typename T1, typename T2, typename T3 = char,

typename T4, typename T5>
class Quintuple; // OK: T4 and T5 already have defaults

template <typename T1 = char, typename T2, typename T3,

typename T4, typename T5>
class Quintuple; // ERROR: T1 cannot have a default argument
// because T2 doesn't have a default

D efau lt tem p late arg u m ents cannot be rep eated:

template<typename T = void>
class Value;

template<typename T = void>
class Value; // ERROR: repeated default argument
8.3 Template Arguments

T em p late arg u m ents are th e " v alu es " th at are s u bs ti tu ted for tem p late
p aram eters wh en i ns tanti ati ng a tem p late. T h es e v alu es can be determ i ned u s i ng
s ev eral di fferent m ech ani s m s :

• E x p li ci t tem p late arg u m ents : A tem p late nam e can be followed by ex p li ci t

tem p late arg u m ent v alu es enclos ed i n ang le brack ets . T h e res u lti ng nam e
i s called a template-i d .
• I nj ected clas s nam e: W i th i n th e s cop e of a clas s tem p late X wi th tem p late
p aram eters P1, P2, … , th e nam e of th at tem p late (X) can be eq u i v alent to
th e tem p late-i d X<P1, P2, …>. See Secti on 9 .2.3 on p ag e 126 for
detai ls .
• D efau lt tem p late arg u m ents : E x p li ci t tem p late arg u m ents can be om i tted
from clas s tem p late i ns tances i f defau lt tem p late arg u m ents are av ai lable.
H owev er, ev en i f all tem p late p aram eters h av e a defau lt v alu e, th e
(p os s i bly em p ty) ang le brack ets m u s t be p rov i ded.
• A rg u m ent dedu cti on: F u ncti on tem p late arg u m ents th at are not ex p li ci tly
s p eci fi ed m ay be dedu ced from th e typ es of th e fu ncti on call arg u m ents i n
a call. T h i s i s des cri bed i n detai l i n C h ap ter 11. D edu cti on i s als o done i n a
few oth er s i tu ati ons . I f all th e tem p late arg u m ents can be dedu ced, no
ang le brack ets need to be s p eci fi ed after th e nam e of th e fu ncti on
tem p late.

8.3.1 Function Template Arguments

T em p late arg u m ents for a fu ncti on tem p late can be s p eci fi ed ex p li ci tly or dedu ced
from th e way th e tem p late i s u s ed. F or ex am p le:

// details/max.cpp

template <typename T>

inline T const& max (T const& a, T const& b)
{
return a<b?b:a;
}

int main()
{
max<double>(1.0, -3.0); // explicitly specify template argument
max(1.0, -3.0); // template argument is implicitly
deduced
// to be double
max<int>(1.0, 3.0); // the explicit <int> inhibits the
deduction;
// hence the result has type int
}

Som e tem p late arg u m ents can nev er be dedu ced (s ee C h ap ter 11). T h e
corres p ondi ng p aram eters are bes t p laced at th e beg i nni ng of th e li s t of tem p late
p aram eters s o th ey can be s p eci fi ed ex p li ci tly wh i le allowi ng th e oth er arg u m ents
to be dedu ced. F or ex am p le:

// details/implicit.cpp

template <typename DstT, typename SrcT>

inline DstT implicit_cast (SrcT const& x) // SrcT can be deduced,
{ // but DstT cannot
return x;
}

int main()
{
double value = implicit_cast<double>(-1);
}

I f we h ad rev ers ed th e order of th e tem p late p aram eters i n th i s ex am p le (i n oth er

words , i f we h ad wri tten template<typename SrcT, typename DstT>), a call
of implicit_cast wou ld h av e to s p eci fy both tem p late arg u m ents ex p li ci tly.

B ecau s e fu ncti on tem p lates can be ov erloaded, ex p li ci tly p rov i di ng all th e

arg u m ents for a fu ncti on tem p late m ay not be s u ffi ci ent to i denti fy a s i ng le
fu ncti on: I n s om e cas es , i t i denti fi es a set of fu ncti ons . T h e followi ng ex am p le
i llu s trates a cons eq u ence of th i s obs erv ati on:

template <typename Func, typename T>

void apply (Func func_ptr, T x)
{
func_ptr(x);
}

template <typename T> void single(T);

template <typename T> void multi(T);

template <typename T> void multi(T*);

int main()
{
apply(&single<int>, 3); // OK
apply(&multi<int>, 7); // ERROR: no single multi<int>
}

I n th i s ex am p le, th e fi rs t call to apply() work s becau s e th e typ e of th e

ex p res s i on &single<int> i s u nam bi g u ou s . A s a res u lt, th e tem p late arg u m ent
v alu e for th e Func p aram eter i s eas i ly dedu ced. I n th e s econd call, h owev er,
&multi<int> cou ld be one of two di fferent typ es and th erefore Func cannot be
dedu ced i n th i s cas e.

F u rth erm ore, i t i s p os s i ble th at ex p li ci tly s p eci fyi ng th e tem p late arg u m ents for a
fu ncti on tem p late res u lts i n an attem p t to cons tru ct an i nv ali d C + + typ e.
C ons i der th e followi ng ov erloaded fu ncti on tem p late (RT1 and RT2 are
u ns p eci fi ed typ es ):

template<typename T> RT1 test(typename T::X const*);

template<typename T> RT2 test(...);

T h e ex p res s i on test<int> m ak es no s ens e for th e fi rs t of th e two fu ncti on

tem p lates becau s e typ e int h as no m em ber typ e X. H owev er, th e s econd
tem p late h as no s u ch p roblem . T h erefore, th e ex p res s i on &test<int> i denti fi es
th e addres s of a s i ng le fu ncti on. T h e fact th at th e s u bs ti tu ti on of int i nto th e fi rs t
tem p late fai ls does not m ak e th e ex p res s i on i nv ali d.

T h i s " s u bs ti tu ti on-fai lu re-i s -not-an-error" (SF I N A E ) p ri nci p le i s clearly an

i m p ortant i ng redi ent to m ak e th e ov erloadi ng of fu ncti on tem p lates p racti cal.
H owev er, i t als o enables rem ark able com p i le-ti m e tech ni q u es . F or ex am p le,
as s u m i ng th at typ es RT1 and RT2 are defi ned as follows :

typedef char RT1;

typedef struct { char a[2]; } RT2;

W e can ch eck at c ompi le ti me (i n oth er words , as a s o-called c on stan t-

ex pr essi on ) wh eth er a g i v en typ e T h as a m em ber typ e X:

#define type_has_member_type_X(T) \
(sizeof(test<T>(0)) == 1)

T o u nders tand th e ex p res s i on i n th i s m acro, i t i s conv eni ent to analyz e from th e

ou ts i de to th e i ns i de. F i rs t, th e sizeof ex p res s i on wi ll eq u al one i f th e fi rs t test
tem p late (wh i ch retu rns a char of s i z e one) i s s elected. T h e oth er tem p late
retu rns a s tru ctu re wi th a s i z e th at i s at leas t two (becau s e i t contai ns an array of
s i z e two). I n oth er words , th i s i s a dev i ce to determ i ne as a cons tant-ex p res s i on
wh eth er th e fi rs t or s econd tem p late was s elected for th e call test<T>(0).
C learly, th e fi rs t tem p late cannot be s elected i f th e g i v en typ e T h as no m em ber
typ e X. H owev er, i f th e g i v en typ e has a m em ber typ e X, th en th e fi rs t tem p late
i s p referred becau s e ov erload res olu ti on (s ee A p p endi x B ) p refers th e conv ers i on
from z ero to a nu ll p oi nter cons tant ov er bi ndi ng an arg u m ent to an elli p s i s
p aram eter (elli p s i s p aram eters are th e weak es t k i nd of bi ndi ng from an ov erload
res olu ti on p ers p ecti v e). Si m i lar tech ni q u es are ex p lored i n C h ap ter 15 .
T h e SF I N A E p ri nci p le p rotects only ag ai ns t attem p ts to create i nv ali d typ es bu t
not ag ai ns t attem p ts to ev alu ate i nv ali d ex p res s i ons . T h e followi ng ex am p le i s
th erefore i nv ali d C + + :

template<int I> void f(int (&)[24/(4-I)]);

template<int I> void f(int (&)[24/(4+I)]);

int main()
{
&f<4>; // ERROR: division by zero (SFINAE doesn't apply)
}

T h i s ex am p le i s an error ev en th ou g h th e s econd tem p late s u p p orts th e

s u bs ti tu ti on wi th ou t leadi ng to a di v i s i on by z ero. T h i s s ort of error m u s t occu r i n
th e ex p res s i on i ts elf and not i n bi ndi ng of an ex p res s i on to a tem p late p aram eter.
I ndeed, th e followi ng ex am p le i s v ali d:

template<int N> int g() { return N; }

template<int* P> int g() { return *P }

int main()
{
return g<1>(); // 1 cannot be bound to int* parameter,
} // but SFINAE principle applies

See Secti on 15 .2.2 on p ag e 266 and Secti on 19 .3 on p ag e 3 5 3 for fu rth er

ap p li cati ons of th e SF I N A E p ri nci p le.

8.3.2 Type Arguments

T em p late typ e arg u m ents are th e " v alu es " s p eci fi ed for tem p late typ e
p aram eters . M os t com m only u s ed typ es can be u s ed as tem p late arg u m ents , bu t
th ere are two ex cep ti ons :

1. L o c a l c la s s e s a n d e n u m e r a tio n s ( in o th e r w o r d s , ty p e s d e c la r e d in a fu n c tio n d e fin itio n ) c a n n o t b e

in v o lv e d in te m p la te ty p e a r g u m e n ts .
2 . Ty p e s t h a t i n v o l v e u n n a m e d c la s s t y p e s o r u n n a m e d e n u m e r a t io n t y p e s c a n n o t b e t e m p la te t y p e
a r g u m e n t s ( u n n a m e d c la s s e s o r e n u m e r a tio n s t h a t a r e g iv e n a n a m e t h r o u g h a ty p e d e f d e c la r a t io n
a r e O K ) .

A n ex am p le i llu s trates th es e two ex cep ti ons :

template <typename T> class List {

…
};

typedef struct {
double x, y, z;
} Point;
typedef enum { red, green, blue } *ColorPtr;

int main()
{
struct Association
{
int* p;
int* q;
};
List<Assocation*> error1; // ERROR: local type in template
argument
List<ColorPtr> error2; // ERROR: unnamed type in template
// argument
List<Point> ok; // OK: unnamed class type named
through
// a typedef
}

A lth ou g h oth er typ es can, i n g eneral, be u s ed as tem p late arg u m ents , th ei r

s u bs ti tu ti on for th e tem p late p aram eters m u s t lead to v ali d cons tru cts :

template <typename T>

void clear (T p)
{
*p = 0; // requires that the unary * be applicable to T
}
int main()
{
int a;
clear(a); // ERROR: int doesn't support the unary *
}

8.3.3 Nontype Arguments

N ontyp e tem p late arg u m ents are th e v alu es s u bs ti tu ted for nontyp e p aram eters .
Su ch a v alu e m u s t be one of th e followi ng th i ng s :

• A noth er nontyp e tem p late p aram eter th at h as th e ri g h t typ e

• A com p i le-ti m e cons tant v alu e of i nteg er (or enu m erati on) typ e. T h i s i s
accep table only i f th e corres p ondi ng p aram eter h as a typ e th at m atch es
th at of th e v alu e, or a typ e to wh i ch th e v alu e can be i m p li ci tly conv erted
(for ex am p le, a char can be p rov i ded for an int p aram eter).
• T h e nam e of an ex ternal v ari able or fu ncti on p receded by th e bu i lt-i n
u nary & (" addres s of" ) op erator. F or fu ncti ons and array v ari ables , & can
be left ou t. Su ch tem p late arg u m ents m atch nontyp e p aram eters of a
p oi nter typ e.
• T h e p rev i ou s k i nd of arg u m ent bu t wi th ou t a leadi ng & op erator i s a v ali d
arg u m ent for a nontyp e p aram eter of reference typ e.
• A p oi nter-to-m em ber cons tant; i n oth er words , an ex p res s i on of th e form
&C::m wh ere C i s a clas s typ e and m i s a nons tati c m em ber (data or
fu ncti on). T h i s m atch es nontyp e p aram eters of p oi nter-to-m em ber typ e
 only.

W h en m atch i ng an arg u m ent to a p aram eter th at i s a p oi nter or reference, u ser -

d ef i n ed c on v er si on s (cons tru ctors for one arg u m ent and conv ers i on op erators )
and deri v ed-to-bas e conv ers i ons are not cons i dered, ev en th ou g h i n oth er
ci rcu m s tances th ey wou ld be v ali d i m p li ci t conv ers i ons . I m p li ci t conv ers i ons th at
m ak e an arg u m ent m ore const or m ore volatile are fi ne.

H ere are s om e v ali d ex am p les of nontyp e tem p late arg u m ents :

template <typename T, T nontype_param>

class C;

C<int, 33>* c1; // integer type

int a;
C<int*, &a>* c2; // address of an external variable

void f();
void f(int);
C<void (*)(int), &f>* c3;
// name of a function: overload resolution
selects
// f(int) in this case; the & is implied
class X {
int n;
static bool b;
};

C<bool&, X::b>* c4; // static class members are acceptable variable

// and function names

C<int X::*, &X::n>* c5;

// an example of a pointer-to-member constant

template<typename T>
void templ_func();

C<void (), &templ_func<double> >* c6;

// function template instantiations are
functions too

A g eneral cons trai nt of tem p late arg u m ents i s th at a com p i ler or a li nk er m u s t be

able to ex p res s th ei r v alu e wh en th e p rog ram i s bei ng bu i lt. V alu es th at aren' t
k nown u nti l a p rog ram i s ru n (for ex am p le, th e addres s of local v ari ables ) aren' t
com p ati ble wi th th e noti on th at tem p lates are i ns tanti ated wh en th e p rog ram is
bu i lt.

E v en s o, th ere are s om e cons tant v alu es th at are, p erh ap s s u rp ri s i ng ly, not

cu rrently v ali d:

• N u ll p oi nter cons tants

 • F loati ng -p oi nt nu m bers
• Stri ng li terals

O ne of th e p roblem s wi th s tri ng li terals i s th at two i denti cal li terals can be s tored

at two di s ti nct addres s es . A n alternati v e (bu t cu m bers om e) way to ex p res s
tem p lates i ns tanti ated ov er cons tant s tri ng s i nv olv es i ntrodu ci ng an addi ti onal
v ari able to h old th e s tri ng :

template <char const* str>

class Message;

extern char const hello[] = "Hello World!";

Message<hello>* hello_msg;

N ote th e need for th e extern k eyword becau s e oth erwi s e a const array v ari able
wou ld h av e i nternal li nk ag e.

See Secti on 4 .3 on p ag e 4 0 for anoth er ex am p le and Secti on 13 .4 on p ag e 209

for a di s cu s s i on of p os s i ble fu tu re ch ang es i n th i s area.

H ere are few oth er (les s s u rp ri s i ng ) i nv ali d ex am p les :

template<typename T, T nontype_param>
class C;

class Base {
int i;
} base;

class Derived : public Base {

} derived_obj;

C<Base*, &derived_obj>* err1; // ERROR: derived-to-base conversions

are
// not considered

C<int&, base.i>* err2; // ERROR: fields of variables aren't

// considered to be variables

int a[10];
C<int*, &a[0]>* err3; // ERROR: addresses of individual
array
// elements aren't acceptable
either

8.3.4 Template Template Arguments

A tem p late tem p late arg u m ent m u s t be a clas s tem p late wi th p aram eters th at
ex ac tly m atch th e p aram eters of th e tem p late tem p late p aram eter i t s u bs ti tu tes .
D efau lt tem p late arg u m ents of a tem p late tem p late ar g u men t are i g nored (bu t i f
th e tem p late tem p late par ameter h as defau lt arg u m ents , th ey are cons i dered
du ri ng th e i ns tanti ati on of th e tem p late).

T h i s m ak es th e followi ng ex am p le i nv ali d:

#include <list>
// declares:
// namespace std {
// template <typename T,
// typename Allocator = allocator<T> >
// class list;
// }
template<typename T1,
typename T2,
template<typename> class Container>
// Container expects templates with only
// one parameter
class Relation {
public:
…
private:
Container<T1> dom1;
Container<T2> dom2;
};

int main()
{
Relation<int, double, std::list> rel;
// ERROR: std::list has more than one template parameter
…
}

T h e p roblem i n th i s ex am p le i s th at th e std::list tem p late of th e s tandard

li brary h as m ore th an one p aram eter. T h e s econd p aram eter (wh i ch des cri bes a
s o-called alloc ator ) h as a defau lt v alu e, bu t th i s i s not cons i dered wh en m atch i ng
std::list to th e Container p aram eter.

Som eti m es , s u ch s i tu ati ons can be work ed arou nd by addi ng a p aram eter wi th a
defau lt v alu e to th e tem p late tem p late p aram eter. I n th e cas e of th e p rev i ou s
ex am p le, we m ay rewri te th e Relation tem p late as follows :

#include <memory>

template<typename T1,
typename T2,
template<typename T,
typename = std::allocator<T> > class Container>
// Container now accepts standard container templates
class Relation {
public:
…
private:
Container<T1> dom1;
Container<T2> dom2;
};

C learly th i s i s n' t enti rely s ati s factory, bu t i t enables th e u s e of s tandard contai ner
tem p lates . Secti on 13 .5 on p ag e 211 di s cu s s es p os s i ble fu tu re ch ang es of th i s
top i c.

T h e fact th at s yntacti cally only th e k eyword class can be u s ed to declare a

tem p late tem p late p aram eter i s not to be cons tru ed as an i ndi cati on th at only
clas s tem p lates declared wi th th e k eyword class are allowed as s u bs ti tu ti ng
arg u m ents . I ndeed, " s tru ct tem p lates " and " u ni on tem p lates " are v ali d arg u m ents
for a tem p late tem p late p aram eter. T h i s i s s i m i lar to th e obs erv ati on th at (j u s t
abou t) any typ e can be u s ed as an arg u m ent for a tem p late typ e p aram eter
declared wi th th e k eyword class.

8.3.5 Equivalence

T wo s ets of tem p late arg u m ents are eq u i v alent wh en v alu es of th e arg u m ents are
i denti cal one-for-one. F or typ e arg u m ents , typ edef nam es don' t m atter: I t i s th e
typ e u lti m ately u nderlyi ng th e typ edef th at i s com p ared. F or i nteg er nontyp e
arg u m ents , th e v alu e of th e arg u m ent i s com p ared; h ow th at v alu e i s ex p res s ed
does n' t m atter. T h e followi ng ex am p le i llu s trates th i s concep t:

template <typename T, int I>

class Mix;

typedef int Int;

Mix<int, 3*3>* p1;

Mix<Int, 4+5>* p2; // p2 has the same type as p1

A fu ncti on g enerated from a fu ncti on tem p late i s nev er eq u i v alent to an ordi nary
fu ncti on ev en th ou g h th ey m ay h av e th e s am e typ e and th e s am e nam e. T h i s h as
two i m p ortant cons eq u ences for clas s m em bers :

1. A fu n c tio n g e n e r a t e d fr o m a m e m b e r f u n c t io n te m p la te n e v e r o v e r r id e s a v ir t u a l fu n c tio n .
2 . A c o n s tr u c to r g e n e r a t e d fr o m a c o n s t r u c t o r t e m p la t e is n e v e r a d e f a u lt c o p y c o n s t r u c t o r .( S im ila r ly ,
a n a s s ig n m e n t g e n e r a te d fr o m a n a s s ig n m e n t t e m p l a t e i s n e v e r a c o p y -a s s i g n m e n t o p e r a t o r .
H o w e v e r , t h is is le s s p r o n e to p r o b le m s b e c a u s e u n lik e c o p y c o n s tr u c t o r s , a s s ig n m e n t o p e r a to r s
a r e n e v e r c a l l e d i m p l i c i t l y .)
8.4 Friends

T h e bas i c i dea of fri end declarati ons i s a s i m p le one: I denti fy clas s es or fu ncti ons
th at h av e a p ri v i leg ed connecti on wi th th e clas s i n wh i ch th e fri end declarati on
ap p ears . M atters are s om ewh at com p li cated, h owev er, by two facts :

1. A fr ie n d d e c la r a tio n m a y b e t h e o n ly d e c la r a tio n o f a n e n tity .

2 . A fr ie n d fu n c tio n d e c la r a tio n c a n b e a d e fin itio n .

F ri end clas s declarati ons cannot be defi ni ti ons and th erefore are rarely
p roblem ati c. I n th e contex t of tem p lates , th e only new facet of fri end clas s
declarati ons i s th e abi li ty to nam e a p arti cu lar i ns tance of a clas s tem p late as a
fri end:

template <typename T>

class Node;

template <typename T>

class Tree {
friend class Node<T>;
…
};

N ote th at th e clas s tem p late m u s t be v i s i ble at th e p oi nt wh ere one of i ts

i ns tances i s m ade a fri end of a clas s or clas s tem p late. W i th an ordi nary clas s ,
th ere i s no s u ch req u i rem ent:

template <typename T>

class Tree {
friend class Factory; // OK, even if first declaration of
Factory
friend class class Node<T>; // ERROR if Node isn't visible
};

Secti on 9 .2.2 on p ag e 125 h as m ore to s ay abou t th i s .

8.4.1 Friend Functions

A n i ns tance of a fu ncti on tem p late can be m ade a fri end by m ak i ng s u re th e

nam e of th e fri end fu ncti on i s followed by ang le brack ets . T h e ang le brack ets can
contai n th e tem p late arg u m ents , bu t i f th e arg u m ents can be dedu ced, th e ang le
brack ets can be left em p ty:

template <typename T1, typename T2>

void combine(T1, T2);
class Mixer {
friend void combine<>(int&, int&);
// OK: T1 = int&, T2 = int&
friend void combine<int, int>(int, int);
// OK: T1 = int, T2 = int
friend void combine<char>(char, int);
// OK: T1 = char T2 = int
friend void combine<char>(char&, int);
// ERROR: doesn't match combine() template
friend void combine<>(long, long) { … }
// ERROR: definition not allowed!
};

N ote th at we cannot d ef i n e a tem p late i ns tance (at m os t, we can defi ne a

s p eci ali z ati on), and h ence a fri end declarati on th at nam es an i ns tance cannot be
a defi ni ti on.

I f th e nam e i s not followed by ang le brack ets , th ere are two p os s i bi li ti es :

1. I f t h e n a m e is n 't q u a lifie d ( in o t h e r w o r d s , it d o e s n 't c o n t a in a d o u b le c o lo n ) , it n e v e r r e f e r s t o a

te m p la te in s t a n c e .I f n o m a tc h in g n o n te m p la t e fu n c tio n is v is ib le a t t h e p o in t o f th e fr ie n d
d e c l a r a t i o n , t h e f r i e n d d e c l a r a t i o n i s t h e f i r s t d e c l a r a t i o n o f t h a t f u n c t i o n . Th e d e c l a r a t i o n c o u l d a l s o
b e a d e fin itio n .
2 . I f t h e n a m e is q u a l i f i e d ( i t c o n t a i n s ::) , t h e n a m e m u s t r e f e r t o a p r e v i o u s l y d e c l a r e d f u n c t i o n o r
fu n c tio n te m p la t e .A m a t c h in g fu n c tio n is p r e f e r r e d o v e r a m a t c h in g fu n c tio n te m p la t e .H o w e v e r ,
s u c h a fr ie n d d e c la r a t io n c a n n o t b e a d e fin itio n .

A n ex am p le m ay h elp clari fy th e v ari ou s p os s i bi li ti es :

void multiply (void*); // ordinary function

template <typename T>

void multiply(T); // function template

class Comrades {
friend multiply(int) {}
// defines a new function ::multiply(int)

friend ::multiply(void*);
// refers to the ordinary function above;
// not to the multiply<void*> instance

friend ::multiply(int);
// refers to an instance of the template

friend ::multiply<double*>(double*);
// qualified names can also have angle
brackets
// but a template must be visible.

friend ::error() {}
// ERROR: a qualified friend cannot be a
definition
};

I n ou r p rev i ou s ex am p les , we declared th e fri end fu ncti ons i n an ordi nary clas s .
T h e s am e ru les ap p ly wh en we declare th em i n clas s tem p lates , bu t th e tem p late
p aram eters m ay p arti ci p ate i n i denti fyi ng th e fu ncti on th at i s to be a fri end:

template <typename T>

class Node {
Node<T>* allocate();
…
};

template <typename T>

class List {
friend Node<T>* Node<T>::allocate();
…
};

H owev er, an i nteres ti ng effect occu rs wh en a fri end fu ncti on i s d ef i n ed i n a clas s

tem p late becau s e anyth i ng th at i s only declared i n a tem p late i s n' t a concrete
enti ty u nti l th e tem p late i s i ns tanti ated. C ons i der th e followi ng ex am p le:

template <typename T>

class Creator {
friend void appear() { // a new function ::appear(), but it
doesn't
… // exist until Creator is instantiated
}
};

Creator<void> miracle; // ::appear() is created at this point

Creator<double> oops; // ERROR: ::appear() is created a second
time!

I n th i s ex am p le, two di fferent i ns tanti ati ons create two i denti cal defi ni ti ons —a
di rect v i olati on of th e O D R (s ee A p p endi x A ).

W e m u s t th erefore m ak e s u re th e tem p late p aram eters of th e clas s tem p late

ap p ear i n th e typ e of any fri end fu ncti on defi ned i n th at tem p late (u nles s we want
to p rev ent m ore th an one i ns tanti ati on of a clas s tem p late i n a p arti cu lar fi le, bu t
th i s i s rath er u nli k ely). L et' s ap p ly th i s to a v ari ati on of ou r p rev i ou s ex am p le:

template <typename T>

class Creator {
friend void feed(Creator<T>*){ // every T generates a different
… // function ::feed()
}
};

Creator<void> one; // generates ::feed(Creator<void>*)

Creator<double> two; // generates ::feed(Creator<double>*)

I n th i s ex am p le, ev ery i ns tanti ati on of Creator g enerates a di fferent fu ncti on.

N ote th at ev en th ou g h th es e fu ncti ons are g enerated as p art of th e i ns tanti ati on
 of a tem p late, th e fu ncti ons th em s elv es are ordi nary fu ncti ons , not i ns tances of a
tem p late.

A ls o note th at becau s e th e body of th es e fu ncti ons i s defi ned i ns i de a clas s

defi ni ti on, th ey are i m p li ci tly i nli ne. H ence, i t i s not an error for th e s am e fu ncti on
to be g enerated i n two di fferent trans lati on u ni ts . Secti on 9 .2.2 on p ag e 125 and
Secti on 11.7 on p ag e 17 4 h av e m ore to s ay abou t th i s top i c.

8.4.2 Friend Templates

U s u ally wh en declari ng a fri end th at i s an i ns tance of a fu ncti on or a clas s

tem p late, we can ex p res s ex actly wh i ch enti ty i s to be th e fri end. Som eti m es i t i s
noneth eles s u s efu l to ex p res s th at all i ns tances of a tem p late are fri ends of a
clas s . T h i s req u i res a s o-called f r i en d template. F or ex am p le:

class Manager {
template<typename T>
friend class Task;
template<typename T>
friend void Schedule<T>::dispatch(Task<T>*);
template<typename T>
friend int ticket() {
return ++Manager::counter;
}
static int counter;
};

J u s t as wi th ordi nary fri end declarati ons a fri end tem p late can be a defi ni ti on only
i f i t nam es an u nq u ali fi ed fu ncti on nam e th at i s not followed by ang le brack ets .

A fri end tem p late can declare only p ri m ary tem p lates and m em bers of p ri m ary
tem p lates . A ny p arti al s p eci ali z ati ons and ex p li ci t s p eci ali z ati ons as s oci ated wi th a
p ri m ary tem p late are au tom ati cally cons i dered fri ends too.
8.5 Afternotes

T h e g eneral concep t and s yntax of C + + tem p lates h av e rem ai ned relati v ely
s table s i nce th ei r i ncep ti on i n th e late 19 8 0s . C las s tem p lates and fu ncti on
tem p lates were p art of th e i ni ti al tem p late faci li ty. So were typ e p aram eters and
nontyp e p aram eters .

H owev er, th ere were als o s om e s i g ni fi cant addi ti ons to th e ori g i nal des i g n, m os tly
dri v en by th e needs of th e C + + s tandard li brary. M em ber tem p lates m ay well be
th e m os t fu ndam ental of th os e addi ti ons . C u ri ou s ly, only m em ber f u n c ti on
tem p lates were form ally v oted i nto th e C + + s tandard. M em ber c lass tem p lates
becam e p art of th e s tandard by an edi tori al ov ers i g h t.

F ri end tem p lates , defau lt tem p late arg u m ents , and tem p late tem p late p aram eters
are als o relati v ely recent addi ti ons to th e lang u ag e. T h e abi li ty to declare
tem p late tem p late p aram eters i s s om eti m es called hi g her -or d er g en er i c i ty . T h ey
were ori g i nally i ntrodu ced to s u p p ort a certai n allocator m odel i n th e C + +
s tandard li brary, bu t th at allocator m odel was later rep laced by one th at does not
rely on tem p late tem p late p aram eters . L ater, tem p late tem p late p aram eters
cam e clos e to bei ng rem ov ed from th e lang u ag e becau s e th ei r s p eci fi cati on h ad
rem ai ned i ncom p lete u nti l v ery late i n th e s tandardi z ati on p roces s . E v entu ally a
m aj ori ty of com m i ttee m em bers v oted to k eep th em and th ei r s p eci fi cati ons were
com p leted.
Chapter 9. Names in Templates

N am es are a fu ndam ental concep t i n m os t p rog ram m i ng lang u ag es . T h ey are th e

m eans by wh i ch a p rog ram m er can refer to p rev i ou s ly cons tru cted enti ti es . W h en
aC + + com p i ler encou nters a nam e, i t m u s t " look i t u p " to i denti fy to wh i ch enti ty
i s bei ng referred. F rom an i m p lem enter' s p oi nt of v i ew, C + + i s a h ard lang u ag e i n
th i s res p ect. C ons i der th e C + + s tatem ent x*y; .I fx and y are th e nam es of
v ari ables , th i s s tatem ent i s a m u lti p li cati on, bu t i f x i s th e nam e of a typ e, th en
th e s tatem ent declares y as a p oi nter to an enti ty of typ e x.

T h i s s m all ex am p le dem ons trates th at C + + (li k e C ) i s a s o-called c on tex t-

sen si ti v e lan g u ag e: A cons tru ct cannot always be u nders tood wi th ou t k nowi ng i ts
wi der contex t. H ow does th i s relate to tem p lates ? W ell, tem p lates are cons tru cts
th at m u s t deal wi th m u lti p le wi der contex ts : (1) th e contex t i n wh i ch th e
tem p late ap p ears , (2) th e contex t i n wh i ch th e tem p late i s i ns tanti ated, and (3 )
th e contex ts as s oci ated wi th th e tem p late arg u m ents for wh i ch th e tem p late i s
i ns tanti ated. H ence i t s h ou ld not be totally s u rp ri s i ng th at " nam es " m u s t be dealt
wi th q u i te carefu lly i n C + + .
9.1 Name Taxonomy

C + + clas s i fi es nam es i n a v ari ety of ways —a larg e v ari ety of ways i n fact. T o h elp
cop e wi th th i s abu ndance of term i nolog y, we p rov i de tables T able 9 .1 and T able
9 .2, wh i ch des cri be th es e clas s i fi cati ons . F ortu nately, you can g ai n g ood i ns i g h t
i nto m os t C + + tem p late i s s u es by fam i li ari z i ng you rs elf wi th two m aj or nam i ng
concep ts :

1. A n a m e i s a q u a l if ie d n a m e if th e s c o p e to w h ic h it b e lo n g s is e x p lic itly d e n o t e d u s in g a
s c o p e r e s o l u t i o n o p e r a t o r ( ::) o r a m e m b e r a c c e s s o p e r a t o r ( . o r ->) . F o r e x a m p l e , this->count
i s a q u a l i f i e d n a m e , b u t count i s n o t ( e v e n t h o u g h t h e p l a i n count m i g h t a c t u a l l y r e f e r t o a c l a s s
m e m b e r ) .
2 . A n a m e is a d e p e n d e n t n a m e if it d e p e n d s in s o m e w a y o n a t e m p la te p a r a m e te r .F o r e x a m p le ,
std::vector<T>::iterator i s a d e p e n d e n t n a m e i f T i s a t e m p l a t e p a r a m e t e r , b u t i t i s a
n o n d e p e n d e n t n a m e if Tis a k n o w n t y p e d e f ( fo r e x a m p l e , o f int) .

Table 9.1. Name Taxonomy (part one)

C las s i f i c ati on E xplanati on and Notes
I denti fi er A nam e th at cons i s ts s olely of an u ni nterru p ted s eq u ences of
letters , u nders cores (_) and di g i ts . I t cannot s tart wi th a di g i t,
and s om e i denti fi ers are res erv ed for th e i m p lem entati on: Y ou
s h ou ld not i ntrodu ce th em i n you r p rog ram s (as a ru le of th u m b,
av oi d leadi ng u nders cores and dou ble u nders cores ). T h e concep t
of " letter" s h ou ld be tak en broadly and i nclu des s p eci al u n i v er sal
c har ac ter n ames (U CNs) th at encode g lyp h s from
nonalp h abeti cal lang u ag es .
O p erator- T h e k eyword operator followed by th e s ym bol for an
fu ncti on-i d op erator— for ex am p le, operator new and operator [ ].
M any op erators h av e alternati v e rep res entati ons . F or ex am p le,
operator & can eq u i v alently be wri tten as operator bitand
ev en wh en i t denotes th e u nary ad d r ess of op erator.
C onv ers i on- U s ed to denote u s er-defi ned i m p li ci t conv ers i on op erator—for
fu ncti on-i d ex am p le operator int&, wh i ch cou ld als o be obfu s cated as
operator int bitand.
T em p late-i d T h e nam e of a tem p late followed by tem p late arg u m ents
enclos ed i n ang le brack ets ; for ex am p le, List<T, int, 0>.
(Stri ctly s p eak i ng , th e C + + s tandard allows only s i m p le
i denti fi ers for th e tem p late nam e of a tem p late-i d. H owev er, th i s
i s p robably an ov ers i g h t and an op erator-fu ncti on-i d s h ou ld be
allowed too; e.g . operator+<X<int> >.)
U nq u ali fi ed-i d T h e g enerali z ati on of an i denti fi er. I t can be any of th e abov e
(i denti fi er, op erator-fu ncti on-i d, conv ers i on-fu ncti on-i d or
 (i denti fi er, op erator-fu ncti on-i d, conv ers i on-fu ncti on-i d or
tem p late-i d) or a " des tru ctor nam e" (for ex am p le, notati ons li k e
~Data or ~List<T, T, N>).
Q u ali fi ed-i d A n u nq u ali fi ed-i d th at i s q u ali fi ed wi th th e nam e of a clas s or
nam es p ace, or j u s t wi th th e g lobal s cop e res olu ti on op erator.
N ote th at s u ch a nam e i ts elf can be q u ali fi ed. E x am p les are ::X,
S::x, Array<T>::y, and ::N::A<T>::z.
Q u ali fi ed nam e T h i s term i s not defi ned i n th e s tandard, bu t we u s e i t to refer to
nam es th at u nderg o s o-called q u ali f i ed look u p. Sp eci fi cally, th i s
i s a q u ali fi ed-i d or an u nq u ali fi ed-i d th at i s u s ed after an ex p li ci t
m em ber acces s op erator (. or ->). E x am p les are S::x, this-
>f, and p->A::m. H owev er, j u s t class_mem i n a contex t th at i s
i m p li ci tly eq u i v alent to this->class_mem i s not a q u ali fi ed
nam e: T h e m em ber acces s m u s t be ex p li ci t.
U nq u ali fi ed A n u nq u ali fi ed-i d th at i s not a q u ali fi ed nam e. T h i s i s not a
nam e s tandard term bu t corres p onds to nam es th at u nderg o wh at th e
s tandard calls u n q u ali f i ed look u p.

Table 9.2 . Name Taxonomy (part tw o)

C las s i f i c ati on E xplanati on and Notes
N am e E i th er a q u ali fi ed or an u nq u ali fi ed nam e.
D ep endent A nam e th at dep ends i n s om e way on a tem p late p aram eter.
nam e C ertai nly any q u ali fi ed or u nq u ali fi ed nam e th at ex p li ci tly
contai ns a tem p late p aram eter i s dep endent. F u rth erm ore, a
q u ali fi ed nam e th at i s q u ali fi ed by a m em ber acces s op erator (.
or ->) i s dep endent i f th e typ e of th e ex p res s i on on th e left of
th e acces s op erator dep ends on a tem p late p aram eter. I n
p arti cu lar, b i n this->b i s a dep endent nam e wh en i t ap p ears
i n a tem p late. F i nally, th e i denti fi er ident i n a call of th e form
ident(x, y, z) i s a dep endent nam e i f and only i f any of th e
arg u m ent ex p res s i ons h as a typ e th at dep ends on a tem p late
p aram eter.
N ondep endent A nam e th at i s not a dep endent nam e by th e abov e des cri p ti on.
nam e

I t i s u s efu l to read th rou g h th e tables to g ai n s om e fam i li ari ty wi th th e term s th at

are s om eti m es u s ed to des cri be C + + tem p late i s s u es , bu t i t i s not es s enti al to
rem em ber th e ex act m eani ng of ev ery term . Sh ou ld th e need ari s e, th ey can be
eas i ly fou nd i n th e i ndex .
9.2 Looking Up Names

T h ere are m any s m all detai ls to look i ng u p nam es i n C + + , bu t we wi ll focu s only

on a few m aj or concep ts . T h e detai ls are neces s ary to ens u re only th at (1)
norm al cas es are treated i ntu i ti v ely, and (2) p ath olog i cal cas es are cov ered i n
s om e way by th e s tandard.

Q u ali fi ed nam es are look ed u p i n th e s cop e i m p li ed by th e q u ali fyi ng cons tru ct. I f
th at s cop e i s a clas s , th en bas e clas s es m ay als o be look ed u p . H owev er,
enclos i ng s cop es are not cons i dered wh en look i ng u p q u ali fi ed nam es . T h e
followi ng i llu s trates th i s bas i c p ri nci p le:

int x;

class B {
public:
int i;
};

class D : public B {
};
void f(D* pd)
{
pd->i = 3; // finds B::i
D::x = 2; // ERROR: does not find ::x in the enclosing scope
}

I n contras t, u nq u ali fi ed nam es are typ i cally look ed u p i n s u cces s i v ely m ore
enclos i ng s cop es (alth ou g h i n m em ber fu ncti on defi ni ti ons th e s cop e of th e clas s
and i ts bas e clas s es i s s earch ed before any oth er enclos i ng s cop es ). T h i s i s called
or d i n ar y look u p. H ere i s a bas i c ex am p le s h owi ng th e m ai n i dea u nderlyi ng
ordi nary look u p :

extern int count; // (1)

int lookup_example(int count) // (2)

{
if (count < 0) {
int count = 1; // (3)
lookup_example(count); // unqualified count refers to (3)
}
return count + ::count; // the first (unqualified) count
refers to (2);
} // the second (qualified) count
refers to (1)

A m ore recent twi s t to th e look u p of u nq u ali fi ed nam es i s th at—i n addi ti on to

ordi nary look u p —th ey m ay s om eti m es u nderg o s o-called ar g u men t-d epen d en t
[1]
look u p (AD L ). [1]
B efore p roceedi ng wi th th e detai ls of A D L , let' s m oti v ate th e
m ech ani s m wi th ou r p erenni al max() tem p late:

[1]
T h i s i s als o called K oen i g look u p (or ex ten d ed K oen i g look u p)
after A ndrew K oeni g , wh o fi rs t p rop os ed a v ari ati on of th i s
m ech ani s m .

template <typename T>

inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}

Su p p os e now th at we need to ap p ly th i s tem p late to a typ e defi ned i n anoth er

nam es p ace:

namespace BigMath {
class BigNumber {
…
};
bool operator < (BigNumber const&, BigNumber const&);
…
}
using BigMath::BigNumber;

void g (BigNumber const& a, BigNumber const& b)

{
…
BigNumber x = max(a,b);
…
}

T h e p roblem h ere i s th at th e max() tem p late i s u naware of th e BigMath

nam es p ace, bu t ordi nary look u p wou ld not fi nd th e op erator < ap p li cable to
v alu es of typ e BigNumber. W i th ou t s om e s p eci al ru les , th i s g reatly redu ces th e
ap p li cabi li ty of tem p lates i n th e contex t of C + + nam es p aces . A D L i s th e C + +
ans wer to th os e " s p eci al ru les ."

9.2.1 Argument-Dependent Lookup

A D L ap p li es only to u nq u ali fi ed nam es th at look li k e th ey nam e a nonm em ber

fu ncti on i n a fu ncti on call. I f ordi nary look u p fi nds th e nam e of a m em ber fu ncti on
or th e nam e of a typ e, th en A D L does not h ap p en. A D L i s als o i nh i bi ted i f th e
nam e of th e fu ncti on to be called i s enclos ed i n p arenth es es .

O th erwi s e, i f th e nam e i s followed by a li s t of arg u m ent ex p res s i ons enclos ed i n

p arenth es es , A D L p roceeds by look i ng u p th e nam e i n nam es p aces and clas s es
" as s oci ated wi th " th e typ es of th e call arg u m ents . T h e p reci s e defi ni ti on of th es e
assoc i ated n amespac es and assoc i ated c lasses i s g i v en later, bu t i ntu i ti v ely th ey
can be th ou g h t as bei ng all th e nam es p aces and clas s es th at are fai rly di rectly
connected to a g i v en typ e. F or ex am p le, i f th e typ e i s a p oi nter to a clas s X, th en
th e as s oci ated clas s es and nam es p ace wou ld i nclu de X as well as any
nam es p aces or clas s es to wh i ch X belong s .

T h e p reci s e defi ni ti on of th e s et of assoc i ated n amespac es and assoc i ated c lasses

for a g i v en typ e i s determ i ned by th e followi ng ru les :

• F or bu i lt-i n typ es , th i s i s th e em p ty s et.

• F or p oi nter and array typ es , th e s et of as s oci ated nam es p aces and clas s es
i s th at of th e u nderlyi ng typ e.
• F or enu m erati on typ es , th e as s oci ated nam es p ace i s th e nam es p ace i n
wh i ch th e enu m erati on i s declared. F or clas s m em bers , th e enclos i ng clas s
i s th e as s oci ated clas s .
• F or clas s typ es (i nclu di ng u ni on typ es ) th e s et of as s oci ated clas s es i s th e
typ e i ts elf, th e enclos i ng clas s , and any di rect and i ndi rect bas e clas s es .
T h e s et of as s oci ated nam es p aces i s th e nam es p aces i n wh i ch th e
as s oci ated clas s es are declared. I f th e clas s i s a clas s tem p late
i ns tanti ati on, th en th e typ es of th e tem p late typ e arg u m ents and th e
clas s es and nam es p aces i n wh i ch th e tem p late tem p late arg u m ents are
declared are als o i nclu ded.
• F or fu ncti on typ es , th e s ets of as s oci ated nam es p aces and clas s es
com p ri s e th e nam es p aces and clas s es as s oci ated wi th all th e p aram eter
typ es and th os e as s oci ated wi th th e retu rn typ e.
• F or p oi nter-to-m em ber-of-clas s -X typ es , th e s ets of as s oci ated
nam es p aces and clas s es i nclu de th os e as s oci ated wi th X i