Parent directory
Makefile
stl1.cpp
stl2.cpp
stl3.cpp
CC = g++
CXX = g++
CFLAGS = -g -Wall
CXXFLAGS = -g -Wall -std=c++20
executables = stl1 stl2 stl3
.PHONY: default
default: $(executables)
stl1: stl1.o
stl2: stl2.o
stl3: stl3.o
.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, size_t N>
struct Array {
// typedef T value_type;
using value_type = T;
// T(&)[N] is a reference to array of N elements of type T
using TA = T(&)[N];
T& operator[](int i) { return a[i]; }
const T& operator[](int i) const { return a[i]; }
constexpr size_t size() const { return N; }
TA underlying() { return a; }
T a[N];
};
void print_int(int x) { cout << x << ' '; }
int main() {
// 1. C Arrays
//
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]); }
// 2. Array class template
//
// Array<int,5> v { 100, 101, 102, 103, 104 };
// for (size_t i = 0; i < v.size(); ++i) { print_int(v[i]); }
// constexpr size_t n = sizeof(v.underlying()) /
// sizeof(decltype(v)::value_type);
// static_assert(v.size() == n);
// 3. std::array
//
// std::array<int,5> v { 100, 101, 102, 103, 104 };
// for (size_t i = 0; i < v.size(); ++i) { print_int(v[i]); }
// 4. std::vector
//
// vector<int> v { 100, 101, 102, 103, 104 };
// v.push_back(105);
// for (size_t i = 0; i < v.size(); ++i) { print_int(v[i]); }
// 5. std::deque
//
// deque<int> v { 100, 101, 102, 103, 104 };
// v.push_front(99);
// v.push_back(105);
// for (size_t i = 0; i < v.size(); ++i) { print_int(v[i]); }
// 6. std::list
//
// list<int> v { 100, 101, 102, 103, 104 };
// v.push_front(99);
// v.push_back(105);
// while (!v.empty()) {
// print_int(v.front());
// v.pop_front();
// }
// 7. std::forward_list
//
// forward_list<int> v { 100, 101, 102, 103, 104 };
// v.push_front(99);
// while (!v.empty()) {
// print_int(v.front());
// v.pop_front();
// }
// static_assert(sizeof(forward_list<int>) == 8);
cout << '\n';
}
#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() {
// 1. integer array
//
// int a[5] { 100, 101, 102, 103, 104 };
// For_Each(a, a + 5, &print_int);
// 2. std::vector
//
// vector<int> v { 100, 101, 102, 103, 104 };
// For_Each(&v[0], &v[0] + 5, &print_int);
// For_Each(v.begin(), v.end(), &print_int);
// 3. std::list
//
// list<int> v { 100, 101, 102, 103, 104 };
// For_Each(v.begin(), v.end(), &print_int);
// 4. Looping using iterator
//
// list<int> v { 100, 101, 102, 103, 104 };
// for (list<int>::iterator i = v.begin(); i != v.end(); ++i) {
// *i += 200;
// cout << *i << ' ';
// }
// 5. Looping using const_iterator
//
// const list<int> v { 100, 101, 102, 103, 104 };
// for (list<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
// cout << *i << ' ';
// }
// 6. Using auto instead of iterator type
//
// const list<int> v { 100, 101, 102, 103, 104 };
// for (auto i = v.begin(); i != v.end(); ++i) {
// cout << *i << ' ';
// }
// 7. Range-based for loop
//
const list<int> v { 100, 101, 102, 103, 104 };
for (auto& x : v) {
cout << x << ' ';
}
cout << '\n';
}
/* Lecture outline:
Code to use in lecture:
1. For_Each using pointers to array or vector elements
- Explain using diagram
2. For_Each using begin() & end()
- For vectors, they return the appropriate pointers
- But the same code works if we replace vector with list
- so list::begin() can't just return a pointer -- For_Each() does
++b, which is not the right thing to do for linked list
- it needs to be a class object for which we define operator++()
- let's write some pseudo-code for it
3. Iterator
- for (list<int>::iterator i = v.begin(); i != v.end(); ++i) {
- begin() returns an iterator pointing at the first element
- end() returns an iterator pointing at one PAST the last element
- many STL functions work on the half-open element range: [ b, e )
- for (list<int>::const_iterator i = v.begin(); i != v.end(); ++i) {
- dereferencing iterator gives you "T&"
- dereferecning const_iterator gives you "const T&"
- iterator and range-for loop
- use auto to deduce iterator type
- range-for loop simply uses begin() & end()
4. Subleties in For_Each() implementation
- why not (b < e) instead of (b != e)?
- we will discuss iterator categories next week
- why not b++ instead of ++b?
- consider how one would implement prefix and postfix increments:
iterator& operator(); // prefix increment
iterator operator(int); // postfix increment
*/
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
template <typename Container>
struct IteratorThatPushes {
Container& c;
using iterator_category = output_iterator_tag;
using value_type = void;
using difference_type = void;
using pointer = void;
using reference = void;
explicit IteratorThatPushes(Container& c) : c(c) {}
IteratorThatPushes& operator*() { return *this; }
IteratorThatPushes& operator++() { return *this; }
IteratorThatPushes operator++(int) { return *this; }
IteratorThatPushes& operator=(const typename Container::value_type& x) {
c.push_back(x);
return *this;
}
};
// 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() {
vector<int> v1 { 100, 101, 102, 103, 104 };
vector<int> v2;
copy(v1.begin(), v1.end(), v2.begin());
For_Each(v2.begin(), v2.end(), &print_int);
cout << '\n';
}
/* Lecture outline:
1. std::copy()
- See possible implementation from cppreference.com
- It simply assumes that the target container has enough space
2. ()-initializer vs. {}-initializer
- Try the following two differnt initializers:
vector<int> v2(5);
vector<int> v2{5};
- For STL containers, the ()-initializer syntax is for sizes
and the {}-initializer syntax is for a list of elements
3. vector( std::initializer_list<T> init )
- When an object is initialized with a brace-enclosed initializer list,
and a constructor takes a std::initializer_list parameter, a
std::initializer_list object is automatically constructed
- std::initializer_list<T> is a lightweight viewer object that provides
access to an array of the initializers, which may have been placed
in read-only memory by the compiler
- std::initializer_list can be implemented with a pointer and the length
of the underlying array; copying a std::initializer_list does not copy
the underlying array
- std::initializer_list provides begin() and end()
4. Iterator that calls push_back()
- IteratorThatPushes class code walk-thru
vector<int> v2;
copy(v1.begin(), v1.end(), IteratorThatPushes<vector<int>>{v2});
copy(v1.begin(), v1.end(), IteratorThatPushes{v2});
- STL version:
copy(v1.begin(), v1.end(), back_inserter(v2));
5. ostream_iterator
- Iterator that writes to any ostream object
ostream_iterator<int> oi {cout, "\n"};
copy(v2.begin(), v2.end(), oi);
6. istream_iterator
- Iterator that reads from any istream object
vector<int> v2;
istream_iterator<int> iib {cin};
istream_iterator<int> iie {};
copy(iib, iie, back_inserter(v2));
reverse(v2.begin(), v2.end());
7. Iterator Categories
- Iterator categories are not concrete types. They are defined
conceptually by their capabilities -- i.e., by the set of operations
that they support.
- LegacyOutputIterator: supports writing and single-pass increment
- LegacyInputIterator: supports reading and single-pass increment
- LegacyForwardIterator: InputIter + multi-pass increment
- LegacyBidirectionalIterator: ForwardIter + decrement
- LegacyRandomAccessIterator: BidirIter + O(1) element access
- LegacyContiguousIterator (since C++17): RandomIter + contiguous memory
8. Iterator Concepts (since C++20)
- C++20 turned the idea of these capabilities into a laguage feature
called "Concepts"
- Iterator Categories were reworked into a similar but slightly
different taxonomy called Iterator Concepts.
- The old iterator category names were prepended with "Legacy".
*/