A data structure determines how data is organized so that information can be
used efficiently. Each data structure supports some operations efficiently,
while other operations are either inefficient or not supported at all. Since
different operations are supported by each data structure, you should carefully
evaluate which data structure will work best for your particular problem.
C++
The C++
standard library data structures are
designed to store any type of data. We put the desired data type within the <>
brackets when declaring the data structure, as follows:
vector<string> v;
This creates a vector structure that only stores objects of type string.
For our examples below, we will primarily use the int data type, but note that
you can use any data type including string and user-defined structures.
Nearly every standard library data structure supports the size() method, which
returns the number of elements in the data structure, and the empty() method,
which returns true if the data structure is empty, and false otherwise.
Java
Python
C++
Arrays
Warning!
One can solve all Bronze problems without using anything from this module aside
from arrays. The rest of this module isn't strictly necessary for Bronze
(although it is highly recommended).
You already know one of the simplest data structures: the array! In C++11,
in addition to normal arrays, there exists an
array class in the STL. For
example, an array of 25 ints can be initialized using the following line of
code:
array<int,25> arr;
The array class supports the normal STL operations (such as .empty() or
.size()) as well as the normal square-bracket access operator:
arr[5]// accesses the element at the 5th index
In C++, arrays initialized locally using either the default syntax (i.e.
int arr[25]; ) or the array class are initialized to random numbers because
C++ doesn't have built-in memory management. In order to initialize an array to
zero, you have several options:
Use a for loop (or nested for loops).
Declare the array globally.
Declare the array with an empty initializer list (i.e. int arr[25]{}; ) as
mentioned here.
memset(arr, 0, sizeof arr)
will also zero-initialize an array. However, it's important to note that
memset treats the value that is passed to it as an unsigned char. So for an
array of 32-bit integers, memset(arr, -1, sizeof arr) will set each element to
−1, as you might expect. On the other hand, memset(arr, 1, sizeof arr) will
set each element to 1+28+216+224=16843009, not 1.
Dynamic arrays (vector in
C++) support all the functions that a normal array does, and can resize itself
to accommodate more elements. In a dynamic array, we can also add and delete
elements at the end in O(1) time.
For example, the following code creates a dynamic array and adds the numbers 1
through 10 to it:
vector<int> v;
for(int i =1; i <=10; i++){
v.push_back(i);
}
g++ will allow you to create an array of variable length:
int n; cin >> n;
int v[n];
However, variable-length arrays are
not part of the C++ standard.
We recommend that you use a vector for this purpose instead:
vector<int>v(n);// one way
vector<int> v; v.resize(n);// another way
In array-based contest problems, we'll use one-, two-, and three-dimensional
static arrays much of the time. However, we can also have dynamic arrays of
dynamic arrays (e.g. vector<vector<int>>) static arrays of dynamic arrays
(e.g. array<vector<int>,5>), dynamic arrays of static arrays (e.g.
vector<array<int,5>>), and so on.
One way to iterate through all elements of a static or dynamic array is to use a
regular for loop.
vector<int> v{1,7,4,5,2};
for(int i =0; i <int(size(v)); i++){
cout << v[i]<<" ";
}
cout << endl;
Optional
std::vector (and all the other standard library containers) support bounds-checked
accesses as mentioned here.
We can also use iterators. An iterator allows you to traverse a container by
pointing to an object within the container. However, they are not the same
thing as pointers.
For example, v.begin() or begin(v) returns an iterator pointing to the first
element of the vector v. Apart from the standard way of traversing a vector
(by treating it as an array), you can also use iterators:
for(vector<int>::iterator it = v.begin(); it != v.end();++it){
cout <<*it <<" ";//prints the values in the vector using the iterator
}
Here is another way to write this. auto (since C++11) automatically infers the
type of an object:
vector<int> v{1,7,4,5,2};
for(auto it =begin(v); it !=end(v); it =next(it)){
cout <<*it <<" ";//prints the values in the vector using the iterator
}
We can also use a for-each loop.
for(int element : v){
cout << element <<" ";//prints the values in the vector
}
Inserting and Erasing
Keep in mind that insertion and erasure in the middle of a vector are
O(n).
vector<int> v;
v.push_back(2);// [2]
v.push_back(3);// [2, 3]
v.push_back(7);// [2, 3, 7]
v.push_back(5);// [2, 3, 7, 5]
v[1]=4;// sets element at index 1 to 4 -> [2, 4, 7, 5]
v.erase(v.begin()+1);// removes element at index 1 -> [2, 7, 5]
Java default
Collections
data structures are designed to store any type of object. However, we usually
don't want our data structures to only store one type of data, like integers or
strings. We do this by putting the desired data type within the <> brackets
when declaring the data structure, as follows:
ArrayList<String> list =newArrayList<String>();
This creates an ArrayList structure that only stores objects of type String.
For our examples below, we will primarily use the Integer data type, but note
that you can have Collections of any object type, including Strings , other
Collections, or user-defined objects.
Collections data types always contain an add method for adding an element to
the collection, and a remove method which removes and returns a certain
element from the collection. They also support the size() method, which
returns the number of elements in the data structure, and the isEmpty()
method, which returns true if the data structure is empty, and false
otherwise.
Dynamic Arrays
Dynamic arrays
(ArrayList
in Java) that support all the functions that a normal array does, and can
repeatedly reallocate storage to accommodate more elements as they are added.
In a dynamic array, we can also add and delete elements at the end in
O(1) time. For example, the following code creates a dynamic array
and adds the numbers 1 through 10 to it:
ArrayList<Integer> list =newArrayList<Integer>();
for(int i =1; i <=10; i++){
list.add(i);
}
In array-based contest problems, we'll use one-, two-, and three-dimensional
static arrays most of the time. However, we can also have static arrays of
dynamic arrays, dynamic arrays of static arrays, and so on. Usually, the choice
between a static array and a dynamic array is just personal preference.
Iterating
To iterate through a static or dynamic array, we can use either the regular for
loop or the for-each loop.
We can add and remove at any index of a dynamic array in O(n) time.
ArrayList<Integer> list =newArrayList<Integer>();
list.add(2);// [2]
list.add(3);// [2, 3]
list.add(7);// [2, 3, 7]
list.add(5);// [2, 3, 7, 5]
list.set(1,4);// sets element at index 1 to 4 -> [2, 4, 7, 5]
list.remove(1);// removes element at index 1 -> [2, 7, 5]
// this remove method is O(n); to be avoided
list.add(8);// [2, 7, 5, 8]
list.remove(list.size()-1);// [2, 7, 5]
// here, we remove the element from the end of the list; this is O(1)
System.out.println(list.get(2));// 5
Python
Lists
The default way to store data in Python is using a list, which can
automatically resize itself to accommodate more elements. We can add and delete
elements at the end in O(1) time. A list can be initialized as
follows:
arr =[]
Python lists are generic. This means that they can store any kind of data
type, including objects. For example, the following code creates a dynamic array
and adds the numbers 1 through 10 to it:
for i inrange(1,11):# Note that range(i, j) includes i, but does not include j
arr.append(i)
In Python, we can give a dynamic array an initial size. The code below creates a
dynamic array with 30 zeroes.
arr =[0]*30
Iterating
We can use a regular for loop to iterate through all elements of a list.
arr =[1,7,4,5,2]
for i inrange(len(arr)):
print(arr[i], end =" ")
print()
for element in arr:
print(element, end =" ")
print()
We can also use iterators. An iterator allows you to traverse a container by
pointing to an object within the container. iter(arr) returns an iterator
pointing to the first element of the list arr.
arr =[4,2,0,0,5]
it =iter(arr)
print(next(it))# 4
print(next(it))# 2
print(next(it))# 0
Inserting and Erasing
arr =[]
arr.append(2)# [2]
arr.append(3)# [2, 3]
arr.append(7)# [2, 3, 7]
arr.append(5)# [2, 3, 7, 5]
arr[1]=4;# sets element at index 1 to 4 -> [2, 4, 7, 5]
arr.pop(1)# removes element at index 1 -> [2, 7, 5]
# this remove method is O(n); to be avoided
arr.append(8)# [2, 7, 5, 8]
arr.pop()# [2, 7, 5]
List Comprehensions
List comprehensions are extremely useful for simplifying a python for loop that
modifies/creates a list into one expression. The general syntax is:
[ expression for item in list if conditional ]
An example is provided in the code block below.
# If a number is odd, add the number times 2 into the array
old_list =[2,5,3,1,6]
new_list =[]
for i in old_list:
if i %2==1:
new_list.append(i *2);
print(new_list)# [10, 6, 2]
# Simplified one liner with list comprehension
# Recall the form [ expression for item in list if conditional ]
# expression: i * 2
# list: old_list
# conditional: i % 2 == 1 (only include item i if it satisfies the conditional)
new_list =[i *2for i in old_list if i %2==1]
print(new_list)# [10, 6, 2]
A very applicable use of list comprehensions for competitive programming in
particular is creating an integer list from space separated input:
# Example input: 5 3 2 6 8 1
# Note that the conditional in the list comprehension is optional, and defaults to True if not provided
arr =[int(x)for x ininput().split()]
print(arr)# [5, 3, 2, 6, 8, 1]
For more information on list comprehensions, including nesting them to create
multidimensional lists, refer to the below resources.
Of course, we can hold more than two values with something like
pair<int,pair<int,int>>, but it gets messy when you need a lot of elements. In
this case, using tuples might be more convenient.
tuple<type1, type2, ..., typeN> t: Creates a tuple with N elements, i'th
one being of typei.
make_tuple(a, b, c, ..., d): Returns a tuple with values written in the
brackets.
get<i>(t): Returns the i'th element of the tuple t. Can also be used to
change the element of a tuple.
This operation only works for constant i. Namely, it is not allowed to do
something like the following since i is not constant:
tuple<int,int,int> t{3,4,5};
int i =1; cout << get<i>(t);
tie(a, b, c, ..., d) = t: Assigns a, b, c, ..., d to the elements of the
tuple t accordingly.
One thing to keep in mind when using arrays is the memory limit. Usually the
USACO memory limit is 256 MB. To estimate how many values can be stored within
this limit:
Calculate the total memory size in bytes: for 256 MB, that's 256⋅106.
Divide by the size, in bytes, of an int (4), or a long long (8), etc. For
example, the number of ints that you are able to store is bounded above by
4256⋅106=64⋅106.
Be aware that
program overhead
(which can be very significant, especially with recursive functions) will
reduce the amount of memory available.
Quiz
C++
How do you count the number of items in an std::vector? Suppose we named the vector v.
Question 1 of 3
Java
How do you count the number of items in an ArrayList? Suppose we named it list.
Question 1 of 2
Python
How do you count the number of items in a list? Suppose we named the list l.
2
Copy
count(l)
3
Copy
size(l)
4
Copy
l.length()
PreviousQuestion 1 of 3Submit
Problems
Nothing to see here! To reiterate, arrays of fixed size should suffice for
essentially every Bronze problem, but dynamic arrays, pairs, and tuples can
greatly simplify implementation at times. You'll see some examples of these in
the following module.