{"id":257,"date":"2015-12-11T08:07:16","date_gmt":"2015-12-11T05:07:16","guid":{"rendered":"https:\/\/sobbayi.com\/?p=257"},"modified":"2015-12-11T08:07:16","modified_gmt":"2015-12-11T05:07:16","slug":"the-cpp-standard-template-library-associative-containers-part-4","status":"publish","type":"post","link":"http:\/\/local.brightwhiz\/the-cpp-standard-template-library-associative-containers-part-4\/","title":{"rendered":"The C++ Standard Template Library Associative Containers – Part 4"},"content":{"rendered":"

Welcome to the third tutorial in the C++ Standard Template Library series featuring Associative Containers. In our previous tutorial we discussed about the Sequence Containers focusing on the linked list, deque and STL array<\/a>.<\/p>\n

We also saw the inner workings of the vector, list, forward list, deque and array classes and how they can be used in the C++<\/a> Standard Template Library. <\/p>\n

In case you missed the beginning of this series, you can get up to speed on the overview of the C++ Standard Template Library<\/a> so as to get up to speed with what is being discussed here.<\/p>\n

What are Associative Containers in C++ STL?<\/h2>\n

An associative container in STL<\/a> is a container where each element of the container has a value that is associated with a key. In some cases the key and value can be the same while in other cases they can be of different values.<\/p>\n

The properties of these key\/value pairs will be discussed more in depth when we look at the different types of Associative Containers.<\/p>\n

These containers consist of the following. Set, Multiset, Map, and Multimap. Their characteristics will be highlighted shortly.<\/p>\n

Associative Containers Implementation<\/h2>\n

These containers are always implemented using a binary tree and are always sorted ascending. The sorting is done internally and automatically, therefore, an element is always inserted in its proper place all the time. Likewise, when an element is removed from the container, the remaining elements will be resorted to keeping the tree in the correct order all the time.<\/p>\n

\"Binary<\/a>
Visualization of a C++ STL Binary Tree Set Associative Containers<\/figcaption><\/figure>\n

Set<\/h2>\n

The major characteristics of a set is that the elements contained within it must be unique.There are a few characteristics to note about the set.<\/p>\n

    \n
  • A set does not allow duplicate elements.<\/li>\n
  • Insertions into a set is fast and takes logarithmic time as opposed to linear time like the sequence containers<\/li>\n
  • Traversing a set is slow<\/li>\n
  • Finding an element is also faster than sequence containers by taking logarithmic time<\/li>\n
  • When inserting elements into the set with the “insert”\u00a0 method, it returns a pair. The first element is pointer to the new element. If the element already existed it returns a pointer to the existing duplicate. The second element is a boolean that returns true if successful and false if the element already exists<\/li>\n
  • Elements cannot be modified<\/li>\n
  • Set does not allow random access and does not have the []<\/code> operator<\/li>\n<\/ul>\n

    Some Examples of the Set usage.<\/p>\n