PrevNext

(Optional) C++ - Additional Notes About Data Structures

Author: Benjamin Qi

Issues that you should be aware of.

Edit This Page

vector Out Of Range

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v(1,5), w(1,10);
for (int i = 0; i < 10; ++i)
cout << i << " " << w[i] << "\n";
for (int i = 0; i < 10; ++i) v[i] = i;
cout << "---\n";
for (int i = 0; i < 10; ++i)
cout << i << " " << w[i] << "\n";
}

produces the following output:

0 10
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
---
0 4
1 5
2 6
3 7
4 8
5 9
6 0
7 0
8 0
9 0

This is an example of buffer overflow. Using vector::at instead of vector::operator[]

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v(1,5), w(1,10);
for (int i = 0; i < 10; ++i)
cout << i << " " << w.at(i) << "\n";
for (int i = 0; i < 10; ++i) v.at(i) = i;
cout << "---\n";
for (int i = 0; i < 10; ++i)
cout << i << " " << w.at(i) << "\n";
}

will check the bounds and throw an exception instead:

0 10
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 1) >= this->size() (which is 1)
1 zsh: abort      ./$1 $@[2,-1]

Unspecified Evaluation Order

#include <bits/stdc++.h>
using namespace std;
vector<int> res{-1};
int addElement() {
res.push_back(-1);
return res.size()-1;
}
int main() {
for (int i = 0; i < 10; ++i) {
res[i] = addElement();
cout << i << " " << res[i] << "\n";
}
}

Running the above code with C++17

g++ -std=c++17 bad.cpp -o bad && ./bad

gives the intended output:

0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

But running with C++14

g++ -std=c++14 bad.cpp -o bad && ./bad

gives:

0 -1
1 -1
2 3
3 -1
4 5
5 6
6 7
7 -1
8 9
9 10

However, the code works correctly if you save the result of addElement() to an intermediate variable.

int main() {
for (int i = 0; i < 10; ++i) {
int tmp = addElement();
res[i] = tmp;
cout << i << " " << res[i] << "\n";
}
}

The problem is that res[i] = addElement(); only works if addElement() is evaluated before res[i] is. If res[i] is evaluated first, and then addElement() results in the memory for res being reallocated, then res[i] is invalidated. The order in which res[i] and addElement() are evaluated is unspecified (at least before C++17).

See this StackOverflow post for some discussion about why this is the case (also a similar issue here).

You may come across this issue when trying to create a trie.

Initializing Array of Structs

See here.

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!

PrevNext