Embracing Stl

Embracing Stl - Transcript

Embracing the C STL Why Angle Brackets are Good for You
Pete Isensee

GDC Roadtrip Dec 1999

Introduction Introduction
STL Background History s Key Concepts s Containers Iterators and Algorithms s Efficiency and Thread Safety s Tips and Tricks
s

GDC

Goals Goals
s

STL Newbie STL Junkie

Convince you that it s a good thing Help you avoid common mistakes Add new STL techniques to your toolbox Tricks and tips

s

GDC

Preliminaries Preliminaries
Microsoft Visual C 6 0 s Dinkumware STL implementation s Benchmarks on Pentium III 550MHz s Performance graphs show relative performance taller is better
s

GDC

History History
Alex Stepanov Meng Lee based on earlier work by Stepanov Musser s Proposed to C committee late 93 s HP version released 94 s Accepted into Standard summer 94 s Standard froze 97 ratified 98
s

GDC

Advantages Advantages
Standardized s Thin efficient s Little inheritance no virtual functions s Small easy to learn s Flexible and extensible s Naturally open source
s

GDC

Disadvantages Disadvantages
Template syntax s Difficult to read decipher s Poor or incomplete compiler support s Code bloat potential s No constraints on template types s Limited container types
s

GDC

Key Concepts Key Concepts
Generic algorithms s Container classes s Iterators container walkers for accessing container elements s Iterators provide an abstraction of container access which in turn allows for generic algorithms s Iterator invalidation
s GDC

Key Concepts cont Key Concepts cont
s

Ranges C C past the end pointer
T Wallace N T p Wallace N valid pointer T T w Wallace N invalid dereference Wallace c begin Wallace c begin c end Wallace N c end c end c end first element valid iterator invalid dereference

end begin size s if begin end container is empty s for iter i begin i end i
s GDC

Key Concepts cont Key Concepts cont
s

Linear search example
template class InputItr class T InputItr find InputItr bg InputItr end const T val while bg end bg val while bg bg return bg return const int nSize 4 int Gromit nSize 5 18 23 9 int pFind find Gromit Gromit nSize 23 int find vector int Preston vector int iterator i vector int iterator find Preston begin Preston end 4 find

GDC

Putting the STL into Action Putting the STL into Action
Include files have no h s Standard namespace
s
include cstdio include vector include algorithm using namespace std new include method vector container STL algorithms assume std

vector int Chuck declare a growable array Chuck push back 1 add an element find Chuck begin Chuck end 1

GDC

Containers Containers
Containers contain elements they own the objects s Containers provide iterators that point to its elements s Containers provide a minimal set of operations for manipulating elements
s

GDC

Containers cont Containers cont
Container Description Keys

vector deque list set map multiset multimap

dynamic array dynamic array both ends linked list sorted list of keys sorted list of key and value pairs sorted list of keys sorted list of key and value pairs

no duplicate keys no duplicate keys duplicate keys OK duplicate keys OK

s

Minimum container object requirements
X X X const X X const X operator X bool operator bool bool operator bool const X const X const X default ctor copy ctor assignment op comparison op comparison op

GDC

Vector Vector
Dynamic array s Fast ins erase from end of vector s reserve capacity s Contiguous block of memory s Obliged to grow by some factor 2x when size exceeds capacity s Insert invals all iters if capacity change insert erase invals all iters following
s GDC

Deque Deque
Double ended queue deck s Fast ins erase at begin and end s Directory array of pointers to nodes where each node is small array of T s Insert invals all iters erase in middle invals all erase at begin end on invals iter to begin end
s

GDC

List List
Doubly linked list s Fast insert erase no random access s Special functions splice merge s Erase invals iters to erased elements insert never invals any iters
s

GDC

Set Set
List of sorted elements s Fast retrieval based on key log N s Fast insert erase log N s Red black tree balanced 2 3 4 tree s Erase invals erased elems insert never invals any iters
s

GDC

Map Map
Dictionary of sorted elements s List of sorted key and value pairs s Same implementation and characteristics of set container
s

GDC

Container Adaptors Container Adaptors
Adaptor Example containers Default container

stack list deque vector queue list deque priority queue list deque vector

deque deque vector

s

Example adapator code
stack int deque int TechnoTrousers TechnoTrousers push 1 int i TechnoTrousers top TechnoTrousers pop

GDC

What s Missing What s Missing
stack based arrays T a N s hash tables s singly linked lists s some STL implementations include one or more of these non standard containers
s

GDC

Container Efficiency Container Efficiency
Container list deque vector set multiset map multimap stack queue priority queue slist SGI hashset SGI hashmap SGI Overhead 8 12 0 12 12 16 16 n a n a n a 4 Insert C C at begin or end else N 2 C at end else N log N log N log N log N C C log N C C N C N Erase C C at begin or end else N C at end else N log N d log N d log N d log N d C C log N C C N C N n a C C n a n a log N log N n a n a n a n a n a n a Find N N N log N log N log N log N n a n a n a N C N C N Sort N log N N log N N log N C C C C n a n a n a n a n a n a

s s

Overhead is approx per element size in bytes Hash and slist containers included for comparison only C N indicates best worst case times

GDC

Other C containers Other C containers
s

string

s

valarray bitset

similar to vector char but includes string specific functions similar to vector T where T is numeric but optimized for numeric ops similar to vector bool but fixed size and includes bit operators

s

GDC

Iterators Iterators
Type Input Output Forward Bidirectional Random Valid expressions t i i i x t x t x x i i x t i i i i x t Bidrect l i n i n i n i n i n i n t Example find read only insert iterator C write only slist T iterator SGI specific list T iterator vector T iterator deque T iterator

s

Typical iteration
c T iterator i for i c begin i c end i forward for T t i i for i c rbegin i c rend i backward for T t i i

GDC

Algorithms Algorithms
s

Approx 60 standard algorithms
searching e g find sorting e g sort mutating e g transform numerical e g accumulate fn c begin c end

s

Most functions take the form

GDC

Algorithms cont Algorithms cont
s

Examples
include algorithm return num elements equal to 123 int i count c begin c end 123 int count negate all elements transform c begin c end negate int print all elements for each c begin c end print int shuffle the deck random shuffle deck begin deck end

GDC

Function Objects Functors Function Objects Functors
C objects that can be called like a function to implement callbacks s Use C operator s Simplest type is a function pointer
s
bool StlStrComp const char a const char b bool StlStrComp return strcmp a b 1 return vector char v sort v begin v end StlStrComp sort v begin StlStrComp

GDC

Functors cont Functors cont
s

Functors that do ordering are called predicates
struct StlStrPred public class struct bool operator const char a const char b return strcmp a b 1 return vector char v sort v begin v end StlStrPred sort v begin StlStrPred

GDC

Efficiency Efficiency
Designed to be as fast as hand coded routines s Limiting factor is typically copy ctor and assignment operator
s

GDC

Efficiency cont Efficiency cont
s

STL faster in some cases than standard C functions

const char WestWallaby Gromit strchr WestWallaby m find WestWallaby WestWallaby 6 m

GDC

Efficiency cont Efficiency cont
s

Sorting ints

int arr nElements qsort arr nElements sizeof int IntComp int arr nElements sort arr arr nElements STL int array sort vector int v sort v begin v end STL int vector sort

GDC

Efficiency cont Efficiency cont
Sorting strings
s
char arr nElements qsort arr nElements sizeof char StrComp sort arr arr nElements StlStrComp sort v begin v end StlStrComp char sort v begin v end StlStrComp string

GDC

STL Allocators STL Allocators
s

Every STL container takes an allocator object as a template parameter
template class T public AllocSpecialCheese public pointer allocate size type const void pointer void deallocate void size type other boilerplate code here set int Camembert default allocator set int All Wensleydale allocations use special allocator set int AllocSpecialCheese Wensleydale

GDC

Template Partial Template Partial Specialization
generic template function for swapping objects template class T void swap T x T y T z x x y y z z x swap v1 v2 swapping vectors slow swap v1 v1 swap v2 swapping vectors fast v1 swap v2 template partial specialization template class T void swap vector T x vector T y vector T x swap y x swap y swap v1 v2 fast swap v1

GDC

Template Specialization part II Template Specialization part II
STL generic copy algorithm template class InItr class OutItr OutItr copy InItr bg InItr end OutItr val for bg end val bg val bg return val A fast version for simple memory chunks template char copy const char bg const char end char val size t n end bg memcpy val bg n return val n

GDC

Thread Safety Thread Safety
Official answer STL has no thread safety obligations whatsoever s One bad answer have STL handle all synchronization issues s Typical answer make STL thread safe internally but require users to insure no thread accesses a container when another thread modifies the container
s GDC

Thread Safety cont Thread Safety cont
s

Current status of implementations


s

Typical STL implementation promises

Original HP version not thread safe SGI thread safe VC mostly thread safe dinkumware com vc fixes html

Multiple reads is thread safe Read write across different containers same objects is thread safe Writes to a container by one thread and read writes by another thread is not thread safe users must prevent

GDC

Exception Safety Exception Safety
s

C standard requires the following

destructors may not throw excptns valid iterator operations may not throw containers must survive excptns content unspecified but still destructable an excptn thrown while inserting one element leaves the container unchanged an excptn thrown while inserting two elements leaves a list unchanged

GDC

Code Bloat Code Bloat
Templates expand into different sets of code for each type T s If different types have the same size and same comparison functions the compiler can optimize s Some STL implementations are optimized to minimize code bloat XTL from DeltaLogic
s GDC

Compiler Warnings Errors Compiler Warnings Errors
s

VC warning C4786 identifier truncation
pragma warning disable 4786 before headers pragma

s

Errors warnings in header files

really means your code has a problem

s

Interpreting gonzo error messages
map string map string m erase i m erase i int m int const iterator i m find abc big error here

GDC

Compiler Errors cont Compiler Errors cont
error class std Tree class std basic string char struct std char traits char class std allocator char struct std pair class std basic string char struct std char traits char class std allocator char const int struct std map class std basic string char struct std char traits char class std allocator char int struct std less class std basic string char struct std char traits char class std allocator char class std allocator int Kfn struct std less class std basic string char struct std char traits char class std allocator char class std allocator int iterator thiscall std map class std basic string char struct std char traits char class std allocator char int struct std less class std basic string char struct std char traits char class std allocator char class std allocator int class std Tree class std basic string char struct std char traits char class std allocator char struct std pair class std basic string char struct std char traits char class std allocator char const int struct std map class std basic string char struct std char traits char class std allocator char int struct std less class std basic string char struct std char traits char class std allocator char class std allocator int Kfn struct std less class std basic string char struct std char traits char class std allocator char class std allocator int iterator class std Tree class std basic string char struct std char traits char class std allocator char struct std pair class std basic string char struct std char traits char class std allocator char const int struct std map class std basic string char struct std char traits char class std allocator char int struct std less class std basic string char struct std char traits char class std allocator char class std allocator int Kfn struct std less class std basic string char struct std char traits char class std allocator char class std allocator int class std Tree class std basic string char struct std char traits char class std allocator char struct std pair class std basic string char struct std char traits char class std allocator char const int struct std map class std basic string char struct std char traits char class std allocator char int struct std less class std basic string char struct std char traits char class std allocator char class std allocator int Kfn struct std less class std basic string char struct std char traits char class std allocator char class std allocator int

C2664

erase

cannot convert parameter 1 from

const iterator to

iterator

No constructor could take the source type or constructor overload resolution was ambiguous

GDC

Extending the STL Extending the STL
Designed for extension s Not difficult to write new algorithms containers or iterators s SGI implementation has many useful container extensions hash tables slist
s

GDC

Our own Algorithm Our own Algorithm
Compute sum of all squares in range template class InItr class T T sumsqrs InItr bg InItr end T init T ss init for bg end bg ss bg bg return ss int CloseShave 4 1 2 3 4 int x sumsqrs CloseShave CloseShave 4 0 30 deque double WrongTrousers 1 1 2 2 3 3 double y sumsqrs WrongTrousers begin 16 94 WrongTrousers end 0 0

GDC

Our own Iterator Our own Iterator
template class C class T class A allocator T struct MfcIt public Ranit T A difference type C mpC MFC container int mI index into container MfcIt C pC 0 mpC pC mI 0 MfcIt C pC int n mpC pC mI n MfcIt begin return MfcIt mpC 0 MfcIt end return MfcIt mpC mpC GetSize T operator const return mpC mI MfcIt operator if mI mpC GetSize mI else mI 0 return this MfcIt operator difference type n const MfcIt tmp this return tmp n bool operator const MfcIt i const return mI i mI mpC i mpC bool operator const MfcIt i const return mI i mI mpC i mpC

GDC

Our own Iterator cont Our own Iterator cont
s

Example of using the MFC STL iterator
MFC container CStringArray arr arr Add xyz arr Add abc Create STL iterator from MFC container MfcIt CStringArray CString mfc arr Sort the MFC container using an STL algorithm sort mfc begin mfc end

GDC

Common Mistakes Common Mistakes
s

Template of templates
stack vector int GoneWrong need space

s

Same algorithm different container
sort Marmalade begin Jelly end crash

s

Right iterator wrong container
list int iterator i Feathers begin McGraw erase i i doesn t point into McGraw

GDC

Common Mistakes cont Common Mistakes cont
s

Invalid iterator
vector int iterator i GrandDayOut begin GrandDayOut push back 1 potential realloc TheCooker i uh oh i might be invalid

s

Adding elements with subscript op
vector char Wendolene Wendolene 0 W crash Wendolene push back W the right way

GDC

Common Mistakes cont Common Mistakes cont
s

Sorting problems

Usually a problem with op or op s Rules
s

e g lookups fail a set gets duplicates

if x y is true y x is always false if x y y z are true x z is always false if x y then x y is always false if x y and y x x y

GDC

Hiding the Angle Brackets Hiding the Angle Brackets
s

Not pretty
This is hard to read map string int Shaun Shaun insert pair string int abc 31 map string int iterator i Shaun find abc pair string int pr i pr first abc pr second int

GDC

Hiding the Angle Brackets cont Hiding the Angle Brackets cont
s

Typedefs are your friend
Tuck typedef typedef typedef these away in a header file map string int ShaunMap pair string int ShaunPair ShaunMap iterator ShaunItr

Same code but no more angle brackets ShaunMap Shaun Shaun insert ShaunPair abc 31 ShaunItr i Shaun find abc ShaunPair pr i

GDC

Storing Pointers in Containers Storing Pointers in Containers
Container will not delete the pointers when the container goes away s Will sort on pointer not what it contains unless you tell it otherwise
s
deque int Walkies sorted by pointer sort Walkies begin Walkies end bool intpLess const int a const int j return a b sorted by int sort Walkies begin Walkies end intpLess

GDC

Vector Tips Vector Tips
Use reserve to set aside space when vector size is known in advance s Can I safely take the address of a vector element e g v 21
s

s

Trimming unused space

According to Standard no According to practice yes Standard expected to adjust

v swap vector T v vector swap thyself

GDC

Checking for Empty Container Checking for Empty Container
Write if c empty instead of if c size 0 s empty is guaranteed constant time s size is not guaranteed constant time it usually is but not always e g lists
s

GDC

Copying Containers Copying Containers
s

The wrong way copy can t add elems
copy v begin v end nv begin uh oh

s

Better and best
nv resize v size size of nv matches v copy v begin v end nv begin copy v begin v end back inserter nv copy m begin m end insert iterator T map and set use this method nm nm begin

GDC

Algorithms that Remove Algorithms that Remove Elems
Algorithms by themselves can t insert or delete elements so they move them s unique moves unique elems to the front and returns an iter to the new end of the container s remove similarly moves the unremoved elems to the front and returns an iter to the new end
s GDC

Removing Elems cont Removing Elems cont
s

To actually get rid of the extra elems you must call erase
Removes duplicates and shrinks the container v erase unique v begin v end v end Removes the given elements and shrinks v v erase remove v begin v end 1 v end

GDC

Iterator Troubleshooting Iterator Troubleshooting
Iter dereferenceable end is not s Container invalidated the iter s Pair of iters a valid range First really before last s Iter pointing to the right container s Pair of iters pointing to the same container
s GDC

Vectors vs C style arrays Vectors vs C style arrays
Prefer vector or deque over arrays s Don t have to know size in advance s Don t have to keep track of size separately s Little loss of efficiency s Vector works well with legacy code that expect arrays
s GDC

Deque vs Vector Deque vs Vector
Almost identical usability characteristics s Faster middle insertion because deque only needs to shift a chunk s Constant time insertion at the front s Uses memory in a more operating system friendly way s Don t need to worry about reserve
s GDC

Vector bool Vector bool
Standard says vector bool stores boolean values as bits for space optimization s Technically not a container can t be used reliably with generic algorithms s Prefer deque bool or vector char unless space benefits outweigh
s

GDC

The Key Requirement The Key Requirement
Once a key has been inserted into a container the key should not change s Can t be enforced internally by the STL s Example key is a filename comparison is based on file contents
s

GDC

Copy vs Memcpy Copy vs Memcpy
copy works reliably with all objects s memcpy unsafe on any object with a copy ctor s copy can copy a sequence whose length is not known in advance s copy returns an iter to the end of the copy can be used as concatenation tool s good implementation will optimize
s GDC

Wrap Up Wrap Up
Algorithms Containers Iterators s Efficient Flexible Extensible s Angle Brackets mmm
s

GDC

References References
Email me PKIsensee msn com s Home page www tantalon com s Books Generic Programming the STL Austern STL Tutorial Reference Guid Musser s Websites sgi com Technology STL dinkumware com deltalogic com roguewave com stlport org
s GDC