Kynning á Standard Template Library

Standard Template Library, eða STL, er C++ safn(library) af container klösum, algorithmum, og iterators. STL útvegar okkur marga af grundvallar algorithms and data structures tölvunarfræðinnar. STL er generic safn, sem þýðir að componentar þess eru mjög parameterized: næstum allir componentar í STL eru template. Þú ættir að fullvissa þig um að þú skiljir hvernig templates virka í C++ áður en þú notar STL.
Containers og algorithmar
Eins og mörg klasa söfn libraries, inniheldur STL container klasa: klasar sem hafa þann tilgang að geyma aðra hluti. STL inniheldur klasana vector, list, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map, og hash_multimap. Hver og einn af þessum klösum eru template, og geta verið instantiated til að geyma hvaða tag af hlut sem er. Þú getur, til dæmis, notað vector<int> að mestu á sama hátt og þú myndir nota venjulegt C fylki, nema að vector kemur í veg fyrir að þurfa að meðhöndla dynamic memory allocation handvirkt.
vector<int> v(3); // Yfirlýsum vektor af 3 stökum
v[0] = 7;
v[1] = v[0] + 3;
v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
STL inniheldur einnig stórt safn af algorithmum sem meðhöndla gögnin sem er vistuð í containers. Þú getur snúið við röðinni af stökunum í vektor, til dæmis, með því að nota reverse algorithma.
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
Það er tvennt sem er mikilvægt að taka eftir varðandi þetta kall á reverse. Fyrst, það er global function, ekki member function. Annað, Það þarf tvo argumenta frekar en einn: Þetta vinnur á range af stökum, frekar en á container. Í þessu tilviki vill svo til að range –ið er allt container v.


Ástæðan fyrir báðum þessum staðreyndum: reverse, líkt og aðrir STL algorithmar, er decoupled frá STL container klösunum. Þetta þýðir að reverse getur verið notað, ekki bara til að snúa við stökum í vektor, heldur líka til að snúa við stökum í lista og jafnvel stökum í fylkjum. Eftirfarandi forrit er dæmi.
double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
reverse(A, A + 6);
for (int i = 0; i < 6; ++i)
cout << "A[" << i << "] = " << A;
Þetta dæmi notar range, alveg eins og dæmið að snúa við vector: fyrsti argumentinn til að snúa við er bendir á byrjun range, og næsti argumenti bendir einu staki lengra en endinn á range. Þetta range er denoted [A, A + 6); asymmetrical rithátturinn er áminning á að endapunktarnir tveir eru öðruvísi, að fyrsti er byrjun á range og næsti er einum lengra en endinn á range.
Ítrarar
Í dæminu snúa við C fylki, argumentar til að reverse eru greinilega af taginu double*. Hverjir eru argumentarnir sem þarf að snúa við ef þú ert að snúa við vector, eða lista? Það er, hvað yfirlýsir nákvæmlega reverse sem argumenta sína, og hvað nákvæmlega skila v.begin() og v.end() tilbaka?
Svarið er að argumentarnir til að reverse eru ítrara (iterators), sem er alhæfing fyrir benda. Bendar eru sjálfir ítrarar, sem gerir það kleift að snúa við stökum C fylkis. Líkt, vector yfirlís nested tögin iterator og const_iterator. Í dæminu að ofan, tagið sem skilað var af v.begin() og v.end() er vector<int>::iterator. Það er líka nokkrir ítrarar, eins og istream_iterator og ostream_iterator, sem tengjast ekki containers á neinn hátt.
Ítrarar eru tækið sem gerir það kleift að decouple algorithma frá containerum: algorithmar eru templates, og eru parameterized af tagi ítrara, svo að þeir eru ekki bundnir af eitthverju einu tagi af containter. Hugsaðu, til dæmis, hvernig á að skrifa algorithma sem framkvæmir línulega leit í gegnum bilið(range).
Þetta er STL's find algorithminn.
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}
Find tekur þrjá argumenta: tvo ítrara sem skilgreina bil(range), og gildi til að leita að á þessu bili. Það skoðar hvern ítrara á bilinu [first, last), frá upphafi til enda, og stoppar annað hvort þegar það finnur ítrarann né sem bendir á value eða þegar það nær enda á bildinu.
First og last eru declared að vera af taginu InputIterator, og InputIterator er template parameter. Það er, Það er nefnilega ekkert tag sem kallast InputIterator: þegar þú kallar á find, úthlutar compiler taginu af argumentunum fyrir formlega tag parameters InputIterator og T. Ef fyrstu tveir argumentarnir til find eru af taginu int* og sá þriðji er af taginu int, þá er eins og þú hefðir kallað eftirfarndi fall.
int* find(int* first, int* last, const int& value) {
while (first != last && *first != value) ++first;
return first;
}
Hugtök og Modeling
Ein mjög mikilvæg spurning sem vert er að spyrja um hvaða template fall sem er, ekki bara um STL algorithmana, er hvaða hópur af tögum það er sem má vera rétt úthlutað fyrir formlegu template parameters. Augljóslega, til dæmis, int* eða double* má úthluta fyrir find's formlegu template parameter InputIterator. Jafn augljóslega, , int eða double getur ekki: find notar segðina *first, og dereference operator-inn meikar ekki sens fyrir hlut af taginu int eða af taginu double. Grundvallarsvarið er því, find skilgreinir skýrt mengi af kröfum um tög, og því má stilla instantiated upp með hvaða tagi sem er, sem fullnægir þessum kröfum. Hvaða tag sem kemur í stað InputIterator verður að útvega ákveðnar aðgerðir: það verður að vera mögulegt að bera saman tvo hluti af þessu tagi fyrir hvort þeir séu jafnir, það verður að vera mögulegt að hækka hlut af þessu tagi, það verður að vera mögulegt að dereference hlut af því tagi til að fá þann hlut sem það bendir á, o.s.frv.
Find er ekki eini STL algorithminn sem hefur svona kröfur; argumentar fyrir for_each og count, og aðra algorithma, verða fullnægja sömu kröfum. Þessar kröfur eru sufficiently mikilvægar að við gefum þeim nafn: við köllum slíkt mengi af tag kröfum hugtak (concept), og við köllum þetta tiltekna hugtak Input Ítrari. Við segjum að tag conforms to a concept, eða að það er a model of a hugtaki, ef þetta fullnægir öllum þessum kröfum. Við segjum að int* er model af Input Ítrara af því að int* útvegar að aðgerðir sem eru tilgreindar af Input Ítrara kröfunum.
Hugtök(concepts) eru ekki hluti af C++ málinu; það er engin að leið til að yfirlýsa hugtak í forriti, eða til að yfirlýsa að tiltekið tag er model af hugtaki. Engu að síður eru hugtök mjög mikilvægur hluti af STL. Að nota hugtök gerir það kleitft að skrifa forrit sundurgreinir vel viðmót frá útfærslu(implementation): hönnuður find þarf aðeins að hugsa um viðmótið sem er tiltekið af hugtakinu Input Ítrara, frekar en útfærslu(implementation) af öllum hugsanlegum tögum sem conforms að því hugtaki. Eins, ef þú vilt nota find, þarft þú aðeins að vera viss að argumentar sem þú sendir því eru model af Input Ítrara. Þetta er ástæðan fyrir því af hverju það er hægt að nota find og reverse með lists, vectors, C fylkjum, og mörgum öðrum tögum: forritun með tilliti til hugtaka, frekar en til tilliti til ákveðinna taga, gerir það mögulegt að endurnýta hugbúnaðar componenta og sameina componenta saman.
Refinement
Input Ítrari er, í raun, frekar veikt hugtak: það er, það imposes mjög fáar kröfur. Input Ítrari verður að styðja hlutmengi af benda reikningi (það verður að vera mögulegt að hækka Input Ítrara með að nota prefix og postfix operator++), en verða ekki að styðja allar aðgerðir af benda reikningi. Þetta er fullnægjandi fyrir find, en sumir aðrir algorithmar krefjast að argumentar þeirra fullnægji auka kröfum. Reverse, til dæmis, verður að vera fær um að decrementa argumenta sína sem og incrementa þá: það notar segina –last. Með tilliti til hugtaka, segjum við að arguments reverse's verða að vera models af Bidirectional Ítrara frekar en Input Ítrara.
Bidirectional Ítrari hugtakið er mjög svipað Input Ítrara hugtakinu: það einfaldlega imposes nokkrar auka kröfur. Tögin sem eru models af Bidirectional Ítrara eru hlutmengi af tögunum sem eru model af Input Ítrara: hvert tag sem er model af Bidirectional Ítrara er einnig model af Input Ítrara. Int*, til dæmis, er bæði model af Bidirectional Ítrara og model af Input Ítrara, en istream_iterator, er aðeins model af Input Ítrara: það conform-ar ekki að meiri stringent kröfum Bidirectional Ítrara.
Við lýsum sambandinu á milli Bidirectional Ítrara og Input Ítrara með því að segja að Bidirectional Ítrari er refinement af Input Ítrara.
Refinement hugtaka er mjög keimlíkt erfðum C++ klasa; megin ástæða þess að við notum annað orða, í staðinn að kalla það “erfðir”, er til að leggja áherslu á aðrefinement á við um hugtök frekar en eiginleg tög.
Það eru reyndar þrjú fleiri ítrara hugtök til viðbótar við þau tvö sem ég hef fjallað um. Hugtökin fimm eru Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, og Random Access Iterator; Forward Iterator er refinement af Input Iterator, Bidirectional Iterator er refinement af Forward Iterator, og Random Access Iterator er refinement af Bidirectional Iterator. (Output Iterator er tengdur öðrum fjórum hugtökum, en er ekki hluti af refinement: það er ekki refinement af neinu öðru iterator hugtaki, og ekkert af hinum iterator hugtökunum eru refinements af því.)
Aðrir hlutar af STL
Ef þú skilur algorithma, iterators, og containers, þá skilur þú næstum allt sem hægt er að vita um STL. STL inniheldur, aftur á móti, nokkra aðrar tegundir af componentum.
Í fyrsta lagi, inniheldur STL nokkrar utilities: mjög basic hugtök og föll sem eru notuð í mörgum mismunandi hlutum library-ins. Hugtakið Assignable, til dæmis, lýsa tögum sem hafa assignment virkja og copy constructors; næstum allir STL klasar eru model af Assignable, og næstum allir STL algorithmar krefjast að argumentar þeirra séu model af Assignable.
Í öðru lagi, inniheldur STL nokkra low-level mechanisma til að allocating and deallocating minni. Allocators eru mjög sérhæfðir, og þú getur hunsað þá alveg fyrir næstum hvaða verkefni sem er.


Að lokum inniheldur STL stórt safn af funtion objects, einnig þekkt sem functors. Rétt eins og iterators eru alhæfing af bendum, þá eru function hlutir alhæfing af föllum: function hlutur er hvað sem þú allt sem þú getur kallað á með því að nota venjulega function kalla syntax-ið. Það eru nokkur mismunandi hugtök sem tengjast function objects, þar með talið Unary Function (function hlutur sem tekur einn argumenta, t.d. einn sem er kallaður eins og f(x)) og Binary Function (function hlutur sem tekur tvo argumenta, t.d. einn sem sem kallaður eins og f(x, y)). Function hlutir eru mikilvægur hluti af generic forritun af því að þeir leyfa abstraction ekki bara yfir hlutum, heldur líka yfir aðgerðunum sem verið er að framkvæma.