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:

Copy
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

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 $\mathcal{O}(1)$ time. A list can be initialized as follows:

Copy
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:

Copy
for i in range(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.

Copy
arr = [0] * 30

Iterating

We can use a regular for loop to iterate through all elements of a list.

Copy
arr = [1, 7, 4, 5, 2]

for i in range(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.

Copy
arr = [4, 2, 0, 0, 5]
it = iter(arr)

print(next(it))  # 4
print(next(it))  # 2
print(next(it))  # 0

Inserting and Erasing

Copy
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]

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.

Copy
# 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 * 2 for 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:

Copy
# 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 in input().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.

While Python doesn't have a specific class just for pairs, 2-element tuples give nearly the exact same functionality. The only issue is that you can't modify the elements since tuples are immutable.

On the other hand, Python has built-in comparison support for tuples. When comparing, it looks at the first elements of each pair, then the second, and so on and so forth.

Copy
"""
Output:
(5, 'asdf')
5
True
"""

p1 = (5, "asdf")
print(p1)
print(p1[0])  # access the first element of the tuple

p2 = (6, "asdf")
print(p1 < p2)