Introduction to Data Structures
Authors: Darren Yao, Benjamin Qi, Allen Li, Neo Wang
Contributors: Nathan Wang, Abutalib Namazov
What a data structure is, (dynamic) arrays, pairs, and tuples.
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.
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.
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).
Resources | ||||
---|---|---|---|---|
LCPP |
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 int
s can be initialized using the following line of
code:
array<int, 25> arr;
The array class supports 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. - Use a built-in function such as
std::fill_n(arr, 25, 0)
orstd::fill(arr, arr+25, 0)
.
Warning!
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
, as you might expect. On the other hand, memset(arr, -1, sizeof arr)
will
set each element to , not .
Dynamic Arrays
Resources | ||||
---|---|---|---|---|
IUSACO | module is based off this | |||
CPH | vectors, strings | |||
PAPS | ||||
LCPP |
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 time.
For example, the following code creates a dynamic array and adds the numbers through 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:
// one wayvector<int> v(n);// another wayvector<int> v;v.resize(n);
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.
Iterating
Resources | ||||
---|---|---|---|---|
CPH | ||||
CPP | ||||
LCPP |
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
.
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]// this remove method is O(n); to be avoidedv.push_back(8); // [2, 7, 5, 8]v.erase(v.end() - 1); // [2, 7, 5]
Strings
Resources | ||||
---|---|---|---|---|
LCPP | Goes over the basics of strings | |||
CPP | C++ Reference for std::string |
Introductory problems might involve doing some things with strings, such
- Reading in strings from standard input
- Knowing how to use
getline
andcin
together (more rare; refer to LCPP resource above) - Knowing how to sort strings, concatenate strings, loop through a string's characters
- Get the
i
th character of a string - Know how to get substrings with
string::substr
Pairs
If we want to store a collection of points on the 2D plane, then we can use a dynamic array of pairs.
Both vector<vector<int>>
and vector<array<int,2>>
would suffice
for this case, but a pair can also store two elements of different types.
C++ Pairs
pair<type1, type2> p
: Creates a pairp
with two elements with the first one being oftype1
and the second one being oftype2
.make_pair(a, b)
: Returns a pair with valuesa
,b
.{a, b}
: With C++11 and above, this can be used as to create a pair, which is easier to write thanmake_pair(a, b)
.pair.first
: The first value of the pair.pair.second
: The second value of the pair.
Demo
#include <iostream>#include <vector>using namespace std;/*** Output:* Testing 123* It is possible to edit pairs after declaring them 123* Testing curly braces
C++ Tuples
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 withN
elements, i'th one being oftypei
.make_tuple(a, b, c, ..., d)
: Returns a tuple with values written in the brackets.get<i>(t)
: Returns thei
'th element of the tuplet
. 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 sincei
is not constant:tuple<int, int, int> t{3, 4, 5};int i = 1;cout << get<i>(t) << endl; // not allowed!tie(a, b, c, ..., d) = t
: Assignsa, b, c, ..., d
to the elements of the tuple accordingly.
Demo
#include <iostream>#include <tuple>using namespace std;/*** Output:* 3 4 5* 7 4 5* Hello world 100
Memory Allocation
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 .
- Divide by the size, in bytes, of an
int
(4), or along long
(8), etc. For example, the number ofint
s that you are able to store is bounded above by . - Be aware that program overhead (which can be very significant, especially with recursive functions) will reduce the amount of memory available.
Quiz
How do you count the number of items in an std::vector
? Suppose we named the vector v
.
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.
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!