The Standard Template Library - Alexander Stepanov

mII HEWLBTTa:aI.PACKARDThe Standard Template LibraryAlexander StepanovMengLeeHewlett Packard Laboratories1501 Page Mill Road, Palo Alio, CA 94304stepanovtehpl.hp.com & lee@hpl.hp.comMarch 7, 1994,J

The design principles:1. Comprehensive- take all the bestfrom APL, Lisp, Dylan, C library, USL Standard Components.- provide structure andfill the gaps2. Extensible- orthogonality ofthe component space- semantically based interoperability guarantees3. Emcient- no penalty for generality- complexity guarantees at the interface level4. Natural- C/C machine model and programming paradigm- support for built-in data typesThe Standard Template Library2/Fli;'HEWLETTa: PACKARD

Component Classification: container -manages a set of memory locations iterator - provides a traversal protocol through a container algorithm - encapsulates a computational process applicative object - encapsulates a state (possibly empty) together with analgorithmThe Standard Template LInry3Fli;' HEWLETTa: PACKARD

Mergeint a[lOOO]iint b(2000)iint c[3000);mergeCopy(a, a 1000, b, b 2000, C)iVector int XiList int Yiint z [ . )aergeCopy (X. begin ( ), x. end ( ), y. begin ( ), y. end ( ), z) ;4rG'l HEWLETT PACKARD

MergeCopy(l)template class Iteratorl, class Iterator2, class Resultlterator Resultlterator mergeCopy(Iteratorl first, Iteratorl last,Iterator2 otherFirst, Iterator2 otherLast,Resultlterator result) {while (first ! iast && otherFirst ! otherLast)if (*otherFirst *first *result *otherFirst ielse*result *first ireturn copy(otherFirst, otherLast, copy(first, last, result»i)5rG'll HEWLETT z.tI PACKARD

,jiIIftIMergeCopy(2)template class Iteratorl, class Iterator2, class ResultIterator,class Cc:.pare ResultIterator mergeCopy(Iteratorl first, Iteratorl last,Iterator2 otherFirst, Iterator2 otherLast,Resultlterator result, Compare comp) {while (first ! last && otherFirst ! otherLast)if (comp(*otherFirst, *first»*result *otherFirst ;else*result *first ;return copy (otherFirst, otherLast, copy(first, last, result»;}FJiiiW HEWLETT PACKARD

Intmerge'include 8tl.h main(int argc, char** argv) {if (argc ! 3) throw(-usage: intmerge filel file2\n-)imerg8Copy(InputIterator int (ifstream(argv[l]», Inputlterator int (O),InputIterator int (ifstream(argv[2]», Inputlterator int (O),Outputlterator int (N\nN»i}The Standard Tempt 1 Ubraty7FGII HEWLE.TT PACKARD

Deterministic sort: free reference implementation of sorttemplate class BidirectionalIterator void deterministicSort{BidirectionalIterator first,Bidirectionallterator last) {while (nextPermutation(first, last»;)te.plate class Iterator, class Compare void deterministicSort(Bidirectionallterator first,Bidirectionallterator last, Compare comp) {while (nextPermutation(first, last, comp»;}The Standard T. LInry8r HEWLETTIto. PACKARD

Partial sortlinclude stl.h II prints n -Jl t integers fra. stdinmain(int argc, char·· argyl {if (argc ! 2)throw("usage: partialsort number\n")iVector int v(size t(atoi(argv[l]», O)icopy(v.begin(),partialSortCopy(Inputlterator int (), Inputlj:erator int (O),v.begin(), v.end(»,OUtputlterator int ("\n"»i}The Standard Template Libnuy9rmHEWLETTPACKARDa:!&

Sort'include stl.h 'include -string.H NII .orts a file l-.ioographical1ymain(int argc, char**) {if (argc ! 1) throw(Nusage: sort\nN)iVector String Vicopy(Inputlterator String (), Inputlterator String (O),VectorlnsertIterator String (v, v.end(»)isort(v.begin(), v.end(»icopy(v.begin(), v.end(), OUtputlterator String (»;}The Standard Template Ubrary10.rG'l HEWLETT gPACKARD

Sequence containers:Vector:random accessconstant time (amortized) insert and erase at the endList:sequentialaccessconstant time insert and erase anywhereDeque:random access (but slower than Vector)constant time insert and erase at the beginning .and the endAll three share the same interfaceThe Standard Template LIwaIy11 HEWLETT PACKARD

Taxonomy of iteratorsPrimary Forward iterator Bidirectional iterator Random access iteratorAdditional Iterator, result iterator - weaker versions of forward iterators Insert iterator - special kind of result iterator Bidirectional reverse iterator, random access reverse iterator - reverse iteratorsNOTE: ALL THESE ARE NOT CLASSES BUT CLASS REQUIREMENTSThe Standard Template Ubrary12FG'II HEWLETTa:UPACKARD

Iterator template classes: -0,Random access iteratton:(pointer), ReversePointer, DequeIterator, Dequekeverselterator .Bidirectionalltentors:Lisdterator, ListReverseIteratorIteraton:InpudteratorResult iteraton:OutputIterator, VectorlnsertIterator, ListInsertIterator, DequeInsertIterator,InsertPointerThe Standard Template Ubnuy13 ·HEWLETT PACKARD

Applicative objects:cout « Greater int () (27, 5);prints: truecout « GreaterX int (5) (27); II bind the secondprints: truecout « XGreater int (27) (5); II bind the firstprints: truear l. .nt·ar lmeDtExample:int a[10000]isort(a, a 10000, Greater int (»; II sort in descending orderThe Standard Template Ubrary14 HEWLETT U11 PACKARD

Appli ativetemplate classesIdentityBiDary arithmetic operations:Plus, Minus, Times, Divides, Modulus (with X op and -cope-X)."i,;Unary arithmetic operations: NegateBinary relational operations:Equal, NotEqual, Greater, Less, GreaterEqual, LessEqual (with Xcop and OP X)Unary reladoaal operations: NotIncrement & decrement:PrefixPlusplus, PostfixPlusplus, PrefixMinusminus, PostfixMinusminusAssipmentTrivial predicates: .True, FalseThe Standard Template Ubrary15.Fl3HEWLETT· PACKARD

Algorithmic template functions:SwapFunctions 011 ordered elements: min, maxGeneral Itentlons: forBach, accumulate, innerProductSearching: find, adjacentFind, mismatch, equal, search, countOrder selectors: maxElement, minElementLeDcographical comparisons: lexicographicalCompareSeMdd.ng in sorted structures: lesserRange, greaterRange, equalRange, isMeniberTransformers: copy, copyBackward, swapRanges, transform, transformCopy, replace,replaceCopy, partialSum, partialSumCopy, adjacentDifference, adjacentDifferenceCopy,fill, iota.Removers: remove, removeCopy, unique, uniqueCopyMerging of sorted structures: merge, mergeCopyThe Standard Template Ubrary16. rJ.'I3.'D. HEWLETT PACKARD

Set operations on sorted structures: includes, unionCopy, intersectionCopy,differenceCopy, symmetricDifferenceCopyPermutations: reverse, reverseCopy, rotate, rotateCopy, randomShuffiePermutation genentors: nextPermutation, prevPermutationPartitions: partition, stablePartitionSorting: sort, stableSort, partialSort, partialSortCopy, selectHeap operations: pushHeap, popfIeap, makeHeap, sortHeapList mutative operations: listRemove, listUnique, listMerge, listReverse, listSortThe Standard Template Ubrary17r!3HEWLETT PACKARD

Memory management template class T T* allocate(size t n, T*);template class T void·deallocate(T*buffer);.,'.template class T Pair T*, size t getTemporaryBuffer(size t n, T*);template class T void construct(T* p, const T& value);template class T void destroy(T* pointer);template class T void destroy(T* first, T* last);The Standard Template Library18r .HEWLETT PACKARD

Conclusions:-II1. lIP position:- make the library widely available, :: reference implementation and validation suite are under consideration2. The status of the library:- fully implemented under HP C compiler- tested, the full validation suite is under construction- porting to other compilers is under wayThe Standard Template LInry19FJ.3 HEWLETT PACKARD

The Standard Template Library Author: Alexander Stepanov and Meng Lee Subject: Hewlett Packard Laboratories, March 7, 1994 Created Date: 5/27/2007 1:43:11 PM .