《软件设计（II）教学课件：Chapter 14 Introduction to theStandard Template Library》由会员分享，可在线阅读，更多相关《软件设计（II）教学课件：Chapter 14 Introduction to theStandard Template Library（31页珍藏版）》请在金锄头文库上搜索。
1、Chapter 14 Introduction to the Standard Template Library14.1 Introduction14.2 Containers14.3 Iterators14.4 Algorithms14.5 Function Objects14.1 IntroductionStandard Template Library (STL) 标准模板库lA software library included in the C+ Standard LibraryPurposelTo standardize commonly used componentsHistor
2、ylOriginally developed by Alexander Stepanov in 1980slAccepted as part of C+ standard in Feb. 19942Components of STLContainers（容器）（容器）lA container object, such as vector, used to store a collection of data, often referred to as elementsAlgorithms（算法）（算法）lFunctions to manipulate data such as sorting,
3、 searching, and comparing elements. lMost of them use iterators to access the elements in the container.Iterators（迭代器）（迭代器）lObjects that facilitate traversing through the elements in a containerlLike built-in pointers that provide a convenient way to access and manipulate the elements in a container
4、3Components of STL4Algorithm 3Algorithm 2Algorithm 1ContainerObject1Object2Object3Iterator3Iterator2Iterator114.2 Containers5ContainersvectordequelistSequence containerssetmultisetmapmultimapAssociative containersstackqueuepriority_queueDerived containerslinear data structuresNon-linear (tree) conta
5、iners Suitable for searchingConstrained versions of sequence containersSequence ContainersRepresent linear data structures Three sequence containerslvector 向量, list 表, and deque 双端队列Differ only in performance6Element 0iteratorBegin()end()Element 1Element 2Last Elementint values = 1, 2, 3, 4 ; list i
6、ntList(values, values + 4); Sequence Containers7ContainerRandom accessInsertion or deletion in the middleInsertion or deletion at the endsvectorFastSlowFast at backlistSlowFastFast at frontdequeFastSlowFast at both the endsAssociative ContainersRepresent non-linear data structures (tree)Elements are
7、 sorted by keyslE.g. the name of student objectsSuitable for searching via keysSet/Multiset: set of itemsMap/Multimap: set of item pairs8int values = 3, 5, 1, 7, 2, 2; set set1(values, values + 6); map map1; map1.insert(map:value_type(100, John Smith); Derived ContainersContainers adapted from the s
8、equence containerslFor handling special casesProgrammer can choose an appropriate sequence container for a derived containers9HeaderfileFeaturesImpl. struct.stackLast-In-First-Outdeque*, list, vector queueFirst-In-First-Outdeque*, listpriority_queueLargest-In-First-Outvector*, deque *:defaultonestac
9、kint, vector stack2; Containers supported by the STLContainerDescriptionHeader FileIteratorvectorAdynamicarray.Allowsinsertionsanddeletionatback.PermitsdirectaccesstoanyelementRandomaccesslistAbidirectional,linearlist.Allowsinsertionsanddeletionsanywhere.BidirectionaldequeAdouble-endedqueue.Allowsin
10、sertionsanddeletionsatboththeends.Permitsdirectaccesstoanyelement.RandomaccesssetAnassociatecontainerforstoringuniquesets.Allowsrapidlookup.(Noduplicatesallowed)BidirectionalmultisetAnassociatecontainerforsortingnon-uniquesets.(Duplicatesallowed)Bidirectional10Containers supported by the STLContaine
11、rDescriptionHeader FileIteratormapAnassociatecontainerforstoringuniquekey/valuepairs.Eachkeyisassociatedwithonlyonevalue(One-to-onemapping).Allowskey-basedlookup.BidirectionalmultimapAnassociatecontainerforstoringkey/valuepairswithonekeymaybeassociatedwithmorethanonevalue(one-to-manymapping).Allowsk
12、ey-basedlookup.BidirectionalstackAstandardstack.Last-in-first-out(LIFO).NoiteratorqueueAstandardqueue.First-in-first-out(FIFO).Noiteratorpriority-queueApriorityqueue.Thefirstelementoutisalwaysthehighestpriorityelement.Noiterator11Common Functions in All Containers12Common Functions in Sequence/Assoc
13、iative Containers13Common Functions in Sequence Container14Common Functions in Associative Containers 1514.3 IteratorsIterators are objects to facilitate traversing through the elements in a containerA iterator is like a built-in pointer that can manipulate the elements in a container16random access
14、bidirectionalforwardinputoutputIterators and CharacteristicsIteratorAccess methodDirection of movementI/O capabilityRemarkInputLinearForward onlyRead onlyCannot be savedOutputLinearForward onlyWrite onlyCannot be savedForwardLinearForward onlyRead/WriteCan be savedBidirectionalLinearForward and back
15、wardRead/WriteCan be savedRandomRandomForward and backwardRead/WriteCan be saved17Iterator OperationsIteratorElement accessReadWriteIncrement operationComparisonInput-V=*p+=,!=OutputV=*p*p=v+=,!=Forward-V=*p*p=v+=,!=Bidirectional-V=*p*p=v+,-=,!=Random-,V=*p*p=v+, -, _, -, +=, -=,!=,=18Iterator Types
16、 Supported by Containers19Iterator Demo20 vector intVector; intVector.push_back(10); intVector.push_back(20); intVector.push_back(30); intVector.push_back(40); intVector.push_back(50); intVector.push_back(60); vector:iterator p1 = intVector.begin(); for (; p1 != intVector.end(); p1+) cout *p1 ; cout
17、 endl *(-p1) endl; cout *(p1 - 3) endl; cout p1-3 endl; *p1 = 1234; cout *p1 endl;IteratorDemo14.4 AlgorithmsMore than sixty algorithms in STL Five groupslRetrieve or non-mutating AlgorithmslMutating AlgorithmslSorting AlgorithmslSet AlgorithmslRelational Algorithms21The copy Algorithm22templatecopy
18、(InputIteratorbeg,InputIteratorend,OutputIteratortargetPostition)intvalues=1,2,3,4,5,6;vectorintVector(5);listintList(5);copy(values+2,values+4,intVector.begin();copy(values,values+5,intList.begin();#include#include#include#includeCopy to Output Stream23intVector.insert(intVector.begin(),747);ostrea
19、m_iteratoroutput(cout,);coutnAftertheinsertionfunciton,intVector:;copy(intVector.begin(),intVector.end(),output);The copy Demo24AfterinitialcopyintVector:34000AfterinitialcopyintList:12345Aftertheinsertionfunction,intVector:74734000Afterthecopyfunction,intList:7473405intvalues=1,2,3,4,5,6;vectorintV
20、ector(5);listintList(5);copy(values+2,values+4,intVector.begin();copy(values,values+5,intList.begin();intVector.insert(intVector.begin(),747);copy(intVector.begin(),intVector.begin()+4,intList.begin();intvalues=1,2,3,4,5vectorintVector;copy(values+2,values+4,intVector.begin();CautionThe target conta
21、iner in copying must contains enough elements to store the values from the source container25“sort” and “binary_search”26template void sort(RandomAccessIterator beg, RandomAccessIterator end)template void sort(RandomAccessIterator beg, RandomAccessIterator end, relationalOperator op)template bool bi
22、nary_search(ForwardIterator beg, ForwardIterator end, const T &value)template bool binary_search(ForwardIterator beg, ForwardIterator end, const T &value, strickWeakOrdering op)SortDemoDemo of sort, binary_search27int array1 = 1, 7, 3, 4, 3, 3, 1, 2;sort(array1, array1 + 8);binary_search(array1, arr
23、ay1 + 8, 4)sort(array1, array1 + 8, greater_equal();binary_search(array1, array1 + 8, 4, greater_equal()A function operator!14.5 Function ObjectsObject can be used as a functionl“function” “object”Passing a function as a parameterIn header28int main()int x = 10,50,30,40,20;int y = 70,90,60,80;sort(x
24、,x+5,greater();sort(y,y+4);for (int i=0;i5;i+) coutxi ; coutn;for (int j=0;j4;j+) coutyj ; coutn;int z9;merge(x,x+5,y,y+4,z);for (int i=0;i9;i+) coutzi ; coutn;Functors in 29Customized Function ObjectsBy defining member function operator() in a class30classMypublic:intoperator()(inta)returna;Mymo;in
25、tx=mo(0);templateclassgreater:binary_functionpublic:booloperator()(constT&x,constT&y)constreturnxy;class BiggerThanpublic: const int testValue; BiggerThan(int x) : testValue(x) bool operator()(int val) const return val testValue; ;int my = 1, 7, 3, 4, 3, 3, 1, 2;sort(my, my + 8, Mygreater();BiggerThan bt(10);coutbt(11) bt(9)endl;My m;coutm(4)endl;104A SummaryConceptslSTL, Container, Iterator, AlgorithmlThree types of containerslFunction, Operation, AlgorithmlFunctional objectFeatures of different containersMain functions of containersFeatures of STL algorithmUse of functional object31
