Pointers themselves are iterators, which is why it is possible to reverse the elements of a C array. In the example above, the type returned by v. Iterators are the mechanism that makes it possible to decouple algorithms from containers: algorithms are templates, and are parameterized by the type of iterator, so they are not restricted to a single type of container.
Consider, for example, how to write an algorithm that performs linear search through a range. This is the STL's find algorithm.
Find takes three arguments: two iterators that define a range, and a value to search for in that range. It examines each iterator in the range [first, last , proceeding from the beginning to the end, and stops either when it finds an iterator that points to value or when it reaches the end of the range. First and last are declared to be of type InputIterator , and InputIterator is a template parameter.
That is, there isn't actually any type called InputIterator : when you call find , the compiler substitutes the actual type of the arguments for the formal type parameters InputIterator and T. One very important question to ask about any template function, not just about STL algorithms, is what the set of types is that may correctly be substituted for the formal template parameters.
The basic answer, then, is that find implicitly defines a set of requirements on types, and that it may be instantiated with any type that satisfies those requirements. Whatever type is substituted for InputIterator must provide certain operations: it must be possible to compare two objects of that type for equality, it must be possible to increment an object of that type, it must be possible to dereference an object of that type to obtain the object that it points to, and so on.
These requirements are sufficiently important that we give them a name: we call such a set of type requirements a concept , and we call this particular concept Input Iterator. We say that a type conforms to a concept , or that it is a model of a concept , if it satisfies all of those requirements.
Nevertheless, concepts are an extremely important part of the STL. Using concepts makes it possible to write programs that cleanly separate interface from implementation: the author of find only has to consider the interface specified by the concept Input Iterator , rather than the implementation of every possible type that conforms to that concept.
Similarly, if you want to use find , you need only to ensure that the arguments you pass to it are models of Input Iterator. This is the reason why find and reverse can be used with list s, vector s, C arrays, and many other types: programming in terms of concepts, rather than in terms of specific types, makes it possible to reuse software components and to combine components together.
Also we can replace the Line 31 with below line. Further the STL has three separate components i. But this separation is quite useful, as it reduces the number of algorithm-implementations in STL by increasing the re-usability.
In the other words, with the help of separation, an algorithms can be used for different containers instead of one algorithm for each component. This is achieved by an intermediate entity i. Sequence container : It is an ordered collection i. STL contains five sequence containers,. STL has four associative containers,.
Unordered container : In this container, the position of the elements do not matter i. STL has four types of unordered container,. We already saw an example of vector in Listing The size of the vector changes, when we insert or delete an element to it. Hence the index-access is not possible in lists.
Further, it does not provide a random access i. For insertion and deletion, only two links needed to be changes instead of shifting the whole array , therefore insertion and deletion is faster in lists. Associative containers sort the elements automatically based on one of the two criterion i. Below is the output of above code. Unordered containers do not have any order. All containers provide same set of iterators. The following two iterators are the most important iterators,. We already see the example of iterator in Listing In the below code, the Listing Random access iterators allows the random access of the elements in the containers.
These iterators can be increment or decrement using mathematical operations Lines 17 and Also, these iterators can be compared with each others Line Input iterators read and process the values while iterating forward.
We can read the value using input iterators, but can not write the value. Note that, this iterator can not move backward. Output iterators output the value while iterating forward. We can write the value to the output iterator but can not read the value. STL provides some functions as well for iterators as shown in Lines 17 and 21 of Listing The algorithms are used on containers to perform various operations such as sorting, searching and transforming etc.
In previous sections, we saw that the functions may not available to all kinds of containers e. In this section, few tables are added which show the various functions available for different types of container.
Table Some of the possible vector operations are listed in Table The operations in deque is same as vector operations Table Further, Listing In this section, we will see some more examples along with some new features of each element. A lot of data structures are based on real-life applications. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized.
Note: We can include just one library, i. To overcome this problem, we can add specific libraries to access particular data structures of STL. Also while removing the elements, it is required to take care if the data structure is empty or not.
Calling remove function on an empty data structure leads to error. Below are the some Data Structures with their illustration shown. It can be implemented using arrays, linked lists, and vectors.
Some problems like reversing an element or string, parenthesis check, print next greater element, postfix expression, etc, can be done using stack class rather than making all the functions we can use its inbuilt functions. For example, in a queue for buying tickets for a show, the one who enters the queue first, get the ticket first. It can be implemented using arrays, linked lists, and vectors just like stacks. Some applications of queue include level-order traversal in trees and graphs, in resource sharing, etc.
Priority Queue : This data structure is similar to queues, but the order of first out is decided by a priority set by the user. The main functions include getting top priority element, insert, delete the top priority element or decrease the priority.
Deletes element with max priority in max heap else deletes min element size : Returns the size of the queue. In max priority queue, it returns the maximum, while in min priority queue, it returns the minimum value. Set : Sets are associative containers in which each element is unique. The elements cannot be modified once inserted in the set. A set ignores the duplicate values and all the elements are stored in sorted order.
This data structure is particularly useful when incoming elements need to be sorted and modification is not required. The sets can store elements in two orders, increasing order or decreasing order.
0コメント