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.

JCF vs STL

Quality of implementation

Java is standardised and have formalized methods such as Java community process(JCP) and Java Specification request (JSR) to define revisions of java platforms. C++ only gives a defining standard and one can have different implementations of that standard. Hence different implementations can be incompatible.

Portability

This is a direct consequence of the fact that standards are available in Java and not in C++. The following is a list of various STL libraries(link http://en.wikipedia.org/wiki/List_of_C%2B%2B_template_libraries). These may have some common templates which might not necessarily be interoperable. In contrast the implementations of JCF are standardized and they will be portable as long as versions remain the same.

Better optimization of containers

In C++ STL the algorithms (i.e functions which manipulate the data) are completely decoupled from the containers it is not possible to optimize containers for specific purposes. In JCF since the algorithms are defined as interfaces it is easy to provide specific implementations based on requirements. Because the various implementations of each interface are interchangeable, programs can be easily tuned by switching implementations. The only way to optimize in STL is to create new containers which are tied together with the algorithms.

Fosters software reuse

By providing a standard interface for collections and algorithms to manipulate them

More number of methods in STL

STL has more number of methods than Java for collections. This is becasue STL has separate methods for containers and algortihms used for containers like Non-mutating algorithms, Mutating algorithms, Sorting http://www.sgi.com/tech/stl/table_of_contents.html

Collections in Java are more extensible than in STL

STL collections are difficult to extend as the base classes are not declared as virtual. In Java since the basic collections are interfaces, it is easy to implement the interfaces in a class, and extend from that.

Manipulation of container objects using Iterators

C++ STL uses iterators to iterate through the items. Iterators themselves are generalizations of pointers. This leads to problems when one has to manipulate the items in the container, especially if the items have to be removed. It is tricky to iterate through the container and delete objects within the same loop. This is not the casein java since memory cannot be directly manipulated by the programmer.

Pass by reference Vs Pass by value

Containers in STL is accessed using copy semantics, thereby providing both efficiency and type safety, while in Java collections are accessed via references (or pointers). In Java if an one tries to access an object of a container that was just deleted , since we are using a reference this would result in error.