CSC/ECE 517 Fall 2011/ch1 1b ds

Cover the history of Collections frameworks back to the late 1970s or early 1980s, and how they were retrofitted to various languages. Discuss the advantage of a standard Collections framework (e.g., Java) vs. several competing frameworks (e.g., C++), and the advantage of collections built into the language (e.g., Ruby) vs. collections as class libraries. Give examples to illustrate the advantages you identify.

Authors

• Dilip Devaraj
• Srinath Sridhar

Java Collections Framework (JCF)

Java Collections Framework— is a library of classes that implement collections. The collections framework also provides utility methods to perform functions such as sorting a list of data. If you need to store instances of your own class in some types of collection then we need to employ hashing by writing our own hashCode and equals method.

The collections in Java are mainly the following List, Set, Map and Queue. Java provides these collections as interfaces from which one can write their own classes or can use the inbuilt Java classes that implement these interfaces.

List

List is a collection of objects that has a fixed order (when we add an object to the list, it will stay in the place we put it), and allows objects to be referred to by position.Duplicate elements are allowed in a list. The general-purpose List implementations are ArrayList and LinkedList. List<String> myList = new ArrayList<String>();

Set

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction.The Java platform contains three general-purpose Set implementations: HashSet, TreeSet, and LinkedHashSet.

Map

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. Maps are defined by the java.util.Map interface in Java. The three general-purpose Map implementations are HashMap, TreeMap and LinkedHashMap. The java.util.Map interface is extended by its subinterface, java.util.SortedMap. This interface defines a map that's sorted by the keys provided.

Queue

A Queue is a collection for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, removal, and inspection operations. LinkedList implements the Queue interface, providing first in, first out (FIFO) queue operations.

C++ Standard Template Library(STL)

C++ standard template library is a software library that provides implementations of some basic containers for storing collections of related objects as well as algorithms to perform operations on the elements in these containers. All the classes in C++ STL are generic and can be used with any user defined or primitive data types. In general the C++ STL has four major components.

Containers

These are classes which are used to store other objects. Taking an example suppose there is a “jar of jellybeans”, the jar can be thought of as the container while the jelly beans are the objects that are stored in the container. Most collections automatically resize depending on the number of elements in them.The C++ STL provides a number of such classes which can be classified into two categories

Sequence Containers

These containers impose a strict linear order on the elements. Sequence containers support insertions and deletions (either at the ends or at a random position) using an index. Some examples of sequence containers are vector, list, dequeue etc.

Associative containers

These containers store key value pairs and each object stored in an associative container is mapped to a specific key. In other words associative containers perform insertions and deletions based on a key. Some examples of associative containers are set, map, hash map, multiset etc.

Algorithms

The C++ STL contains a large collection of algorithms that can be used to manipulate the data contained in the container. Continuing from the earlier “jar of jelly beans” example, suppose you wanted to count the number of red colored jelly beans. Or you wanted to change the color of all the jelly beans to red the algorithms in STL allow you to accomplish this.

An important thing to note is that the algorithms in STL are decoupled from the container. This means that there is only one definition of the function which implements the algorithm. This works for any valid container containing any any valid set of objects. Analogous to our example the function to count the number of red jelly beans also works for a “bucket containing colored pebbles”.

The algorithms contained in STL can be classified into two categories

Non-Mutating

Those which do not change the collection in any way. Examples include count, find, for each etc.

Mutating

Those which modify the contents of the collection in some way. Examples include replace, copy, reverse etc.

Iterators

Iterators are an important part of the C++ STL. Iterators facilitate traversal through a container’s elements. The separation of algorithms from containers is achieved through the use of iterators. Iterators can be thought of as a generalization of pointers. All the algorithms make use of iterators as function arguments. There are 5 types of iterators in STL. These differ in the way they traverse through the elements in the container.

Functor

A functor or functional object is an object that can be called as a function. This is in essence similar to function pointers in C. A functor is any class that overloads the operator() function. Such a class is most commonly used to define custom comparison functions to compare two objects. This is similar to “comparator” in JAVA.