COMS W4995 C++ Deep Dive for C Programmers

Index of 2025-9/code/10

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

Makefile

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

stl1.cpp

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

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() {
    // 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
*/

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

*/