COMP6771 Advanced C++ Programming
Week 2.1 STL Containers
1
Libraries
Most of us are quite familiar with libraries in software. For example, in COMP1511, we’ve used
Being an effective programmer often consists of the effective use of libraries. In some ways, this becomes more important than being a genius at writing code from scratch (Don’t reinvent the wheel!).
While there are many libraries that can be used with C++, the Standard Template Library is the one we will focus on.
2
STL: Standard Template Library
STL is an architecture and design philosophy for managing generic and abstract collections of data with algorithms
All components of the STL are templates
Containers store data, but don’t know about algorithms
Iterators are an API to access items within a container in a particular order, agnostic of the container used
Each container has its own iterator types
Algorithms manipulate values referenced by iterators, but don’t know about containers
Container Container Container Algorithm Container
3
Iterator
Iterator
Iterating through a basic container
1 #include
2 #include
3
4 int main() {
5 //
6 //
7 //
8 //
9 //
10
11 //
12 //
13 std::array
14
15 for (unsigned int i = 0; i < ages.size(); ++i) {
16 std::cout << ages[i] << "\n";
17 }
18 for (auto it = ages.begin(); it != ages.end(); ++it) {
19 std::cout << *it << "\n";
20 }
21 for (const auto& age : ages) {
22 std::cout << age << "\n";
23 }
24 }
C-style. Don't do this
int ages[3] = { 18, 19, 20 };
for (int i = 0; i < 3; ++i) {
std::cout << ages[i] << "\n";
}
C++ style. This can be used like any other C++ container.
It has iterators, safe accesses, and it doesn't act like a pointer.
demo201-vec-iter.cpp
4
Sequential Containers
Organises a finite set of objects into a strict linear arrangement.
std::vector
std::array
std::deque
std::forward_list
std::list
Dynamically-sized array.
Fixed-sized array. Double-ended queue.
Singly-linked list. Doubly-linked list.
We will explore these in greater detail in Week 10.
It won't be necessary to use anything other than std::vector in COMP6771.
5.1
Another look at Vector
Array-like container most used is
Abstract, dynamically resizable array
In later weeks we will learn about various ways to construct a vector
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
#include
#include
// Begin with numbers 1, 2, 3 in the list already
int main() {
// In C++17 we can omit the int if the compiler can determine the type.
std::vector
int input;
while (std::cin >> input) {
numbers.push_back(input);
}
std::cout << "1st element: " << numbers.at(0) << "\n"; // slower, safer
std::cout << "2nd element: " << numbers[1] << "\n"; // faster, less safe
std::cout << "Max size before realloc: " << numbers.capacity() << "\n";
for (int n : numbers) {
std::cout << n << "\n";
}
}
demo202-vec-obj.cpp
5.2
Ordered Associative Containers
Provide fast retrieval of data based on keys. The keys are sorted. A value is accessed via a key.
A collection of unique keys.
A collection of keys.
Associative array that map a unique keys to values.
Associative array where one key may map to many values. They are mostly interface-compatible with the unordered associative containers.
std::set
std::multiset
std::map
std::multimap
6.1
std::map example
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include
#include