Lecture Seven

Generic Class, STL and Collection Framework

C++ & Java

© Dr. Mohammad Mahfuzul Islam, PEng

Professor, Dept. of CSE, BUET
 Generic Class
➢ Many classes, interfaces or methods are logically same but uses various types of data like integer,
double or string. For example, a stack.

➢ Generic class, interface or method uses type parameter It is recommended that type parameter names
be single character capital letter like T, V and E.

➢ Java does not allow a primitive type as a type parameter. However, it’s not a serious problem due
having wrappers to encapsulate each primitive type. Java’s autoboxing and auto-unboxing makes the
use of wrapper transparent.

➢ When code with generic class, interface or method is compiled, all generic type information is removed
and type parameter is replaced with compatible type. This is known as Erasure.

➢ A generic class cannot extend Throwable. This means that you cannot create generic exception classes.
2
 Generic Class
#include <iostream> int main(){
using namespace std; Gen<int> iob(88);
iob.showType();

C++ Code
template <typename T>
class Gen{
cout << "Value: " << iob.getob() << endl;
T ob;
public: Gen<double> dob(22.22);
Gen(T o){ ob = o;} dob.showType();
T getob(){ return ob;} cout << "Value: " << dob.getob() << endl;
void showType();
}; Gen<char *> cob("Template Test");
template <class T>
cob.showType();
void Gen<T>::showType(){ cout << "Value: " << cob.getob() << endl;
cout << "Type: " <<typeid(ob).name()<<endl;
} // iob = cob; // Error: incompatible types
OUTPUT:
Type of T is: i return 0;
Value: 88 }
Type of T is: d
template <typename T>
Value: 22.22
Type of T is: Pc can also be used instead of
Value: Template Test template <class T> and Vice-Versa
3
 Generic Class
class Gen <T>{
T ob;
Gen(T o){ ob = o; }
T getOb(){ return ob;}
void showType(){
System.out.println("Type of T: "+ob.getClass().getName());
}
}
OUTPUT:
Java Code

public class Main {

public static void main(String[] args) { Type of T: java.lang.Integer
Gen<Integer> iOb = new Gen<Integer>(88); Value: 88
iOb.showType(); Type of T: java.lang.String
int v = iOb.getOb(); value: Generic Test.
System.out.println("Value: " + v);

Gen<String> strOb = new Gen<String>("Generic Test.");

strOb.showType();
String str = strOb.getOb();
System.out.println("value: "+str);
}
}
4
 Type Inference and Local Variable Type Inference in Java
Consider A Declaration: class Gen <T>{
Gen<Integer> iOb = new Gen<Integer>(88); T ob;
Gen(T o){ ob = o; }
Repetition of Integer can be avoided in two ways: T getOb(){ return ob;}
void showType(){
(a) Type Inference;
System.out.println("Type of T: "+ob.getClass().getName());
(b) Local variable Type Inference }
}
(a) Type Inference: public class Main {
public static void main(String[] args) {
Repetition of Integer can be avoided using <>, which is Gen<Integer> iOb = new Gen<>(88);
known as the diamond operator. iOb.showType();
int v = iOb.getOb();
Gen<Integer> iOb = new Gen<>(88); System.out.println("Value: " + v);

var strOb = new Gen<String>("Generic Test.");

(b) Local variable Type Inference: strOb.showType();
String str = strOb.getOb();
Repetition of Integer can be avoided local variable var. System.out.println("value: "+str);
}
var iOb = new Gen<Integer>(88); }
5
 Using Object instead of Generic Class in Java
class NonGen{
Object ob; OUTPUT:
NonGen(Object o) { ob = o; } Type: java.lang.Integer
Object getOb(){ return ob;} Value: 88
void showType(){ Type: java.lang.String
System.out.println("Type: "+ob.getClass().getName()); Value: NonGenDemo
} Exception in thread "main"
}
java.lang.ClassCastException: class
public class Main { java.lang.String cannot be cast to
public static void main(String[] args) { class java.lang.Integer
NonGen iOb = new NonGen(88); (java.lang.String and
iOb.showType(); java.lang.Integer are in module
int v = (Integer) iOb.getOb(); java.base of loader 'bootstrap')
System.out.println("Value: "+v); at Main.main(Main.java:21)
NonGen strOb = new NonGen("NonGenDemo");
strOb.showType(); Two Problems:
String str = (String) strOb.getOb();
✓ Explicit casts must be employed to retrieve the stored
System.out.println("Value: "+str);
data.
iOb = strOb; ✓ Many kinds of type mismatch errors cannot be found
v = (Integer) iOb.getOb(); until runtime.
}
}
6
 Generic Class with More Type Parameters
class Gen<T, V>{
#include <iostream>
T ob1; V ob2;
using namespace std;
Gen(T o1, V o2){ ob1 = o1; ob2 = o2; }
T getOb1(){ return ob1; }

C++ Code
template <class T, class V>

Java Code
V getOb2(){ return ob2; }
class Gen{
void showType(){
T ob1; V ob2;
System.out.println("Type of T: "+ob1.getClass().getName());
public:
System.out.println("Type of V: "+ob2.getClass().getName());
Gen(T o1, V o2){ ob1 = o1; ob2 = o2;}
}
T getob1(){ return ob1;}
}
V getob2(){ return ob2;}
public class Main {
void showType(){
public static void main(String[] args) {
cout << "Type of T is: " << typeid(ob1).name() << endl;
Gen<Integer, String> ob = new Gen<>(88, "Double Type
cout << "Type of V is: " << typeid(ob2).name() << endl;
Parameters");
}
ob.showType();
};
System.out.println("Value: "+ob.getOb1());
System.out.println("Value: "+ob.getOb2());
int main(){
}
Gen<int, char *> iob(88, "Double Type Parameters");
}
iob.showType();
cout << "Value: " << iob.getob1() << endl;
cout << "Value: " << iob.getob2() << endl;
OUTPUT:
Type of T is: i
return 0; Type of V is: Pc
} Value: 88
Value: Double Type Parameters 7
 Bounded Type Parameters in Java
class Stats<T extends Number>{
T[] nums;
Stats(T[] o){ nums = o; }
How can a method average() double average(){
double sum = 0.0;
be added in a generic class? for( T num: nums )
sum += num.doubleValue();
return sum / nums.length;
}
}
Bounded Type Parameters public class Main {
public static void main(String[] args) {
Integer[] inums={1, 2, 3, 4, 5};
Stats<Integer> iOb = new Stats<>(inums);
System.out.println("Integer Avg: " + iOb.average());

Double[] dnums = {2.3, 3.5, 4.3, 1.6, 9.4};

OUTPUT: Stats<Double> dOb = new Stats<>(dnums);
System.out.println("Double Avg: " + dOb.average());
Integer Avg: 3.0
Double Avg: 4.220000000000001 // double[] str ={"One", "Two", "Three"};
// Stats<String> strOb = new Stats<String>(str);
}
}
8
 Using Wildcard <?> Arguments
Method “isSameAvg()” to check
whether average of Integer array is same as the average of Double array.
class Stats<T extends Number>{ public class Main {
T[] nums; public static void main(String[] args) {
Stats(T[] o){ nums = o; } Integer[] inums = {2, 4, 6, 8};
double average(){ Stats<Integer> iOb = new Stats<>(inums);
double sum = 0.0; Double[] dnums = {2.0, 4.0, 6.0, 8.0};
for(T num: nums) Stats<Double> dOb = new Stats<>(dnums);
sum += num.doubleValue(); if (iOb.isSameAvg(dOb))
return sum / nums.length; System.out.println("Same Avg.");
} else System.out.println("Different Avg.");
boolean isSameAvg(Stats<T> ob){ }
if (average() == ob.average()) }
return true;
return false; Solution: wildcard
} boolean isSameAvg(Stats<?> ob){
} …………………………
OUTPUT: }
java: incompatible types: Stats<java.lang.Double>
cannot be converted to Stats<java.lang.Integer>
9
 Bounded Wildcard <?>
class TwoD{ public class Main {
int x, y;
TwoD(int a, int b) { x = a; y = b; } static void showXY( Coords<?> c){
} System.out.println("X Y Coordinate:");
for (TwoD coord: c.coords )
class ThreeD extends TwoD{ System.out.println(coord.x+" "+coord.y);
int z; }
ThreeD(int a, int b, int c){
super(a, b); static void showXYZ( Coords<? extends ThreeD> c){
z = c; System.out.println("X Y Z Coordinates:");
} for(ThreeD coord: c.coords){
} System.out.println(coord.x + " "+coord.y+" "+ coord.z );
}
class FourD extends ThreeD{ }
int t;
FourD(int a, int b, int c, int d){ static void showAll( Coords<? extends FourD> c){
super(a, b, c); System.out.println("X Y Z T Coordinates:");
t = d; for (int i = 0; i < c.coords.length; ++i){
} System.out.println(c.coords[i].x+" "
} +c.coords[i].y+" "
+c.coords[i].z+" "
class Coords<T extends TwoD>{
+c.coords[i].t);
T[] coords; }
Coords(T[] o) { coords = o; }
}
}
10
 Bounded Wildcard <?>
public static void main(String[] args) { OUTPUT: What Happens?
TwoD[] td = { new TwoD(0, 0), X Y Coordinate:
new TwoD(4,5)}; 0 0 static void showXY( Coords<?
FourD[] fd ={ new FourD(3, 4, 5, 6), 4 5 Extends TwoD> c)
new FourD(7, 4, 3, 8), X Y Coordinate:
new FourD(9, 3, 6, 2)}; 3 4 What Happens?
7 4
Coords<TwoD> tdOb = new Coords<>(td); 9 3 static void showXYZ( Coords<?
Extends TwoD> c)
Coords<FourD> fdOb = new Coords<>(fd); X Y Z Coordinates:
3 4 5 Error:
showXY(tdOb); 7 4 3 java: incompatible types: capture#1 of ?
// showXYZ(tdOb); 9 3 6 extends TwoD cannot be converted to ThreeD
// showAll(tdOb); X Y Z T Coordinates:
3 4 5 6
showXY(fdOb); 7 4 3 8
showXYZ(fdOb); 9 3 6 2
showAll(fdOb);
showXZY(tdOb);
}
}
OUTPUT:
java: incompatible types: Coords<TwoD> cannot be
converted to Coords<? extends ThreeD> 11
 Generic Function / Method
#include <iostream> int main(){
using namespace std; int i = 10, j = 20;
float x = 10.1, y = 23.3;
template <typename T> char a = 'x', b = 'y’;

C++ Code
void swapargs(T &a, T &b){
T temp = a; swapargs(i, j);
a = b; cout << i << " " << j << endl;
b = temp;
} swapargs(x, y);
cout << x << " " << y << endl;
void swapargs(int &a, int &b){
int temp = a; swapargs(a, b);
a = b; cout << a << " " << b << endl;
b = temp;
cout << "Non-Generic swap" << endl; Gen g;
} g.showType(i); OUTPUT:
g.showType(x); Non-Generic swap
class Gen{ //non-generic class g.showType(a); 20 10
public: 23.3 10.1
template <typename T> return 0;
}
y x
void showType(T &a){
Type: i
cout << "Type: " << typeid(a).name() << endl;
} Type: f
}; Type: c
12
 Generic Method in Java
public class Main { ❖ The Type Parameters is declared before
static <T extends Comparable<T>, V extends T>
boolean isIn(T x, V[] list){
the return type of a method.
for(T y: list) ❖ Comparable is a Generic Interface
if (x.equals(y)) return true;
return false; defined in java.lang and its Type
} Parameter specifies the type of objects
that that it compares.
public static void main(String[] args) {
Integer[] nums = {2, 4, 6, 7, 8, 3, 5};
String[] strs ={"One", "Two", "Three"};

if (isIn(2, nums))
System.out.println("2 is in nums");

if (isIn("Two", strs))
System.out.println("Two is in strs");
}
} OUTPUT:
2 is in nums
Two is in strs 13
 Generic Constructor
#include <iostream> class GenCons{
using namespace std; private double val;

Java Code
class GenCons{ <T extends Number>

C++ Code
double val; GenCons(T arg){
public: val = arg.doubleValue();
template <typename T> }
GenCons(T arg){ public void showVal(){
val = arg; System.out.println("Val: "+val);
} }
void showVal(){ }
cout << "Val: " << val << endl; public class Main {
} public static void main(String[] args) {
}; GenCons iVal = new GenCons(100);
GenCons dVal = new GenCons(25.6);
int main(){ iVal.showVal();
GenCons iVal(100); dVal.showVal();
GenCons dVal(25.6); }
}
iVal.showVal(); OUTPUT:
dVal.showVal(); Val: 100
} Val: 25.6 14
 Generic Interface
interface MinMax<T extends Comparable<T>>{
T min(); public class Main {
T max(); public static void main(String[] args) {
} Integer[] iVals = {2, 4, 3, 1, 7, 9, 6};
String[] sVals = {"One", "Two", "Three", "Four"};
class MyClass <T extends Comparable<T>>
implements MinMax<T>{ MyClass<Integer> iOb = new MyClass<>(iVals);
T[] list; MyClass<String> sOb = new MyClass<>(sVals);

MyClass(T[] cList){ list = cList; } System.out.println("Min in iVals: "+ iOb.min());

System.out.println("Max in iVals: "+ iOb.max());
public T min(){ System.out.println("Min in sVals: "+ sOb.min());
T val = list[0]; System.out.println("Max in sVals: "+ sOb.max());
for(T x: list) }
if (x.compareTo(val) < 0) val = x; }
return val;
}
OUTPUT:
public T max(){ Min in iVals: 1
T val = list[0]; Max in iVals: 9
for(T x: list) Min in sVals: Four
if (x.compareTo(val) > 0) val = x; Max in sVals: Two
return val;
}
} 15
 Generic in Inheritance
#include <iostream> template <class T, class V>
using namespace std; class Gen2D : public Gen<T>{
V ob;
class NonGen{ public:
int num; Gen2D(int n, T o, V o2) : Gen<T>(n, o){ ob = o2; }
public: V getob(){ return ob; }
NonGen(int n){ num = n; } void show(){
void show(){ cout << "Gen2D: " << ob << endl;
cout << "NonGen: " << num << endl; }

C++ Code
} };
};
int main(){
template <class T> NonGen ob(10);
class Gen : public NonGen{ Gen<char> ob1(20, 'A’);
T ob; Gen2D<double, char *> ob2(40, 60.5, "Gen2 Object");
public:
ob.show();
Gen(int n, T o) : NonGen(n){ ob = o; }
ob1.show();
OUTPUT:
T getob(){ return ob; } NonGen: 10
void show(){ ob2.show();
Gen: A
cout << "Gen: " << ob << endl;
} cout << ob1.getob() << endl; Gen2D: Gen2 Object
}; cout << ob2.getob() << endl; A
return 0; Gen2 Object
}
16
 Generic in Inheritance
class NonGen{
public class Main {
private int num;
public static void main(String[] args) {
NonGen(int n) { num = n;}
NonGen ob = new NonGen(10);
public void show(){
Gen<Character> ob1 = new Gen<>(20, 'A');
System.out.println("NonGen: "+num);
Gen2<Double, String> ob2 = new Gen2<>(40, 60.5, "Gen2 Object");
}
}
ob.show();
ob1.show();
class Gen<T> extends NonGen{
ob2.show();
private T ob;
Gen(int n, T o){ super(n); ob = o; }
System.out.println(ob1.getOb());
public T getOb(){ return ob; }
System.out.println(ob2.getOb2());
public void show(){
}
System.out.println("Gen: "+ob);
}
}
}
OUTPUT:
class Gen2<T, V> extends Gen<T>{ NonGen: 10
private V ob;
Gen: A
Gen2(int n, T o1, V o2){ super(n, o1); ob = o2; }
public V getOb2(){ return ob; } Gen2D: Gen2 Object
public void show(){ A
System.out.println("Gen2: "+ob); Gen2 Object
}
}
17
Standard Template Library(STL)
C++

18
 STL Items

At the core of Standard Template Library (STL) are three fundamental Items:
Containers, Algorithms and Iterators.
❖ Containers: containers are objects that hold other objects.
❖ Algorithms: algorithms act containers. Their capabilities includes initialization, sorting,
searching and transforming the contents of containers.
❖ Iterators: iterators are objects that act like pointer to the contents of a container with the
ability to cycle.

➢ Besides these three Items, STL relies upon some standard components like allocators, predicates,
comparison functions and function objects.
➢ In addition to the headers required by the various STL classes, the C++ standard library includes the
<utility> and <functional> headers, which provide support for the STL.

19
 Containers

Containers

bidirectional None
Some examples of Containers

Sequence Containers Associative Containers Container Adaptors

(linear list) (allow efficient retrieval of (transforms one thing to
values based on keys) another)
vector (random access)
stack
array (random access)
Ordered Associative Unordered Associative queue
deque (random access)
Containers Containers priority_queue
list (bidirectional)
set unordered_set
forward_list (forward)
multiset unordered_multiset
map unordered_map
multimap unordered_multimap

20
 Some functions associated with Containers
Some commonly used functions:
Function Purpose Containers Applicable
insert() Insert an elements Sequence containers, Associative containers
erase() Remove elements Sequence containers, Associative containers
push_back() Add an element at the end. Sequence containers
pop_back() Remove an element from the end Sequence containers
push_front() Add an element at the start. list and deque containers
pop_front Remove an element from the start list and deque containers
size() Return the current size of the container Sequence containers, Associative containers
sort() Sort data within the range in custom order Array, vector, deque, etc.
merge() Combine two sorted ranges.
empty()
clear()
make_pair()
21
 typedef defined in STL
Some of the most common typedef names defined in STL:
Containers Applicable
size_type Some type of integer
Reference A reference to an element ➢ Overloaded operators <, <=,
>, >=, == and != perform
const_reference A const reference to an element
element-by-element
iterator An iterator comparisons.
const_iterator A const iterator
reverse_iterator A reverse iterator ➢ Overloaded operators <, <=,
const_reverse_iterator A const reverse iterator > and >= are not provided
for the unordered
value_type The type of a value stored in a container
associative containers.
allocator_type The type of the allocator
key_type The type of a key
key_compare The type of a function that compares two keys
value_compare The type of a function that compares two values
22
 Iterators
➢ Iterators are objects that like pointers. Random Access
There are five types of iterators:
Iterator Actions Direction Bidirectional
Random Access Store and Retrieve values Elements may be accessed randomly.
Bidirectional Store and Retrieve values Forward and Backward moving Forward
Forward Store and Retrieve values Forward moving only.
Input Retrieve, but not Store Forward moving only.
Output Store, but not Retrieve Forward moving only. Input Output

There are five types of iterators:

Function Purpose Containers Applicable
begin() Return iterator to the start Sequence Containers, Associative Containers
end() Return iterator to the end (last element: end()-1) Sequence Containers, Associative Containers
find() Locate an element given its key Associative Containers
23
 Some Sample Codes
Sample Definition of a Container (vector):
vector<int> iv; // create zero-length int vector
vector<char> cv(5); // create 5-element char vector
vector<char> cv(5, 'x’); // initialize a 5-element char vector
vector<int> iv2(iv); // create int vector from an int vector

Sample Definition of Iterator:

vector<char>::iterator p; // create an iterator

Sample code for a Container:

vector<char> v2;
char str[] = "<Vector>";
for(int i=0; str[i]; i++) v2.push_back(str[i]);

Sample insert() and erase() code:

v.insert(p, 10, 'X’); // insert 10 ‘X’ into V starting from p
v.insert(p, v2.begin(), v2.end()); // insert v2 into v
v.erase(p, p+10); // remove next 10 elements starting from p
24
 A Sample Program using vector
#include <iostream> v.insert(p, 3, 'Y’);
#include <vector> for(int i = 0; i < v.size(); i++){
using namespace std; cout << v[i] << " ";
}
int main(){ cout << endl;
vector<char> v;
vector<char>::iterator p; p = v.begin();
p += 3;
if (v.empty()){ v.erase(p, p+3);
cout << "Vector is empty" << endl; for(int i = 0; i < v.size(); i++){
} cout << v[i] << " ";
}
for(int i = 0; i < 10; i++){ cout << endl;
v.push_back(i+'A’);
} v.clear();
cout << "Size: " << v.size() << endl;
p = v.begin();
while(p != v.end()){ return 0;
cout << *p << " "; } OUTPUT:
p++; Vector is empty
} A B C D E F G H I J
cout << endl; A B C D E F G X Y Y Y H I J
A B C G X Y Y Y H I J
p = p-3;
Size: 0
v.insert(p++, 'X’);
25
 A Sample Program using list
#include <iostream> p = lst1.begin(); lst1.sort();
#include <list> while(p != lst1.end()){ p = lst1.begin();
using namespace std; cout << *p << " "; while(p != lst1.end()){
p++; cout << *p << " ";
int main(){ } p++;
list<int> lst1, lst2; cout << endl; }
list<int>::iterator p = lst1.begin(); cout << endl;
for(int i = 0; i < 3; i++){
for(int i = 0; i < 5; i++){ lst2.push_back(i+20); return 0;
lst1.push_back(2*i); } }
lst2.push_front(2*i+1);
} lst1.splice(lst1.end(), lst2);
cout << "Size1: " << lst1.size() << " ";
lst1.merge(lst2); cout << "Size2: " << lst2.size() << endl;
p = lst1.begin();
while(p != lst1.end()){ p = lst1.begin();
cout << *p << " "; while(p != lst1.end()){
p++; cout << *p << " "; OUTPUT:
} p++; 0 2 4 6 8 9 7 5 3 1
cout << endl; } Size1: 10 Size2: 0
cout << "Size1: " << lst1.size() << " "; cout << endl; 1 3 5 7 9 8 6 4 2 0
cout << "Size2: " << lst2.size() << endl; Size1: 13 Size2: 0
1 3 5 7 9 8 6 4 2 0 20 21 22
lst1.reverse(); 0 1 2 3 4 5 6 7 8 9 20 21 22
26
 A Sample Program using map
p = myMap.find('M’);
#include <iostream> if(p != myMap.end()){
#include <map> cout << "Found: " << p->first << " "
using namespace std; << p->second << endl;
} else {
int main(){ cout << "Not found" << endl;
map<char, char*> myMap; }
map<char, char*>::iterator p;
return 0;
myMap.insert(pair<char, char*>('J', "John")); }
myMap.insert(pair<char, char*>('P', "Paul"));
myMap.insert(make_pair<char, char*>('L', "Linda"));
myMap.insert(make_pair<char, char*>('M', "Mike"));
OUTPUT:
J John
L Linda
p = myMap.begin(); M Mike
while(p != myMap.end()){ P Paul
cout << p->first << " " << p->second << endl;
p++; Found: M Mike
}
cout << endl;

27
 Algorithms
Algorithms act on containers. Header <algorithm> should be included.
Some Algorithms:
Name Format Explanation
count() int n = count(v.begin(), v.end(), val) Returns the number of elements in the sequence beginning
at v.begin() and ending at v.end() that match val
count_if() int n = count_if(v.begin(), v.end(), Returns the number of elements in the sequence beginning
even) at v.begin() and ending at v.end() for which the unary
predicate even returns true
remove_copy() remove_copy(v.begin(), v.end(), Copies elements from the specified range, i.e., from v.begin()
back_inserter(v2), val) to v.end() that are not equal to val and puts the results into
the sequence pointed by v2.begin()
reverse() reverse(v.begin(), v.end()) Reverse the order of the range specified
transform() transform(v.begin(), v.end(), Modifies each element in the range specified according to the
v.begin(), xform) function xform

28
 Example Program using Algorithms
#include <iostream> for(int i = 1; i < 6; i++){
#include <list> myList.push_back(i * 3);
#include <algorithm> myList.push_front(i * 4);
using namespace std; }

bool even(int n){ for(p = myList.begin(); p != myList.end(); p++){

if (n % 2 == 0) return true; cout << *p << " ";
return false; }
} cout << endl;

int square(int n){ int n = count(myList.begin(), myList.end(), 12);

return n * n; cout << "12 appears " << n << " times" << endl;
}
n = count_if(myList.begin(), myList.end(), even);
int main(){ cout << n << " even numbers." << endl;
list<int> myList;
list<int>::iterator p; remove_copy(myList.begin(), myList.end(),
list<int> v2; back_inserter(v2), 12);
list<int>::iterator q;

29
 Example Program using Algorithms
for(q = v2.begin(); q != v2.end(); q++){
cout << *q << " ";
}
cout << endl;
OUTPUT:
reverse(v2.begin(), v2.end()); 20 16 12 8 4 3 6 9 12 15
for(q = v2.begin(); q != v2.end(); q++){ 12 appears 2 times
cout << *q << " "; 7 even numbers.
} 20 16 8 4 3 6 9 15
15 9 6 3 4 8 16 20
cout << endl;
225 81 36 9 16 64 256 400

transform(v2.begin(), v2.end(), v2.begin(), square);

for(q = v2.begin(); q != v2.end(); q++){
cout << *q << " ";
}
cout << endl;

return 0;
}

30
Collection Framework
Java

31
 Collection Framework

➢ The Collections Framework is a sophisticated hierarchy of interfaces and classes that provide
state-of-the-art technology for managing groups of objects. Package: java.util
➢ Three items of Collection Framework: Collections (Interfaces & Classes), Iterators and
Algorithms.
➢ Goals of Collection Framework:
✓ High efficiency and high performance

✓ Different types of collections to work in a similar manner and with a high degree of interoperability

✓ Easy extending/adapting a collection.

➢ Legacy of ad-hoc classes before Collections: Dictionary, Vector, Stack and Properties.
➢ In addition to Collection interfaces, Collections also use Comparator, RandomAccess, Iterator,
ListIterator and Spliterator.
32
 Collections
Interfaces Classes AbstractCollection

Extending Hierarchy
Iterable

AbstractList AbstractQueue AbstractSet ArrayDeque

Extending hierarchy
Collection

AbstractSequentialList ArrayList EnumSet HashSet TreeSet

List Queue Set
PriorityQueue

LinkedList LinkedHashSet
Deque SortedSet
Implementation:
NavigableSet ✓ AbstractCollection, AbstractList, AbstractQueue and AbstractSet
implement Collection, List, Queue and Set, respectively.
✓ ArrayDeque implemts Deque. 33
 The Collection Interfaces
➢ Two Types of methods for interfaces: modifiable and unmodifiable. All the built-in Collections are
modifiable, i.e., allow to modify the contents of the collection.
Some Methods of Collection Interface:
Method Return Type Description
add() boolean add() adds a compatible object into the collection.
addAll() addAll() method adds the entire contents of a collection to another.
remove() boolean remove() removes an object from the collection.
removeAll(c) removeAll() removes all objects of c from the collection.
removeIf() removeIf() removes objects that satisfy the condition specified by predicate.
retainAll(c) retainAll() removes all objects from the invoking collection except those in c.
clear() void Clear or remove all objects.
contains() boolean contains() checks whether a collection contains a specific object.
containAll() containAll() checks whether one collection contains all the members of another.
isEmpty() boolean Returns true if the invoking collection is empty.
size() int Returns the number of elements in the invoking collection.
toString() Object[] Returns an array of elements from the invoking collection.
34
 The Collection Interface
Some Methods of Collection Interface:
Method Return Type Description
equals() boolean Returns true if the invoking collection and object are equal.
iterator() Iterator Returns an Iterator for the invoking collection.
spliterator() Spliterator Returns a Spliterator from the invoking collection.
stream() Stream Returns a stream that uses the invoking collection as its source of elements.
parallelStream() Returned stream supports parallel operations, if possible.

Some Exceptions of Collection Interface:

Exception Name Reason for thrown
UnsupportedOperationException If a collection cannot be modified.
ClassCastException When one object is incompatible with another.
NullPointerException If an attempt is made to store a null object in a collection.
IllegalArgumentException If an invalid argument is used.
IllegalStateException if an attempt is made to add an element to a fixed-length collection that is full.
35
 The List Interface
Some Methods of List Interface:
Method Return Type Description
replaceAll() void Modify each element in the collection.
get() Object Return the object stored at the specific index.
set() Object Assigns obj to the location specified by index . Returns old object value.
indexOf() int Return the index of the first instance of an object.
lastIndexOf() Return the index of the last instance of an object.
subList() list To obtain a sublist specifying beginning and ending index.
sort() void To sort the list.
of() list Creates an unmodifiable list containing the elements specified in parameter-list.

Exception of List Interface:

Exception Name Reason for thrown
IndexOutOfBoundsException If an invalid index is used.

36
 The Queue Interface

Some Methods of Queue Interface:

Method Return Type Description
poll() Object Obtain an element from the head of the queue. Return null if the queue is
remove() empty.
Remove an element from the head of the Queue. Return Exception if empty.
peek() Object Obtain an element from the head of the Queue without removing it. peek()
element() returns null while element() throws exception if the queue is empty.
offer() boolean Add an element to a queue. It fails when fixed-length Queue is full.

Exceptions of Queue Interface:

Exception Name Reason for thrown
NoSuchElementException If an attempt is made to remove an element from an empty Queue.

37
 Iterator
Iterator: A standardized way of accessing the elements within a collection, one at a time. It’s an
Interface.
ListIterator: It extends Iterator interface and used for all types of list including ArrayList, Vector,
LinkedList, Stack, etc. Access the collection either forward or backward directions.
Spliterator: Provide support for parallel iteration.
PrimitiveIterator: Used for primitive data type. For example, PrimitiveIterator.OfDouble

Class iterator
implements Iterator
Interface.

38
 Iterator
Methods used in Iterator:
Method Return Type Description
hasNext() boolean Returns true if the iterator has more elements.
next() Object Returns the next element of the iterator. Throws
NoSuchElementException if no more element is present.
remove() void Removes the current element in the collection. If it is not followed by
next() method, then throws IllegalStateException.

Some Methods of ListIterator:

Method Return Type Description
set(), add() void Assign Object to the current and next location, respectively.
previous() Object Returns the previous element.
nextIndex(), int Returns the index of next and previous element, respectively.
previosIndex()
forEachRemaining() void The action specified by action is executed on each unprocessed
element in the collection. 39
 The ArrayList class
import java.util.Iterator; ListIterator<String> litr = al.listIterator();
import java.util.ListIterator; litr.add("Three");
System.out.println(al);
public class Main { OUTPUT:
public static void main(String[] args) { while(litr.hasNext()){ [One, Two, Three]
ArrayList <String> al = new ArrayList<>(); String str = litr.next(); One Two Three
litr.set(str+"+"); [One, Two]
al.add("One"); } [Three, One, Two]
al.add("Two"); System.out.println(al); [Three, One+, Two+]
al.add("Three"); Two+ One+ Three
Three One+ Two+
System.out.println(al); while(litr.hasPrevious()){
String str = litr.previous();
Iterator<String> itr = al.iterator(); System.out.print(str+" ");
}
while(itr.hasNext()){ System.out.println();
String str = itr.next();
System.out.print(str + " "); String[] strA = new String[al.size()];
} strA = al.toArray(strA);
System.out.println(); for(String s: strA) System.out.print(s+" ");
itr.remove(); }
System.out.println(al) ; }
40
 Map

Interfaces Classes
AbstractMap
Map Map.Entry
Nested interface
of Map
EnumMap HashMap TreeMap WeakHashMap
SortedMap
IdentityHashMap

AbstractSequentialList
NavigableMap

41
 Map
Some Methods of Map Interface:
Method Return Type Description
get() Value To obtain a value passing the key as an argument.
put() Value To put a value into a Map specifying the key and value. Returns the
previous value linked to the key is returned. Returns null if the key did not
already exist.
entrySet() Set Returns a Set that contains the entries in the map. The set contains objects
of type Map.Entry.
getKey() Key To obtain the collection-view of keys.
getValue() Value To obtain the collection-view of values.
containsKey() boolean Returns true if the invoking map contains k as a key. Otherwise, returns
false.
containsValue() boolean Returns true if the map contains v as a value. Otherwise, returns false.

42
 Map
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main { OUTPUT:

John Doe : 4434.34
public static void main(String[] args) {
Tom Smith : 123.22
HashMap<String, Double> hm = new HashMap<>(); Jane Baker : 1378.0
hm.put("John Doe", 3434.34); Found
hm.put("Tom Smith", 123.22);
hm.put("Jane Baker", 1378.00);

double balance = hm.get("John Doe");

hm.put("John Doe", balance+1000);
Set<Map.Entry<String, Double>> set = hm.entrySet();
for(Map.Entry<String, Double> me: set){
System.out.print(me.getKey()+" : ");
System.out.println(me.getValue());
}

if (hm.containsKey("Tom Smith")) System.out.println("Found");

}
}
43
 Comparator
❖ Both TreeSet and TreeMap store elements in sorted order. However, it is the comparator that
defines precisely what “sorted order” means.

Some Methods of Comparator:

Method Return Type Description
compareTo() int Tests whether an object equals the invoking comparator.
equals() int Two objects (Object1 and Object2) are compared. Returns zero if both
are equal. Returns positive value if Object1 is greater than Object2;
otherwise returns negative value.
reversed() Comparator Reverses the ordering of the comparator.
nullsFirst() Comparator Returns a comparator that views null values as less than other values.
nullsLast() Comparator Returns a comparator that views null values as greater than other
values.

44
 Comparator
import java.util.Comparator; import java.util.Comparator;
import java.util.TreeSet; import java.util.TreeSet;

class MyComp implements Comparator<String> { class MyComp implements Comparator<String> {

public int compare(String aStr, String bStr){ public int compare(String aStr, String bStr){
return bStr.compareTo(aStr); return aStr.compareTo(bStr);
} }
} }

public class Main { public class Main {

public static void main(String[] args) { public static void main(String[] args) {
TreeSet<String> ts = new TreeSet<>(new MyComp()); TreeSet<String> ts = new TreeSet<>(new MyComp());
MyComp mc = new MyComp(); MyComp mc = new MyComp();

ts.add("One"); OUTPUT: ts.add("One"); OUTPUT:

ts.add("Two"); [Two, Three, One, Four, Five] ts.add("Two"); [Five, Four, One, Three, Two]
ts.add("Three"); 12 ts.add("Three"); -6
ts.add("Four"); [Five, Four, One, Three, Two] ts.add("Four"); [Two, Three, One, Four, Five]
ts.add("Five"); ts.add("Five");
System.out.println(ts);
System.out.println(mc.compare("Dhaka", "Pabna")); System.out.println(ts);
System.out.println(ts.reversed()); System.out.println(mc.compare("Dhaka", "Jamalpur"));
} System.out.println(ts.reversed());
} }
} 45
 Algorithms
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {

public static void main(String[] args) {
LinkedList<Integer> ll = new LinkedList<>();
ll.add(20);
OUTPUT:
[6, 20, 5, 8, -25]
ll.add(8); [20, 8, 6, 5, -25]
ll.add(1, 5); [8, -25, 6, 5, 20]
ll.addFirst(6); Max:20
ll.addLast(-25); Min: -25
System.out.println(ll);
Comparator<Integer> r = Collections.reverseOrder();
Collections.sort(ll, r);
System.out.println(ll);
Collections.shuffle(ll);
System.out.println(ll);
System.out.println("Max:" + Collections.max(ll));
System.out.println("Min: " + Collections.min(ll));
}
}
46