CS计算机代考程序代写 data structure compiler c++ algorithm COMP6771 Advanced C++ Programming

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 and .
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 ages{ 18, 19, 20 };
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 numbers {1, 2, 3};
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

#include
int main() {
std::map m;
// The insert function takes in a key-value pair.
std::pair p1{“bat”, 14.75};
m.insert(p1);
// The compiler will automatically construct values as
// required when it knows the required type.
m.insert({“cat”, 10.157});
// This is the preferred way of using a map
m.emplace(“cat”, 10.157);
// This is very dangerous, and one of the most common causes of mistakes in C++.
std::cout << m["bat"] << '\n'; auto it = m.find("bat"); // Iterator to bat if present, otherwise m.end() // This is a great example of when to use auto, but we want to show you what type it is. for (const std::pair& kv : m) {
std::cout << kv.first << ' ' << kv.second << '\n'; } } demo203-map.cpp 6.2 Unordered Associative Containers Provide fast retrieval of data based on keys. The keys are hashed. A collection of unique keys. std::unordered_set std::unordered_map Associative array that map unique keys to a values. 7 Container Performance Performance still matters STL containers are abstractions of common data structures cppreference has a summary of them here. Different containers have different time complexity of the same operation (see right) O(1)+ means amortised constant time 8