COMS W4995 C++ for C Programmers

Index of 2025-1/code/08

Parent directory
Makefile
stl1.cpp
stl2.cpp
stl3.cpp

Makefile

CC  = g++
CXX = g++

CFLAGS   = -g -Wall
CXXFLAGS = -g -Wall -std=c++17

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

stl1.cpp

#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';
}

/* Lecture outline:

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); }

1.  Arrays in C++

    - Direct-list-initialization and range-for loop for C arrays

    - Array template class code walk-through

    - 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>

*/

stl2.cpp

#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';
}

/* Lecture outline:

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 << ' ';
    }

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
*/

stl3.cpp

#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".

*/