CSC/ECE 517 Fall 2011/ch1 1b sa
==Advantages of Collections in Java vs C++ : Let us see some of the features that makes Collections framework to rule over other competing frameworks such as STL and JGL. Collections framework is a core Java framework used to provide various data structures and algorithms and an API to access them. STL is a similar framework which is supports C++ and JGL is the decedent of STL in Java. ===Package Organization: Packaging is one of the important factor that reveals the quality and amount of thought that was put on the developing the library. The difference in the number of classes shows the major advantage of the Collection framework over the STL/JGL which makes the task simpler with less number of classes to know about. ===Iterator interface hierarchies: Table clearly shows the interface hierarchy in Collections is lot simpler than STL/JGL. The complex approach of STL often leads to developer’s headache due to numerous permutations of incompatible iterators. ====Range view Selection: Iterators in JGL point to elements. JGL uses these pointers to select a sub range of a container. When we add or remove an element, any iterator pointing to it gets invalidated. So, clearly, JGL doesn't let its iterators remove or add elements because such a capability would sabotage most of its range-based algorithms. More than half of the algorithms doesn’t support the operations on sub range of container instead they work on entire container wasting their time. In contrast iterators in Collections point between elements and have an easier approach for selecting sub range in a collection using indices of elements. ===Synchronization: In the view of multithreaded environment, all the STL/JGL containers are synchronized which means operations cannot be parallelized and is a certain issue of overhead and performance. Whereas Collections are not synchronized by default but if required provides a thread safe wrapper around the unsynchronized collection. ===Implementation of Collection/Container entities: ====ArrayList : ArrayList is a resizable form of an Array. Equivalent of ArrayList in STL is vector. When ArrayList constructor ArrayList(int n) is invoked, it creates an empty container and pre allocated space for n elements. So when size method is invoked at this point it returns 0. When a similar constructor of Vector is invoked it creates a container of n elements initialized to 0. So when a size method is invoked it returns n. Adding an element at the beginning in ArrayList takes less time than vector because STL’s vector must shift all the n elements before adding a new element. C++ vectors does not support in-place reallocation of memory i.e upon reallocation memory held by vector is copied to a new location by the element’s copy constructor and later releasing the memory which is an inefficient process.
- example*
====Maps: Maps in Collections framework are internally implemented using arrays. So time taken for accessing, removing a key or checking whether the key is present in the map would be done in the order O(1) i.e in constant time. Initially maps are initiated to a desired size or default size of 10, so until the resizing of the map it would take constant time i.e O(1) and if size is exceeded it would take linear time in the order of input to resize the map i.e O(n). Maps in STL/JGL are internally implemented using self-balancing binary search trees (AVL or Red Black trees). So time taken for accessing, adding, removing a key or checking whether the key is present in the map would be done in the order O(log n).
- Table here *
====Sets: Sets are internally represented using binary search trees in STL so the operations such as adding, removing an element, checking whether an element is there or not can be performed in the order of O(log n). http://en.wikipedia.org/wiki/Set_%28computer_science%29 Sets in CF are implemented as HashSet, TreeSet, SortedSet through maps, binary search trees. HashSet implementation of set can perform set operations such as adding, removing an element, checking whether an element is there or not can be performed in the order of O(1). http://www.cis.usouthal.edu/~hain/general/Publications/oopsla-paper6.pdf Set operations such as set union, difference and intersection in STL takes more space and time than in Collections framework. Because when these operations are performed on two sets, result is stored in the first set in CF whereas a new set is created and stored in it. // Create the sets Set set1 = new HashSet(); Set set2 = new HashSet();
// Add elements to the sets ...
// Copy all the elements from set2 to set1 (set1 += set2) // set1 becomes the union of set1 and set2 set1.addAll(set2);
// Remove all the elements in set1 from set2 (set1 -= set2) // set1 becomes the asymmetric difference of set1 and set2 set1.removeAll(set2);
// Get the intersection of set1 and set2 // set1 becomes the intersection of set1 and set2 set1.retainAll(set2);
// Remove all elements from a set set1.clear();
http://www.exampledepot.com/egs/java.util/coll_SetOps.html
===Compilation and executable size: STL is majorly dependent on templates. As compilers generate additional amount of code for each template type, indiscriminate usage of templates leads to code bloat which results in generation of large executable files. ===Readability: Code tends to lose its readability when there is a need of lot of new classes to perform a task and if this task involves templates it even makes the code complex and virtually unmaintainable. In contrast readability in Java using Collections framework is far better as it performs the task with a minimal set of classes and interfaces. ===Debugging: STL has far less support for debugging when compared to Java’s Collection framework. The error messages generated by the template code are far from being readable; one has to get acquainted with these to understand them. ===It's either in the core, or it isn't: One of the big advantages of Collections framework over its competing frameworks like STL, JGL which would dwarf any advantage is it is a product of Sun and has been given core status. So any new user of one of these frameworks would certainly go for the one which has “brand” tag attached it.