Parent directory
Makefile
stl1.cpp
stl2.cpp
words.cpp
CC = g++
CXX = g++
CFLAGS = -Wall
CXXFLAGS = -Wall -std=c++17
executables = stl1 stl2 words
.PHONY: default
default: $(executables)
.PHONY: clean
clean:
rm -f a.out core *.o $(executables)
.PHONY: all
all: clean default
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
using namespace std;
template <typename T, int N>
struct Array {
// typedef T value_type;
using value_type = T;
// The type "T(&)[N]" is reference to array of N elements of T
typedef T (&TA)[N];
T& operator[](int i) { return a[i]; }
const T& operator[](int i) const { return a[i]; }
constexpr int size() const { return N; }
TA underlying() { return a; }
T a[N];
};
void print_int(int x) { cout << x << ' '; }
int main()
{
int a[5] = { 100, 101, 102, 103, 104 };
size_t n = sizeof(a) / sizeof(a[0]);
for (size_t i = 0; i < n; ++i) { print_int(a[i]); }
cout << '\n';
}
/*
Code to use in lecture:
int a[5] { 100, 101, 102, 103, 104 };
Array<int,5> v { 100, 101, 102, 103, 104 };
std::array<int,5> v { 100, 101, 102, 103, 104 };
vector<int> v { 100, 101, 102, 103, 104 };
deque<int> v { 100, 101, 102, 103, 104 };
list<int> v { 100, 101, 102, 103, 104 };
v.push_front(99);
v.push_back(205);
forward_list<int> v { 100, 101, 102, 103, 104 };
cout << sizeof(v) << '\n';
for (int x : a) { print_int(x); }
for (int x : v.a) { print_int(x); }
for (int x : v.underlying()) { print_int(x); }
for (int x : v) { print_int(x); }
Lecture outline:
1. arrays in C++
- direct-list-initialization and range-for loop for C arrays
- Array template class
- std::array template class
2. STL containers
- vector
- elements are always contiguous
- push_back() in O(1), but may invalidate pointers and refs
- deque
- push_back() & push_front() in O(1), and preserve ptrs and refs
- elements are not contiguous though
- list
- doubly linked list
- push_back(), push_front(), insert() all in O(1)
- but probably slower than vector in many situations
- forward_list
- minimal singly linked list
- push_front()
- all STL containers contain elements by value
- recall the memory diagram of vector<MyString>
*/
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
#include <iterator>
using namespace std;
// Pretty much the same as std::for_each
template <typename I, typename F>
void For_Each(I b, I e, F f)
{
while (b != e) {
f(*b);
++b;
}
}
void print_int(int x) { cout << x << ' '; }
int main()
{
int a[5] = { 100, 101, 102, 103, 104 };
For_Each(a, a + 5, &print_int);
cout << '\n';
}
/*
Code to use in lecture:
vector<int> v { 100, 101, 102, 103, 104 };
vector v { 100, 101, 102, 103, 104 };
list v { 100, 101, 102, 103, 104 };
const list v { 100, 101, 102, 103, 104 };
For_Each(&v[0], &v[0] + 5, &print_int);
For_Each(v.begin(), v.end(), &print_int);
for (list<int>::iterator i = v.begin(); i != v.end(); ++i) {
*i += 200;
cout << *i << ' ';
}
for (list<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
cout << *i << ' ';
}
for (auto i = v.begin(); i != v.end(); ++i) {
cout << *i << ' ';
}
for (auto& x : v) {
cout << x << ' ';
}
Lecture outline:
1. For_Each using pointers
- array
- vector
2. For_Each using begin() & end()
- also works for list & deque, so ++b can't just be pointer arithmetic
3. Iterators
- end() points to one past the last element
- half-open element range: [ b, e )
- dereferencing iterator gives you "T&"
- dereferecning const_iterator gives you "const T&"
- use auto to deduce iterator type
- range-for loop uses begin() & end()
- why not (b < e)?
- why not b++?
4. Template compilation model
*/
#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
map<string,int> m;
for (string s; cin >> s; ) {
++m[s];
//m.insert( {s, m.count(s) + 1} );
}
// Looping through map using iterator... ugh!
for (auto i = m.begin(); i != m.end(); ++i) {
cout << setw(4) << (*i).second << '|';
cout << i->first << '\n';
}
}
/*
Code to use in the lecture:
unordered_map<string,int> m;
multimap<string,int> m;
unordered_multimap<string,int> m;
// Range-for loop... better.
for (auto& e : m) {
cout << setw(4) << e.second << '|' << e.first << '\n';
}
// Structured binding in C++17!
for (auto& [s, n] : m) {
cout << setw(4) << n << '|' << s << '\n';
}
// This compiles & runs for multimaps, but probably not what you want!
auto it = m.find("#include"s);
if (it != m.end()) {
auto& [s, n] = *it;
cout << "\nThe program " << s << " " << n << " headers." << '\n';
}
// Call equal_range() to find all elements in multimaps
auto range = m.equal_range("#include"s);
if (range.first != range.second) {
auto& s = range.first->first;
//auto n = range.second - range.first;
auto n = distance(range.first, range.second);
cout << "\nThe program " << s << " " << n << " headers." << '\n';
}
*/