DynamicArray

Dynamic Array

An Array that automatically resizes itself when full.

• C++ Vector
• Java ArrayList

Dynamic arrays can usually pre-allocate memory. While this does not usually affect runtime significantly enough for a human to notice, it might make a difference with the online judge.

• C++: vector<int> myVector(size);
• Java: ArrayList<Integer> myList = new ArrayList<Integer>(size);

The contents can also be initalized on construction.

• C++: vector<int> myVector(size, -1);
• Java: ArrayList<Integer> myList = new ArrayList<Integer>(Collections.nCopies(size, -1));

Adding elements:

• C++: myVector.push_back(item);
• Java: myList.add(item);

Accessing items:

• C++: int item = myVector[index];
• Java: int item = myList.get(index);

Changing items:

• C++: myVector[index] = newItem;
• Java: myList.put(index, newItem);

Getting size:

• C++: size_t size = myVector.size();
• Java: int size = myList.size();

Checking if empty:

• C++: bool empty = myVector.empty();
• Java: boolean empty = myList.isEmpty();

Iterating over contents:

• C++: for( vector<int>::iterator it = myVector.begin(); it != myVector.end(); it++ ){ int value = *it; }
• C++11: for( int value : myVector ) {}
• Java: Iterator<Integer> it = myList.iterator(); while(it.hasNext()){ int value = it.next(); }
• Java7: for(int value : myList) {}

Sorting:

• C++ (you must #include<algorithm>): stable_sort(myVector.begin(), myVector.end());
• Java: Collections.sort(myList);

Note that the above sort functions are stable. This means that equivalent items remain in the same relative order. This means that you can sort on multiple values, by applying the comparators in reverse order.

For example, say you have a Student structure which records a name and a gpa. You want the list of students sorted by GPA, with equivalent GPAs sorted by name. You would stable-sort by name first, then by gpa. That way, when sorting by GPA, Students with equal GPA remain in the order they were in before sorting by GPA, i.e. in order by name.

C++:

struct Student{
    string name;
    float gpa;
}
bool byName(Student s1, Student s2){
    return s1.name < s2.name;
}
bool byGPA(Student s1, Student s2){
    return s1.gpa < s2.gpa;
}
//...
vector<Student> students;
stable_sort(students.begin(), students.end(), byName);
stable_sort(students.begin(), students.end(), byGPA);

Java:

public class Student{
    String name;
    double gpa;
    public static class CompByName implements Comparator<Student>{
        public static final CompByName instance = new CompByName();
        private CompByName(){}
        public int compare(Student s1, Student s2){
            return s1.name.compareTo(s2.name);
        }
    }
    public static class CompByGPA implements Comparator<Student>{
        public static final CompByGPA instance = new CompByGPA();
        private CompByGPA(){}
        public int compare(Student s1, Student s2){
            return s1.gpa - s2.gpa;
        }
    }
}
//...
ArrayList<Student> students;
Collections.sort(students, Student.CompByName.instance);
Collections.sort(students, Student.CompByGPA.instance);

There are also functions to negate a comparator, allowing a reverse-order sort.

• C++ (you must #include<functional>): sort(students.begin(), students.end(), not2(byName));
• Java: Collections.sort(students, Collections.reverseOrder(Student.CompByName.instance));