An introduction to STL

of 4
12 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
see www.joyofprogramming.com
Document Share
Document Tags
Document Transcript
  78 MAY 2007 | LINUX FOR YOU |  www.linuxforu.com verv ew   tandard Template Library (STL) isa powerful template library forC++, which is used extensively inthe industry. It provides generic,fundamental data structures andalgorithms useful for most of the programs. So,it avoids reinventing the wheel and providescode that is well tested, versatile, efficient andgeneric. For example, if you want to write asymbol table for your toy compiler, you can goahead and write your own symbol table.However, this approach suffers from severaldisadvantages:  The effort required to write a full-fledged,effective and efficient symbol table issubstantial.  The hand-written code needs to undergorigorous testing (since the symbol table is a very important piece of a compiler). Findingand fixing problems can take significantamounts of time and energy.  The data structure needs to be efficient andeffective: achieving this is not easy.  If some other programmers are assigned tomaintain or extend your symbol table in thefuture, they will find it very difficult to S A ReadyReckoner for the Learn about the many benefits of the Standard TemplateLibrary in this introductory article. Overview StandardTemplateLibrary 78 MAY 2007 | LINUX FOR YOU |  www.linuxforu.com understand both the interface andimplementation of your symbol table: only you know your program well, as it is non-standard.Instead, when you use STL forimplementing your symbol table, you can makeuse of a map (or a multi-map) container; use various generic algorithms (binary_search, sortetc) to operate on it; and make use of iteratorsto traverse the table as required. To be specific:  You need not write a full-fledgedimplementation of the symbol table: you canconcentrate on solving the actual, specificproblem of providing a symbol table.  You can reasonably expect the STL library you have to be rigorously tested.  Though STL is a generic library, it isdesigned with efficiency in mind. It is in facta very efficient library.  STL is an industry standard and widely usedlibrary—so you can have any competent C++programmer get some exposure to the STLlibrary. A programmer who may possiblymaintain or extend your symbol table willfind it easy to understand theimplementation of your symbol table.  www.linuxforu.com | LINUX FOR YOU | MAY 2007 79 verv ew The list is not exhaustive, yet it covers a few veryimportant reasons to (re)use standard components asmuch as possible.However, just like C++, STL is designed for experiencedprogrammers: it requires some expertise to make use of itsfull potential and there are lots of traps and pitfalls that anovice can easily fall into. Also, it is a generic library whosedesign is inspired by the functional programming paradigm: itis not object-oriented! Hence, you need some understandingand experience about the design philosophy and problem-solving approach of STL to make the best use of it. STL components STL consists of three main parts:  Containers (like a stack)  Generic algorithms (like a sort)  Iterators (similar to the use of pointers)These components are designed such that they areignorant of specific details of other components, so thatthey can be combined together as the need arises. Herelies the secret of the power of STL: the ability toseamlessly combine the three to fit our need.Containers are objects that can hold other objects. Wecan use any type of object with these containers, butgenerally, it is assumed that an object that is used with acontainer has the following defined for the object:  copy constructor  assignment operator  == operator  < operatorThis is because whenever an object is used with acontainer, a copy of the object is created and only the copy ispresent in the container; so we need the copy constructorand assignment operator to be defined. Also, many of thealgorithms used by the containers need a comparisonbetween objects; so we need == and < overloaded operators. Containers Containers are the data-structures in which we can storeobjects. Basically, we have two kinds of containers:   Sequence containers: Sequence containers: Sequence containers: Sequence containers: Sequence containers: These containers store andretrieve data in a sequential fashion. They include thesimple array, list, vector and deque.     Associative containers: Associative containers: Associative containers: Associative containers: Associative containers: The elements of thesecontainers are associated in some manner. Theassociative containers are  map, multimap, set and  multiset. They rely heavily on comparison operators,because the objects are stored in a sorted order.In other words, sequence containers can hold elementsof the same type, whereas associative containers arecapable of holding a key-value pair.Let’s look at a few of the containers in STL:  vector: vector: vector: vector: vector: Vector can be treated as an array with the capabilityof growing or shrinking dynamically. This can be safely usedinstead of arrays. The elements can be accessed in two ways:  using the overloaded operator []  using the method at The first one is easier and faster to use, but it is not rangechecked. On the other hand, the at method does rangechecking and throws out_of_range exception if needed. deque:deque:deque:deque:deque: This is basically a double-ended queue. If wewant to grow/shrink in a vector, we can do it only at oneend. But with deque , we can do it at both the ends. Itprovides the same accessing efficiency as the  vector butthe allocation efficiency comparable with a list . list:list:list:list:list:  Arrays are optimised for random access but areinefficient when it comes to inserting and deletingelements in the middle; so are the  vector and deque. Foroperations requiring intensive insertions and deletions, usea list, which is very efficient for these operations (and isinternally implemented as a double-linked list ). With alist, you cannot have random access to the data and so the [] operator is not overloaded.  map and set: map and set: map and set: map and set: map and set: Both store the elements along with aunique key. In most of the cases, these two areinterchangeable. The only difference is that in a set, the values are irrelevant and we keep track of the keys only.They provide an important functionality, which thesequence containers do not provide—the  find operation.  multimap and multiset: multimap and multiset: multimap and multiset: multimap and multiset: multimap and multiset: These are extended versions of a map and set respectively. In a map and set,the keys should be unique. But a multimap and multiset donot have this constraint. All the operations of theirrespective counterparts are supported here also. Algorithms The <algorithm> header file provides us with many of thealgorithms that we use in our day-to-day programming (andlots of not so obvious ones, too). For example, most of ushave ended up writing our own versions of a sort, search, find,etc, and STL allows us to reuse the code and helps us toconcentrate on more creative aspects of programming. Let uslook at an example of using a fundamental operation—swap: #include <iostream>#include <algorithm>using namespace std;int main(){string this = “this”, that = “that”;std::swap(this, that);cout<< “this = “<< this<< “and that = “<< that<< endl;}// prints: this = that and that = this  Algorithms in STL are basically of three types:  non-modifying (sequence); for example,  find  modifying (sequence); for example,  fill  sorted (sequence); for example,  sort Non-modifying algorithms are for read-only/traversingfunctionality that essentially doesn’t modify the content of the containers. In short, they don’t modify the sequence onwhich they operate. Note that ‘sequence’ here refers to the‘sequence containers’—referring to containers with  80 MAY 2007 | LINUX FOR YOU |  www.linuxforu.com verv ew elements of the same type T (homogeneous elements), forexample,  std::vector<T>, std::list<T>. Modifying algorithms may alter the sequence on whichthey operate. The last kind of algorithms work on sortedsequences—for example, the binary_search algorithm. As you can easily guess,  swap comes under modifyingsequence algorithms. Iterators Iterators are generalised pointers and act as the glue betweencontainers and algorithms. STL algorithms are written interms of iterator parameters, and STL containers provideiterators that can be plugged into algorithms. Generally,iterators point to a location within a container.Iterators have a pointer-like syntax (in many cases,iterators are indeed implemented as pointers internally).Thus, generic algorithms can handle arrays and pointers -this is of significant importance since we need not throwaway our C-style arrays for the sake of using this library.For example, in the  find generic algorithm, we can eitheruse arrays or container classes: #include<iostream>#include<vector>using namespace std;int main(){int arr[] = {1, 4, 9, 16, 25}; // some valuesint * arr_pos = find(arr, arr+4, 9);std::cout<< “array pos = “<< arr_pos - arr << endl;// find the first occurrence of 9 in the arrayvector<int> int_vec;for(int i = 1; i <= 5; i++)int_vec.push_back(i*i);vector<int>::iterator vec_pos =find (int_vec.begin(),int_vec.end(), 9);std::cout<< “vector pos = “<< (vec_pos - int_vec.begin());// find the first occurrence of 9 in the vector}// prints://array pos = 2//vector pos = 2 Here, note that we are using iterators as ‘pairs’. This is howwe generally make use of iterators: a way of marking thebeginning and the end of the sequence to be operated on.However, unlike pointers, there is no iterator equivalent of ‘null’—it’s simply undefined behaviour to dereference aniterator pointing to some illegal value. Traditionally, returningnull (0) is how we indicate that a value searched is found ornot. Since null cannot be used for iterators, how do we indicatethat the value searched is not found? For that, the element‘one-past’ the end is used (note that it is not illegal for a pointerto point ‘one-past’ the last element in an array). For example: int arr[] = {1, 4, 9, 16, 25}; // some valuesint * pos = find(arr, arr+4, 36);if(pos == (arr+4))std::cout<< “Searched element not found in the array”;elsestd::cout<< “Found in the position “<<(pos - arr);// prints://Searched element not found in the array This aspect of iterators is very important to understandas it is used extensively in STL. Why iterators? Let’s suppose that you want to go to the beginning of a list.You can use the member function  front , which returns aniterator (reference) to the first element of the array, and inthis way proceed with your usual work. You might wonderwhy we need iterators when member functions will do.Let us take the generic algorithm  sort , which is usedfor sorting, say, a  vector . If we hadn't had iterators, thenwe would have had to write a separate algorithm for eachand every container. So we pass to this algorithm twoiterators as parameters, which point to the start and end of the sequence to be sorted, respectively. You will noticethat, with this mechanism we are able to use any sort of containers with an algorithm. Important concepts for using STL Since STL provides a whole new way of solving theproblems in C++, there are many concepts that need to beunderstood to learn and to make best use of STL.Function objects:Function objects:Function objects:Function objects:Function objects: Using C style function pointers isnot type-safe and isn’t object oriented. An alternative inC++ is to use ‘function objects’. By overloading thefunction call operator (), we encapsulate a function andpass it on to some other functions. The advantages of usinga function pointer (also referred to as ‘functor’) are:  typesafe and object oriented  efficient, as it can be inlined  reusable, as it can be genericThe idea is to overload the () operator so that the objectcan be used as if it were a function. Overloaded () can haveany number of arguments / any return type. For example: #include<iostream>using namespace std;class printClass{public:template<class T> void operator() (T t){ cout<< t << endl; }};template<class T> void print(T type, printClass &p){p(type);// invoke the () operator  www.linuxforu.com | LINUX FOR YOU | MAY 2007 81 verv ew }int main(){int i = 10;float f = 10.0;printClass p;print(i, p);print(f, p);}// prints//10//10 This simple program makes use of function objects toprint objects of any type (provided that they override ostream << ()). Plug-compatibility:Plug-compatibility:Plug-compatibility:Plug-compatibility:Plug-compatibility: Plug-compatibility in programming jargon means that a generic algorithm and a container canbe plugged (used) together. For example  , vector and  sort are plug-compatible (you can apply  sort function on a  vector ), whereas you cannot use  sort for a list —for that you have to use the  sort member function (of  list ).Theoretically, it is possible for generic  sort to be pluggedwith list— but it will affect the efficiency of the code. So, list provides a separate member function to achieve that. sort(vector1.begin(), vector1.end());// ok, worksvector1.sort();// no sort member functionsort(list1.begin(), list1.end());// no, generic sort should not be used with listlist1.sort();// ok, works Nearly containers:Nearly containers:Nearly containers:Nearly containers:Nearly containers: STL is a generic library withcomponents written for general-purpose use. But not allcomponents are ‘truly generic’. There are threecomponents in STL that are written for specific types/ purposes in mind. For example, bitset is not a generic setcomponent—it is specifically designed to handle bitinformation. Such containers are referred to as ‘nearlycontainers’, and they are for specific purposes and notreally generic in nature. The other two containers are  valarray —designed specifically for numericcomputations, and  string , an alternative for nullterminated C-style strings.Predicate objects:Predicate objects:Predicate objects:Predicate objects:Predicate objects: When a function object returns aBoolean value, it is referred to as a ‘predicate object’. In STL, <functional> contains many such predicate objects and theycan be used in generic algorithms to change their behaviour.For example, the  sort method implicitly takes the less<int> predicate as the third argument (to sort the elements inascending order). To change this default behaviour of   sort , itis enough to pass some other predicate! Adaptors: Adaptors: Adaptors: Adaptors: Adaptors: Adaptors, as the name itself hints, is acomponent that adapts (modifies) an existing interface of a component to expose a different one suitable for someother purpose. There are three types of adaptors:   Sequence adaptor: The interface of a container isexposed in a different way. A classic example forsequence adaptors is from STL itself:  stack is built onmodifying the interface of  deque .   Iterator adaptor: When the interface of an iterator isexposed in a different way, it is an iterator adaptor.   Function adaptor: Function adaptors are functionobjects—depending on the function object (say a‘negator’ or a ‘predicate object’) passed, the behaviourof the algorithm may change.Pseudo-destructor:Pseudo-destructor:Pseudo-destructor:Pseudo-destructor:Pseudo-destructor: STL is fully generic and it needsmany extensions/modifications, mostly related totemplates to support it. For example, ‘pseudo destructor’is just a syntactic convenience: it enables primitive type tobe used with containers and algorithms. template <typename T> void callDest(T &t){t.T::~T();};class Test{public:~Test(){std::cout<<“calling the destructor”<<endl;}};int main(){int i;callDest(i);// doesn’t issue compiler error// when t.T::~T() resolves to t.int::~int()// this has no effect in the code generated.Test t;callDest(t);// results in calling the destructor explicitly// prints:// calling the destructor} Hopefully, this introduction to Standard TemplateLibrary would help a novice understand its basics, in detail.We will cover further details on the same topic later. Tillthen, happy reading...  By: S.G. Ganesh By: S.G. Ganesh By: S.G. Ganesh By: S.G. Ganesh By: S.G. Ganesh is an engineer in Hewlett-Packard’s C++compiler team. He has authored a book “Deep C” (ISBN 81-7656-501-6). He is also a member of the ANSI/ISO C++ Standardisation committee (JTC1/SC22/WG21), representing HP. You can reach him at sgganesh@gmail.com.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x