An Introduction of Stl for Beginners

zhaozj2021-02-16  83

OK, Guys, Here Is One More Beginner's Tutorial., IF you are new to stl and intended in knowing what this STL IS? Or top to use stl in your program? I bet this tutorial is for you. If you .

The Evolution

The Standard Template Library (STL) is not a new library as compared to other libraries. Originally, the development of the STL was started by Alexander Stepanow at HP in 1979. Later, he was joined by David Musser and Meng Lee. In 1994, STL WAS INCLUDED INTO ANSI AND ISO C .

Why the STL?

In one of my project I needed a doubly linked-list to store a tree's node values. One of my fellow developer created this class which has general functions such as addNode, deleteNode, SeachNode, InsertNode and others. It took him more than a week And West Had Some Memory Problems IN It.

The STL provides general purpose utility classes which programmers can use in their applications and they even do not have to worry about allocating and freeing memory. These classes are array, link, stack and map classes. And the STL provides general algorithms for sort, Search, Or Reverse Arrays or Links. Besides these Two Things, The Stl Also Provides Some Iterators and Other Options You Can Apply On these Classes.

Features:. The STL's generic algorithms work on native C data structures such as strings and vectors STL containers are very close to the efficiency of hand-coded, type-specific containers Learning of STL is very simple You need some knowledge of templates and.. C .

WHEN to use the STL?

IF you need to provide any stl features in your program, you can use them.advantages of the STL

You dont have to write your classes and algorithms. It saves your time.You dont have to worry about allocating and freeing memory. That's a big problem when you create you own linked-list, queue or other classes. Reduces your code size because STL uses templates to develop these classes. you have to override your functions or classes to operate on different types of data while STL let you apply these classes on different kind of data.Easy to use and easy to learn.

Templates

......................

A template is a mechanism for generating functions and classes which can apply on different types of data. You can design a single class that operates on different type data. For example, you can create a link list class which can work on into, long, OR Double Data Types. We Will See IN Our Example.

There Are Two Types of Templates: Function Templates and Class Templates.

Function Templates

Function Templates Allow You to Write Types Safe Functions and IT CAN Reduce Size Of Code And Increate Code Flexibility. For Example, IF you have an offloaded function add () Which is defined as here:

INTO Adding A, INTO B) {RETURN A B;}; long add (long A, long b) {RETURN A B;}; Double Add (double a, double b) {Return A B;};

INSTEAD, You CAN WRITE A TEMPLATE FUNCTION ADD Which Will Solve this overloading proBLEM.

Template T Add (T A, T B) {Return A B};

Now you can use this template on diffreent types of data. Such as:

INTO TOTAL = Add (12, 35); Long Total = Add (10245, 35234); double total = add (12.60, 35.98); Fair Easy. Huh?

Class Templates

Templates allows to create classes that do not operate on a specific data type. Instead, the data type can be provided by the user at runtime. Here is an example. We have a class Math, which has three functions, Add, Divide, and Multiply.

Template class math {public: Math () {}; t add (t a, t b) {RETURN A B}; t Divide (t a, t b) {RETURN A B}; T Multiply (T a, t b) {RETURN A B};

Now you can use this class with diffrest data type. Here is how to use it:

Math dmath; // instantiaating the class for double dreturn = dmath.add (12.34, 34.654); double dreturn = dmath.multiply (12.34, 34.654); Math imath; // instantiarating the Class for Integer Data Type. IRETURN = DMath.Add (12, 34); IRETURN = DMATH.MULTIPLY (12, 34);

Does it make Sense? OK, ITS ENOUGH ABOUT TEMPLATES.

Basic Elements of The STL

Here is a list of elements of the stl. First Three of Them Are Fundamental Items.

ItemDescriptionContainerAn object that holds another objectsAlgorithmA function that acts on containersIteratorA pointer-like objectAllocatorThis item manages memory allocation in a containerAdaptorTransforms one object into anotherPredicateA function that returns a boolean value, true or false.Function ObjectA class that defines operator ().

CREATES A Linked-list.

Algorithms are second most useful element of the STL. Algorithms act on the containers. They used to perform operations on the containers such as sorting, searching and others.Iterators work as their name say :). They provide iterations for the STL containers. Iterations Mean looping., if you want to search a contact, you...................

Allocators Manage Memory Allocations for the containers.

An adaptor is used to communication from one Object to another. They area Kind of conversions utilities. For example, you can queue Using Queue Adaptor.

Function Objects Aread (), Greater (), Divides (), Plus (), Minus () etc.

THE Containers

Containers are the base elements of the STL. Containers holds actual data. I should say that containers are data structures that stores, manage a set of items. Containers have constructors and destructors to provide allocation and deallocation for stored items. These items can be an Basic Data Type Such As Int, Char, String etc. All Containers Arement, Templates. The Good Thing About Containers IS All Containers Have Same Specification.

SEQUENCE A SEQUENCE IS A LINEAR LIST Which Stores All of Its Elements in linear Order. For example an array is a sequence.

Char ch [10] is an array of char types 10 Elements Which is Ordered in a linear fashion.

There Are Two Types of Containers and third Type is Container Adaptors:

TypeContainer classesDescriptionSequencevector, list, dequeDynamic arrays, support insertion or deletion in beginning or at the end. They does not support insertion or deletion at a specific position.Associativemap, multimap, set, multisetThis type of container is a variable-sized Container that supports efficient retrieval of elements based on keys. They store data in the form of a key and value. A key has corresponding value or values.Container adaptorsstack, queue, priority_queueThey are restricted containers and do not support all the functionality provided by containers. We Will See In Out definitions later in this tutorial.here is a list of the site...................

ContainerHeader FileVector Deque MultiSet Map MultiMap queue priority_queue stack

Let's see these containers in detail now.

The Vector containerVector container is simplest container It supports random access It provides insertion, deletion of elements at the end Its dynamic array which varies according to need It supports automatic memory management For example.....:

Vector vlist; // initializes a vector list of integers // Fill Values ​​in vlist using push_back for (int i = 1; i <20; i ) Vlist.push_back (i);

Here Is A Sample EXAMPLE OF Vector Conta Us REVERSE ALGORITHM to REVERSE AN ARRAY?

The deque containerThis container is same as vector container accept that the deque container is a queue with both ends That means elements can be added or deleted from both front and back ends Elements can also be inserted at any specific position For example:... Deque d1; d1.push_front (2); d1.push_back (4);

Here Is Sample EXAMPLE OF DEQUE Container. How to use deque container to add and delete items?

The List Container

A list is a doubly linked list. It supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Other list container is slist which is singly linked list. A List Container Is Really Useful When Elements Will Be Frequently ADDED OR Removed from The Middle of The Container And Random Access to Elements Is Not Required.

Example: Sorting Contents of a List Using Sort Algorithm

The Map and Multimap Containers

THE MAP AND MULTIMAP Containers Store Data in The Form of a Pair. Each Pair Has a Key and Corresponding Value (s). For example, pair stdrec = (name , Marks ). A Map Can Store Data OF Type Stdrec Which Has Two Elements, a Key and ITS Value. The Basic Data Type of Key Might Difer from the value. IN Our Example, Key Name Is Int Type.

Map containers. A KEY CAN HAVE SOME DUPLICATE. A KEY May Be a name. So basicly mapsed by using Key. for example:

Map data; for (int i = 0; i <10; i ) data.insert (Pair ('MCB' I, 100 I);

Multimap containers are similar to map accept the allow to store duplicate keys. That Means One Key Can Have More Tan One VALUES.EXAMPLE: How to Use Map Container

The Set and MultiSet Containers

SET Containers Are Similar To Map Containers Except That The Key Part of Value. SIMILAR THE PART. SETS Stores Data IN A form.

Set Class Supports A Set in Which Unique Keys Are Stored. While Multoset Let You Have Duplicate Keys.

Set SDATA; SDATA.INSERT ("MAHESH"); SDATA.INSERT ("Owen"); SDATA.INSERT ("LARA"); set :: itemarator P = sdata.begin ();

Do {cout << * P << ""; p ;} while (p! = sdata.end ());

The Queue Container Adaptor

The queue is a FIFO queue which has certain restrictions in compare to other containers. Elements are inserted into a queue from the tail end and removed from the head. Its like a queue on a gas station. First vehicle fills gas first and next vehicle comes After Last Vehicle. Push and pop is two major operation of the queue.

Queue SDATA; SDATA.PUSH ("MAHESH"); sdata.push ("Owen"); sdata.push ("lara");

While (! sdata.end ()) {cout << sdata.front () << "; sdata.pop ();

The Stack Container Adaptor

The stack is a LIFO queu. Operations are similar to queue accept elements are inserted from top of the stack and removed from top of the stack too. For example a stack of plates in the kitchen. Push and pop are two major operation of the stack .

Stack SDATA; SDATA.PUSH ("MAHESH"); SDATA.PUSH ("Owen"); SDATA.PUSH ("LARA");

While (! sdata.empty ()) {cout << sdata.top () << "; sdata.pop ();

The Algorithmsalgorithms Are Used on The Data of Containers.

Some basic algorithms are sort, search, count, reverse, or merge. Using these algorithms on containers is pretty easy. For example, if you have a vector container with some data in it, here is how to use count algorithm to count its elements :

Vector vdata; ..... add some data ... int i = count (vData.begin (), vData.end (), 3);

Here is Reverse Algorithm:

Vector vdata; ..... add some data ... reverse (vData.begin (), vData.end ());

Lets See One More Example of Sorting The Data.

Vector vdata; vdata.push_back (5); vdata.push_back (3); vData.push_back (8);

Sort (vDATA);

Example: Sorting Contents of a List Using Sort Algorithm

STL Has over 60 Algorithms listed here with their description.

AlgorithmDescriptionadjacent_findSearches for adjacent matching elements within a sequence and returns and iterator to the first matchbinary_searchPerforms a binary search on an ordered swquencecopyCopies a sequence.copy_backwardSame as copy accept that it moves the elements from the end of the sequence firstcountReturns the number of elements in the sequence. count_ifReturns the number of elements in the sequence that satisfy some predicate.equalChecks if two ranges are sameequal_rangeReturns a range in which an element can be inserted into a sequence without disrupting the ordering of the sequence.fill and fill_nFills a range with a specified valuefindSearches and returns the iterator to the first occurencefind_endLast iteratorfind_first_ofFinds the first elementfind_ifSearches with a predicatefor_eachApplies a function to a range of elementsgenerate and generate_nAssigns elements in a range of the values ​​returned by a generator function.includesDetermines if one sequence includes al l elements of other sequence.implace_mergeMerges a range with another rangeiter_swapExchange the values ​​pointed to by its iterator argumentslexicographical _compareCompares two sequences alphabeticallylower_boundFind the first point in the sequence that is less than a specified value.make_heapConstructs a heap from a sequence.maxReturns the maximum of two values.minReturns minimum of two values.min_elementReturns the iterator to the min element within a range.mismatchFinds the first mismatch between the elements in two sequences.next_permutationConstructs next permutation of a sequence.nth_elementArranges all elements in a order so all element less than nth element Come Before IT and Greater Than Come After it.partial_sortsorts a range.

partial_sort_copySorts and copies elements.partition, stable_partitionArranges elements so all elements return true for a predicate come before it and false come after it.pop_heapExchanges first and last-1 elements prev_permutationConstructs previous permutationpush_heapPushes elements onto the end of the heap.random_shuffleRandomize a sequence.remove, remove-if, remove_copy, remove_fopy_ifRemoves elementsreverse and reverse_copyReverses the order of a rangereplace, replace_if, replace_copy, replace_copy_ifReplaces elements within a range.rotate, rotate_copyLeft-rotatesearch, search_insearches a subsequence within a sequenceset_differenceProvides difference between two ordered sets.set_intersectionProvides intersection output between two sets .set_symmetric_ differenceProvides symmetric output between two sets. set_unionProvides union of two sets.sort, stable_sortSorts a range.sort_heapSorts a heap.swap, swap_rangesExchanges two values, ranges.transformApplies a function to a range of Elements and stores outcome, unique_copyeliminates duplicate elements.upper_boundfinds the last point in a suquence.mergemerges two sequence.iterators

Containers do not provide access to thier elements. They used iterators to traverse the elements within a container. In other words, the iteratos provides a way to cycle through the contents of containers. Each container defines one or more iterator types that we can declare iterators For That Container. There is Five Types of Iterators. Iterators Are Very Similar To Smart Pointers and Have Increment and Derefeerencing Operations.

TypeDescriptionRandom AccessStores and retrieves elements randomly.BidirectionalStores and retrieve elements forward and backward both directions.ForwardStores and retrieve forward only.InputForward retrieve only.OutputForward, stores only.As we have seen in our previous examples, we can use iterators like in this sample: Set SDATA; SDATA.INSERT ("MAHESH"); SDATA.INSERT ("Owen"); SDATA.INSERT ("LARA"); set :: itemarator P = sdata.begin ();

Do {cout << * P << ""; p ;} while (p! = sdata.end ());

Function Objects

A Function Object Is An Object That Can Be Called As A Function. The Header for Functional Objects IS . There Are Three Types of Function Objects:

NameDescriptionGeneratorGenerator is a function object which does not take any parameters Such as Do ();. BinaryA binary function object is a function object which takes two arguments Such as Do (int a, char b) Some of them are plus, minus.. , divides, modulus, equal_to, not_equal_to, greater_equal, greater, less, less_equal, local_and, logical_orUnaryA unary function object takes single argument as a parameter Such as Do (false);. logical_notnegate

Function Adaptors

.....................................

Container Adaptors

What if you need to create a new container from an existing one? That means you need to extend the functionality of an existing one and add some more to new one. You can do that by mapping the interface of an existing container to that of the New container.

The STL provides three container adaptors: stack , queue , and deque The following program demonstrates the use of a stack that has been implemented as a vector:. #Include

#include

Void

MAIN () {

Stack >.

For (int i = 0; i <10; i )

St.push (i);

While (! st.empty ()) {

COUT << st.top () << "

ST.POP ();

}

Cout << Endl;

}

Iterator Adaptors

Adaptors CAN Also Be used to Extend The FunctionAry OF An EXISTING ITERATOR. The Reverse, Insert, And Row Storage Iterators Are Example of Iterator Adaptors In The STL.

Allocator

Allocators are responsible of memory management in the STL. Each container has one its allocator. Allocators allocate and deallocate memory automatically for a container. But you can even create your own custom allocators.

The default allocator is allocator. It is defined in the Header File. This Table Shows Allocator's Functions and Their Description:

FunctionDescriptionpointer address (reference ob) const; const_pointer address (const_reference ob) const; Returns the address of object ob.pointer allocate (size_tpe num, typename allocator :: const_pointer h = 0); Returns a pointer to allocated memoryvoid construct ( pointer ptr, const_reference val); Constructs an objectvoid deallocate (pointer ptr, sise_type num); Deallocates num objectvoid destroy (pointer ptr) Destroys ptr object.size_type max_size () const throw (); Returns the maximum number of objects that can be allocated .

EXAMPLE:

Vector :: allocator_type d_a;

Cout << D_A.max_size ();

REFERENCES AND LINKS: If you are interested in more details of the STL, here are more links of STL documentation with sample examples.STL documentation and detailed description with sample examples Everything you need about STL http://www.sgi.com.. / Technology / STLSTL examples for every algorithm http://www.sgi.com/Technology/STL/table_of_contents.htmlSTL Books and other good links http://www.sgi.com/Technology/STL/other_resources.htmlDownload the STL and its versions http://www.sgi.com/Technology/STLThe Standard Template Library by Alexander Stepanov and Meng Lee (ANSI / ISO document) Algorithm-oriented Generic Libraries by David R. Musser and Alexander A. Stepanov

@ Copyright 1999-2003 MINDCRACKER. All Rights Are Reserved. See Terms and Condition To Use this site and its contents. Powered by Maximumasp. Secure Web Hosting for Serious Microsoft Developers

转载请注明原文地址:https://www.9cbs.com/read-10484.html

New Post(0)