Monday, January 20, 2014

container adapters in c++

STL containers in c++ : Standard Template Library Tutorial, ccplusplus.com
Container classes, or containers for short, manage a collection of elements. To meet different needs, the STL provides different kinds of containers, as shown in figure below
Figure: STL Container Types

There are two general kinds of containers:
  1. Sequence containers are ordered collections in which every element has a certain position. This position depends on the time and place of the insertion, but it is independent of the value of the element. For example, if you put six elements into a collection by appending each element at the end of the actual collection, these elements are in the exact order in which you put them. The STL contains three predefined sequence container classes: vector, deque, and list.
  2. Associative containers are sorted collections in which the actual position of an element depends on its value due to a certain sorting criterion. If you put six elements into a collection, their order depends only on their value. The order of insertion doesn't matter. The STL contains four predefined associative container classes: set, multiset, map, and multimap.
An associative container can be considered a special kind of sequence container because sorted collections are ordered according to a sorting criterion. You might expect this especially if you have used other libraries of collection classes like those in Smalltalk or the NIHCL, in which sorted collections are derived from ordered collections. However, note that the STL collection types are completely distinct from each other. They have different implementations that are not derived from each other.

The automatic sorting of elements in associative containers does not mean that those containers are especially designed for sorting elements. You can also sort the elements of a sequence container. The key advantage of automatic sorting is better performance when you search elements. In particular, you can always use a binary search, which results in logarithmic complexity rather than linear complexity. For example, this means that for a search in a collection of 1,000 elements you need, on average, only 10 instead of 500 comparisons. Thus, automatic sorting is only a (useful) "side effect" of the implementation of an associative container, designed to enable better performance.

The following subsections discuss the different container classes in detail. Among other aspects, they describe how containers are typically implemented. Strictly speaking, the particular implementation of any container is not defined inside the C++ standard library. However, the behavior and complexity specified by the standard do not leave much room for variation. So, in practice, the implementations differ only in minor details. Coming post with covers the exact behavior of the container classes. It describes their common and individual abilities, and member functions in detail.

Sequence Containers

The following sequence containers are predefined in the STL:
  • Vectors
  • Deques
  • Lists
In addition you can use strings and ordinary arrays as a (kind of) sequence container.
Vectors
A vector manages its elements in a dynamic array. It enables random access, which means you can access each element directly with the corresponding index. Appending and removing elements at the end of the array is very fast. However, inserting an element in the middle or at the beginning of the array takes time because all the following elements have to be moved to make room for it while maintaining the order. Strictly speaking, appending elements is amortized very fast. An individual append may be slow, when a vector has to reallocate new memory and to copy existing elements into the new memory. However, because such reallocations are rather rare, the operation is very fast in the long term. 

The following example defines a vector for integer values, inserts six elements, and prints the elements of the vector:


With


the header file for vectors is included.
The declaration


creates a vector for elements of type int. The vector is not initialized by any value, so the default constructor creates it as an empty collection.

The push_back() function appends an element to the container:


This member function is provided for all sequence containers. The size() member function returns the number of elements of a container:


This function is provided for any container class.
By using the subscript operator [], you can access a single element of a vector:


Here the elements are written to the standard output, so the output of the whole program is as follows:


Deques
The term deque (it rhymes with "check" ( It is only a mere accident that "deque" also sounds like "hack" :-)) ) is an abbreviation for "double-ended queue." It is a dynamic array that is implemented so that it can grow in both directions. Thus, inserting elements at the end and at the beginning is fast. However, inserting elements in the middle takes time because elements must be moved.

The following example declares a deque for floating-point values, inserts elements from 1.1 to 6.6 at the front of the container, and prints all elements of the deque:


In this example, with


the header file for deques is included.
The declaration


creates an empty collection of floating-point values.
The push_front() function is used to insert elements:


push_front() inserts an element at the front of the collection. Note that this kind of insertion results in a reverse order of the elements because each element gets inserted in front of the previous inserted elements. Thus, the output of the program is as follows:


You could also insert elements in a deque by using the push_back() member function. The push_front() function, however, is not provided for vectors because it would have a bad runtime for vectors (if you insert an element at the front of a vector, all elements have to be moved). Usually, the STL containers provide only those special member functions that in general have "good" timing ("good" timing normally means constant or logarithmic complexity). This prevents a programmer from calling a function that might cause bad performance.
Lists
A list is implemented as a doubly linked list of elements. This means each element in a list has its own segment of memory and refers to its predecessor and its successor. Lists do not provide random access. For example, to access the tenth element, you must navigate the first nine elements by following the chain of their links. However, a step to the next or previous element is possible in constant time. Thus, the general access to an arbitrary element takes linear time (the average distance is proportional to the number of elements). This is a lot worse than the amortized constant time provided by vectors and deques.

The advantage of a list is that the insertion or removal of an element is fast at any position. Only the links must be changed. This implies that moving an element in the middle of a list is very fast compared with moving an element in a vector or a deque.

The following example creates an empty list of characters, inserts all characters from 'a' to 'z', and prints all elements by using a loop that actually prints and removes the first element of the collection:


As usual, the header file for lists, <list>, is used to define a collection of type list for character values:


The empty() member function returns whether the container has no elements. The loop continues as long as it returns true (that is, the container contains elements):


Inside the loop, the front() member function returns the actual first element:


The pop_front() function removes the first element:


Note that pop_front() does not return the element it removed. Thus, you can't combine the previous two statements into one.
The output of the program depends on the actual character set. For the ASCII character set, it is as follows:


Of course it is very strange to "print" the elements of a list by a loop that outputs and removes the actual first element. Usually, you would iterate over all elements. However, direct element access by using operator [] is not provided for lists. This is because lists don't provide random access, and thus using operator [] would cause bad performance. There is another way to loop over the elements and print them by using iterators. After their introduction I will give an example.
Strings
You can also use strings as STL containers. By strings I mean objects of the C++ string classes (basic_string<>, string, and wstring). Strings are similar to vectors except that their elements are characters.
Ordinary Arrays
Another kind of container is a type of the core C and C++ language rather than a class: an ordinary array that has static or dynamic size. However, ordinary arrays are not STL containers because they don't provide member functions such as size() and empty(). Nevertheless, the STL's design allows you to call algorithms for these ordinary arrays. This is especially useful when you process static arrays of values as an initializer list.

The usage of ordinary arrays is nothing new. What is new is using algorithms for them.

Note that in C++ it is no longer necessary to program dynamic arrays directly. Vectors provide all properties of dynamic arrays with a safer and more convenient interface.

Associative Containers

Associative containers sort their elements automatically according to a certain ordering criterion. This criterion takes the form of a function that compares either the value or a special key that is defined for the value. By default, the containers compare the elements or the keys with operator <. However, you can supply your own comparison function to define another ordering criterion.

Associative containers are typically implemented as binary trees. Thus, every element (every node) has one parent and two children. All ancestors to the left have lesser values; all ancestors to the right have greater values. The associative containers differ in the kind of elements they support and how they handle duplicates.
The following associative containers are predefined in the STL. Because you need iterators to access their elements.
  • Sets
    A set is a collection in which elements are sorted according to their own values. Each element may occur only once, thus duplicates are not allowed.
  • Multisets
    A multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value.
  • Maps
    A map contains elements that are key/value pairs. Each element has a key that is the basis for the sorting criterion and a value. Each key may occur only once, thus duplicate keys are not allowed. A map can also be used as an associative array, which is an array that has an arbitrary index type (see page 91 for details).
  • Multimaps
    A multimap is the same as a map except that duplicates are allowed. Thus, a multimap may contain multiple elements that have the same key. A multimap can also be used as dictionary. See page 209 for an example.
All of these associative container classes have an optional template argument for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for equality; that is, two elements are equal if neither is less than the other.

You can consider a set as a special kind of map, in which the value is identical to the key. In fact, all of these associative container types are usually implemented by using the same basic implementation of a binary tree.

Container Adapters

In addition to the fundamental container classes, the C++ standard library provides special predefined container adapters that meet special needs. These are implemented by using the fundamental containers classes. The predefined container adapters are as follows:
  • Stacks
    The name says it all. A stack is a container that manages its elements by the LIFO (last-in-first-out) policy.
  • Queues
    A queue is a container that manages its elements by the FIFO (first-in-first-out) policy. That is, it is an ordinary buffer.
  • Priority Queues
    A priority queue is a container in which the elements may have different priorities. The priority is based on a sorting criterion that the programmer may provide (by default, operator < is used). A priority queue is, in effect, a buffer in which the next element is always the element that has the highest priority inside the queue. If more than one element has the highest priority, the order of these elements is undefined.

Container adapters are historically part of the STL. However, from a programmer's view point, they are just special containers that use the general framework of the containers, iterators, and algorithms provided by the STL.








-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

43 comments:

  1. This is a brilliant blog! I'm very happy with the comments!.. shipping containers

    ReplyDelete
  2. Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. shipping containers for sale toowoomba

    ReplyDelete
  3. I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have enjoyed reading. toowoomba shipping containers

    ReplyDelete
  4. I admire what you have done here. I like the part where you say you are doing this to give back but I would assume by all the comments that this is working for you as well. toowoomba shipping containers

    ReplyDelete
  5. This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. shipping container

    ReplyDelete
  6. I admire what you have done here. I like the part where you say you are doing this to give back but I would assume by all the comments that this is working for you as well. shipping container for sale

    ReplyDelete
  7. This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works. shipping containers ballina

    ReplyDelete
  8. Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. shipping containers ballina

    ReplyDelete
  9. This article gives the light in which we can observe the reality. This is very nice one and gives indepth information. Thanks for this nice article. shipping container brisbane

    ReplyDelete
  10. This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works. shipping containers brisbane

    ReplyDelete
  11. Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. shipping containers brisbane

    ReplyDelete
  12. Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. shipping container ballina

    ReplyDelete
  13. This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works. brisbane shipping containers

    ReplyDelete
  14. Cool stuff you have got and you keep update all of us. brisbane shipping containers

    ReplyDelete
  15. I found this is an informative and interesting post so i think so it is very useful and knowledgeable. I would like to thank you for the efforts you have made in writing this article. shipping containers for sale cairns

    ReplyDelete
  16. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!. cairns shipping containers

    ReplyDelete
  17. Thanks for sharing this quality information with us. I really enjoyed reading. Will surely going to share this URL with my friends. buy shipping container cairns

    ReplyDelete
  18. Great things you’ve always shared with us. Just keep writing this kind of posts.The time which was wasted in traveling for tuition now it can be used for studies.Thanks shipping container cairns

    ReplyDelete
  19. Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. shipping container gold coast

    ReplyDelete
  20. I just want to let you know that I just check out your site and I find it very interesting and informative.. shipping containers for sale gold coast

    ReplyDelete
  21. Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. buy shipping container cairns

    ReplyDelete
  22. I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. buy shipping container cairns

    ReplyDelete
  23. I really thank you for the valuable info on this great subject and look forward to more great posts. Thanks a lot for enjoying this beauty article with me. I am appreciating it very much! Looking forward to another great article. Good luck to the author! All the best! gold coast shipping containers

    ReplyDelete
  24. This blog is really great. The information here will surely be of some help to me. Thanks!. shipping container gold coast

    ReplyDelete
  25. I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot! shipping containers for sale gold coast

    ReplyDelete
  26. Your content is nothing short of brilliant in many ways. I think this is engaging and eye-opening material. Thank you so much for caring about your content and your readers. shipping containers gold coast

    ReplyDelete
  27. I have a hard time describing my thoughts on content, but I really felt I should here. Your article is really great. I like the way you wrote this information. buy shipping container gold coast

    ReplyDelete
  28. You have a good point here!I totally agree with what you have said!!Thanks for sharing your views...hope more people will read this article!!! abc container hire

    ReplyDelete
  29. This is a brilliant blog! I'm very happy with the comments!.. abc containers

    ReplyDelete
  30. I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot! port shipping container

    ReplyDelete
  31. I recently came across your blog and have been reading along. I thought I would leave my first comment. I don’t know what to say except that I have enjoyed reading. 40ft shipping container

    ReplyDelete
  32. You’ve got some interesting points in this article. I would have never considered any of these if I didn’t come across this. Thanks!. container sales containers for sale

    ReplyDelete
  33. This is a good post. This post gives truly quality information. I’m definitely going to look into it. Really very useful tips are provided here. Thank you so much. Keep up the good works. sea container

    ReplyDelete
  34. I have read a few of the articles on your website now, and I really like your style of blogging. I added it to my favorites blog site list and will be checking back soon. Please check out my site as well and let me know what you think. container sales containers for sale

    ReplyDelete
  35. Your work is very good and I appreciate you and hopping for some more informative posts. Thank you for sharing great information to us. sea container

    ReplyDelete
  36. I really impressed after read this because of some quality work and informative thoughts . I just wanna say thanks for the writer and wish you all the best for coming!. 20ft container sales

    ReplyDelete
  37. Nice to be visiting your blog again, it has been months for me. Well this article that i’ve been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share. 20ft container for sale

    ReplyDelete
  38. You’ve got some interesting points in this article. I would have never considered any of these if I didn’t come across this. Thanks!. abc containers

    ReplyDelete
  39. This is a smart blog. I mean it. You have so much knowledge about this issue, and so much passion. You also know how to make people rally behind it, obviously from the responses. abc container hire

    ReplyDelete
  40. This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post. port shipping container

    ReplyDelete
  41. This is a brilliant blog! I'm very happy with the comments!.. 20ft container

    ReplyDelete