An Introduction to STL -

Standard Template Library

Jiang Hu
Department of Electrical Engineering
Texas A&M University

1
What Is STL?
C++ based implementations of general
purpose data structures and algorithms

2
When Do You Need STL?
Reduce your C/C++ programming time
Use data structures and algorithms from STL directly,
instead of implementing everything from scratch
Easier maintenance
Bugs in bottom structures are the most difficult to find
Use STL as building blocks, they are robust
Program runtime is not very critical
General purpose implementations may run a little
slower than customized implementations

3
Assumption
You know basics of
C++
Data structures such as link list, hash table,
binary search tree …
Algorithms such as sorting …

4
Bottom Line: Understand class
class is
An essential concept for C++
What STL is built on
An abstract form
• Has member variables to record data
• Has member functions to do something
• Members can be open to public or encapsulated to
be private

5
Example of class
class
classnode
node{{ node::node(long
node::node(longid)id)::x(0),
x(0),
private: y(0),
y(0),ID(id),
ID(id),parent(NULL)
parent(NULL){}
{}
private:
long
longx,x,y,
y,ID;
ID;
double long
longnode::getID()
doublerat,
rat,cap;
cap; node::getID()
node* {{ return
returnID;
ID;}}
node*parent;
parent;

public: main()
main()
public:
node(long {{
node(longid);
id);
void node
nodemyNode(1);
voidsetCoordinates(
setCoordinates(long,
long, myNode(1);
long
long);); myNode.setCoordinates(5,8);
myNode.setCoordinates(5,8);
long
longgetID();
getID(); long
longpp==myNode.getID();
myNode.getID();
};
}; }}

6
STL Containers
Sequence containers
vector
deque
list
Sorted associative containers
set
multiset
map
multimap
7
STL list
list is a list
Functionally, similar to double-linked list
Supports
Insertion
Deletion
Sorting
……

8
Example of list
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>nodeList;
nodeList;
……… …
nodeList.push_back(
nodeList.push_back(node(1)
node(1));); ////node1
node1isisadded
addedatatend
end
nodeList.push_front(
nodeList.push_front(node(0)
node(0));); ////node0
node0isisadded
addedat atfront
front
nodeList.pop_back();
nodeList.pop_back(); ////remove
removethe theelement
elementat atend
end
nodeList.pop_front();
nodeList.pop_front(); ////remove
removethe theelement
elementat atfront
front
……… …
}}

9
STL iterator
begin()

list end()
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>nodeList;
nodeList;
list<node>::iterator
list<node>::iteratorj;j; ////Generalized
Generalizedpointer
pointer
……… …
for
for((jj==nodeList.begin();
nodeList.begin();jj!=
!=nodeList.end();
nodeList.end();j++
j++)){{
ifif(((*j).getID()
(*j).getID()>>33))break;
break;
}}
……… …
}}
10
 insert(), erase() and remove()
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>nodeList;
nodeList;
list<node>::iterator
list<node>::iteratorj;j; ////Generalized
Generalizedpointer
pointer
……… …
for
for((jj==nodeList.begin();
nodeList.begin();jj!=
!=nodeList.end();
nodeList.end();j++
j++)){{
ifif(((*j).getID()
(*j).getID()>>33))nodeList.insert(
nodeList.insert(j,j,node(2)
node(2)););
ifif(((*j).getID()
(*j).getID()<<00))nodeList.erase(
nodeList.erase(jj);); ////problem??
problem??
}}
nodeList.remove(
nodeList.remove(nodeA nodeA);); ////operator==
operator==defined
definedfor
fornode
node
……… …
}}
11
 Careful erase in a loop
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>nodeList;
nodeList;
list<node>::iterator
list<node>::iteratorj,j,k; k;
……… …
jj==nodeList.begin();
nodeList.begin();
while
while(( jj!= !=nodeList.end()
nodeList.end())){{
kk==j++;j++;
ifif(((*k).getID()
(*k).getID()<<00)){{
nodeList.erase(
nodeList.erase(kk););
}}
}}
……… …
}}
12
front() and back()
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>nodeList;
nodeList;
……… …
node
nodeAA==nodeList.front();
nodeList.front(); ////copy
copythe
thefirst
firstnode
nodeininthe
thelist
list
node
nodeB(B(nodeList.back()
nodeList.back());); ////construct
constructaanode
nodeBBsame
sameas as
////the
thelast
lastnode
nodeininthe
thelist
list
……… …
}}

13
size(), sort() and merge()
#include<list.h>
#include <list.h>
void
voiddoSomething()
doSomething()
{{
list<node>
list<node>listA,
listA,listB;
listB;
……… …
int
intnumNodes
numNodes==listA.size();
listA.size(); ////number
numberof ofelements
elementsininlist
list
listA.sort();
listA.sort(); ////operator<
operator<isisdefined
definedfor
fornode
node
listB.sort();
listB.sort();
listA.merge(
listA.merge(listB
listB);); ////both
bothlists
listsshould
shouldbe
besorted
sorted
////listB
listBbecomes
becomesempty
emptyafter
aftermerge
merge
……… …
}}

14
STL vector
Functionality-wise, roughly a subset of list
No push_front(), pop_front(), remove(),
sort(), merge()
Supports operator [], such as vectorA[3]
Then why need vector ?
Faster access if the data are mostly static or
not much insertion/deletion

15
STL deque
Very similar to vector, except
Supports push_front() and pop_front()
No operator []
Also friendly to accessing static data

16
vector vs. array in C/C++
Dynamic memory management for vector
Certain size of memory is allocated when a
vector is constructed
When add a new element and the memory
space is insufficient, multiple-sized new
memory is allocated automatically

17
Use reserve() if possible
If you have a rough idea of the size of the vector,
use reserve() to allocate sufficient memory space
at the beginning
Dynamic memory allocation is nice, but it costs you
runtime, the related copying also takes time
Ex., you will work on a routing tree for a net with k
sinks, then:
vector<node> nodeVec;
const int a = 2;
nodeVec.reserve( a*k );

18
Sequence Container Summary
Contiguous-memory based:
vector, constant time addition and deletion at end
deque, constant time addition and deletion at
beginning and end
Constant time access
Linear time insertion/deletion in middle
Node based – list
Linear time access
Constant time insertion/deletion any position

19
Sorted Associative Containers
set<key> : a set of sorted key which can
be any data type with operator< defined
multiset<key> : allow duplicative keys
map<key, T> : T is a certain data type,
the data are always sorted according to their
keys
multimap<key, T> : allow duplicative
keys
Internally, implemented via red-black tree
20
STL map
#include<map.h>
#include <map.h>
void
voiddoSomething()
doSomething()
{{
map<string,
map<string,double,
double,less<string>
less<string>>>tempMap;
tempMap;
tempMap[
tempMap[“Austin”
“Austin”]]==93.2;
93.2; ////[][]can
canbebeemployed
employedto toinsert
insert
tempMap.insert(
tempMap.insert(pair<string,double>(
pair<string,double>(“Chicago”,
“Chicago”,84.6
84.6))););
tempMap[
tempMap[“Chicago”
“Chicago”]]==86.8;
86.8; ////[][]isisbetter
betterfor
forupdate
update
map<string,
map<string,double,
double,less<string>
less<string>>::iterator
>::iteratork;k;

for
for((kk==tempMap.begin();
tempMap.begin();kk!= !=tempMap.end();
tempMap.end();k++
k++)){{
ifif(((*k).first
(*k).first==
==“Austin”
“Austin”))(*k).second
(*k).second==97.4;
97.4;
}}
kk==tempMap.find(
tempMap.find(“Austin”
“Austin”););
ifif((kk!= !=tempMap.end()
tempMap.end()))(*k).second
(*k).second==95.3;
95.3;
}}
21
Data Insertion to STL Containers
== Copy
list::push_back(objA)
map::insert(objB)
What actually saved in containers are
copies, not original object
Thus, each insertion incurs an object
copying procedure
If a data type is too complex, sometimes it
is better to save the pointers to the objects

22
empty() vs. size() == 0
Two methods to check if a container is
empty
empty(), takes constant time
Check if size() == 0, may take linear time!

23
Container Adaptors
stack
stack< vector<T> >
stack< list<T> >
queue
queue< deque<T> >
priority_queue
priority_queue< vector<int>, less<int> >

24
STL Algorithms
Many generic algorithms
for_each()
find()
count(), count_if()
copy(), swap(), replace(), remove(), merge()
sort(), nth_element()
min(), max()
partition()
……

25
Algorithm Example remove()
#include<vector.h>
#include<vector.h>
#include<algorithm.h>
#include<algorithm.h>
……… …
vector<int>
vector<int>v; v;
v.reserve(10);
v.reserve(10);
for
for((int
intjj==1;
1;jj<=
<=10;
10;j++
j++)){{
v.push_back(j);
v.push_back(j);
}}
cout
cout<<<<v.size();
v.size(); ////print
print10
10
v[3]
v[3]==v[5]
v[5]==v[9]
v[9]==99;
99;
remove(
remove(v.begin(),
v.begin(),v.end(),
v.end(),99 99);); ////remove
removeall
allelement
element==
==99
99
cout
cout<<<<v.size();
v.size(); ////still
stillprint
print10!
10!

26
The Myth of remove()
At beginning

1 2 3 4 5 6 7 8 9 10

After change data

1 2 3 99 5 99 7 8 9 99

v.end()
After remove()

1 2 3 5 7 8 9 8 9 99

remove() returns an iterator

27
Make remove() More Meaningful
#include<vector.h>
#include<vector.h>
#include<algorithm.h>
#include<algorithm.h>
……… …
vector<int>
vector<int>v; v;
v.reserve(10);
v.reserve(10);
for
for((int
intjj==1;
1;jj<=
<=10;
10;j++j++)){{
v.push_back(j);
v.push_back(j);
}}
cout
cout<<<<v.size();
v.size(); ////print
print10
10
v[3]
v[3]==v[5]
v[5]==v[9]
v[9]==99;
99;
v.erase(
v.erase(remove(
remove(v.begin(),
v.begin(),v.end(),
v.end(),9999),),v.end()
v.end()););
cout
cout<<<<v.size();
v.size(); ////now
nowprint
print7!
7!

28
What Else for STL?
Many other features
Internal implementation
Suggestion:
Buy an STL book
Use it as a dictionary

29
Something About C++
A nice book
Effective C++, Scott Meyers, Addison-Wesley,
1998

30
Data Organization in Declaring
Class
class
classnode
node{{ class
classnode
node{{
private:
private: private:
private:
double
doublerat;
rat; long
longx,
x,y,y,ID;
ID;
long
longx,x,y;
y; double
doublerat,
rat,cap;
cap;
double
doublecap;
cap; node*
node*parent;
parent;
long
longID;
ID; ……… …
node*
node*parent;
parent; };
};
……… …
};
}; ////Put
Putmember
membervariables
variablesofof
////same
sametype
typetogether,
together,this
this
////improves
improvesmemory
memoryefficiency
efficiency

31
Prefer Initialization to
Assignment in Constructors
class
classnode
node{{ node::node(
node::node(int
intj,j,long
longa,
a,long
longb)
b)::ID(j),
ID(j),
private: x(a),
x(a),y(b)
y(b){{}}
private:
const
constint
intID;
ID;
long node::node(
node::node(int
intj,j,long
longa,
a,long
longb)
b)::ID(j)
ID(j){{
longx,x,y;
y;
node* xx==a;
node*parent;
parent; a;
yy==b;
b;
};
}; }}

• const or reference member variables have to be initialized

• Initialization is always performed (to certain default
value), even you do the assignment later
• List members in an initialization list in the same order in
which they are declared 32
Inline Function
class
classnode
node{{ class
classnode
node{{
……… … ……… …
long
longgetID();
getID(); inline
inlinelong
longgetID()
getID(){{
};
}; return
returnID;
ID;}}
};
};
long
longnode::getID()
node::getID()
{{ return
returnID;
ID;}}

Inline function usually runs faster

But, compiling time may be longer

33
Minimize Compiling
Dependencies
////This
Thisisisfile
fileA.h,
A.h,class
classtypeB
typeBisis ////This
Thisisisfile
fileA.h,
A.h,class
classtypeB
typeBisis
////declared
declaredininfile
fileB.h
B.h ////declared
declaredininfile
fileB.h
B.h
#include
#include<B.h> <B.h>
class
classtypeA
typeA{{ class
classtypeB;
typeB;
… …… … class
classtypeA
typeA{{
typeB*
typeB*memberB;
memberB; ……… …
inline
inlinevoid
voiddo()
do(){{ typeB*
typeB*memberB;
memberB;
memberB->doSome();
memberB->doSome(); void
voiddo();
do();
}} };
};
};};
////Change
Changeof ofA.h
A.hinvolves
involvesB.hB.h
////thus,
thus,compiling
compilingtimetimeisislong
long

34
Prefer Pass-by-Reference to
Pass-by-Value
class
classtree
tree{{ class
classnode
node{{
……… … ……… …
node
noderoot;
root; node
noderoot;
root;
node
nodegetRoot();
getRoot(); node&
node&getRoot();
getRoot();
};
}; };
};
////For
Foraacomplex
complexdata
datatype
type ////Pass
Passreference
referenceisisfaster
faster
////return
returnvalue
valuetakes
takestime
time ////but,
but,sometimes
sometimesyou youhave
haveto
to
////on
oncopying
copying ////pass
passvalue
value

35
Never Return Reference to Local
Variable
node&
node&someClass::doSomething()
someClass::doSomething()
{{
……… …
node
nodelocalNode;
localNode;
……… …
return
returnlocalNode;
localNode; ////This
Thiscauses
causestrouble!
trouble!
////Since
Sincethe
thelocal
localvariable
variableisisdiscarded
discarded
////at
atthe
theexit
exitof
ofthe
thefunction
function
}}

36