COMS W4995 C++ for C Programmers

Index of 2025-1/code/05

Parent directory
Makefile
intarray1.cpp
intarray2.cpp
intarray3.cpp
mystring.cpp
mystring.h
rvalue-test.cpp
vec1.cpp
vec2.cpp
vec3.cpp

Makefile

CC  = g++
CXX = g++

CFLAGS   = -g -Wall
CXXFLAGS = -g -Wall -std=c++14 -fno-elide-constructors

executables = intarray1 intarray2 intarray3 rvalue-test vec1 vec2 vec3

.PHONY: default
default: $(executables)

intarray1: intarray1.o

intarray2: intarray2.o

intarray3: intarray3.o

rvalue-test: rvalue-test.o

vec1: vec1.o

vec2: vec2.o

vec3: vec3.o mystring.o

vec3.o mystring.o: mystring.h

.PHONY: clean
clean:
	rm -f *~ a.out core *.o $(executables)

.PHONY: all
all: clean default

intarray1.cpp

#include <string>
#include <iostream>

class IntArray {
public:
    IntArray() {
        sz  = 0;  // TODO: use member initializer list
        cap = 1;
        a = new int[cap];
    }

    ~IntArray() {
        delete[] a;
    }

    IntArray(const IntArray&) = delete;
    IntArray& operator=(const IntArray&) = delete;

    // This is how we can explicitly request compiler-generated versions:
    // IntArray(const IntArray&) = default;
    // IntArray& operator=(const IntArray&) = default;

    int& operator[](int i) { return a[i]; }
    const int& operator[](int i) const { return a[i]; }

    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(int x) {
        if (sz == cap) {
            int *a2 = new int[cap *= 2];  // TODO: strong exception guarantee
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    int *a;      // TODO: is this the right order of declarations?
    size_t sz;
    size_t cap;
};

std::ostream& operator<<(std::ostream& os, const IntArray& ia) {
    for (size_t i = 0; i < ia.size(); i++) {
        os << ia[i] << " ";
    }
    std::cout << "(cap=" << ia.capacity() << ")" << std::flush;
    return os;
}

int main() {
    using namespace std;

    IntArray ia;
    for (int i = 0; i < 20; i++) {
        ia.push_back(i);
        cout << ia << endl;
    }
}

/* Lecture plan:

1.  How IntArray::push_back() works

    - Time complexity: amortized O(1)

2.  Code walk-through

    - =delete & =default
    - push_back() function implementation
    - std::copy() and the pattern of specifying [begin, end) range
    - main() and operator<<()

3.  Fixing some subtle issues

    - providing strong exception guarantee
    - using member initializer list
    - order of member initialization

*/

intarray2.cpp

#include <string>
#include <iostream>

class IntArray {
public:
    IntArray() : sz{0}, cap{1}, a{new int[cap]} {}

    ~IntArray() {
        delete[] a;
    }

    IntArray(const IntArray&) = delete;
    IntArray& operator=(const IntArray&) = delete;

    // This is how we can explicitly request compiler-generated versions:
    // IntArray(const IntArray&) = default;
    // IntArray& operator=(const IntArray&) = default;

    /*
    IntArray(IntArray&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
        std::cout << "move ctor" << std::endl;
    }

    IntArray& operator=(IntArray&& tmp) = delete;
    */

    int& operator[](int i) { return a[i]; }
    const int& operator[](int i) const { return a[i]; }

    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(int x) {
        if (sz == cap) {
            // Separate cap*=2 to provide strong exception guarantee
            // int *a2 = new int[cap *= 2];
            int *a2 = new int[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    size_t sz;
    size_t cap;
    int *a;
};

std::ostream& operator<<(std::ostream& os, const IntArray& ia) {
    for (size_t i = 0; i < ia.size(); i++) {
        os << ia[i] << " ";
    }
    std::cout << "(cap=" << ia.capacity() << ")" << std::flush;
    return os;
}

/*
IntArray createIntArray() {
    IntArray tmp;
    for (int i = 0; i < 20; i++) {
        tmp.push_back(i);
        std::cout << tmp << std::endl;
    }
    return tmp;
}
*/

int main() {
    using namespace std;

    IntArray ia { /* createIntArray() */ };

    cout << "ia: " << ia << endl;
}

/* Lecture outline:

1.  defining and calling createIntArray()

    - does not compile because we deleted the copy constructor

    - explain that the copy constructor would have to deep-copy

    - returning a large object by value is a very nice and clean pradigm
      (think Java), but old C++ avoided it due to the cost of copying

2.  move constructor

    - motivation: make returning local objects efficient

    - if you are copying from an object that will be destroyed, just 
      steal the internals instead of copying from it

    - code: copy the interal pointer to the new object, and then sever the 
      connection from the old object

    - enabling copy elision eliminates the move constructor calls

3.  rvalue reference

    - ravlue examples: 5, MyString{"abc"}

    - rvalue-test.cpp: regular ref vs. const ref vs. rvalue ref

    - why does move constructor need rvalue reference?
        - regular reference cannot be bound to rvalue
        - const reference can be, but you cannot then change the object

*/

intarray3.cpp

#include <string>
#include <iostream>

class IntArray {
public:
    IntArray() : sz{0}, cap{1}, a{new int[cap]} {}

    ~IntArray() {
        delete[] a;
    }

    IntArray(const IntArray&) = delete;
    IntArray& operator=(const IntArray&) = delete;

    // This is how we can explicitly request compiler-generated versions:
    // IntArray(const IntArray&) = default;
    // IntArray& operator=(const IntArray&) = default;

    IntArray(IntArray&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
        std::cout << "move ctor" << std::endl;
    }

    IntArray& operator=(IntArray&& tmp) {
        if (this != &tmp) {
            delete[] a;

            sz = tmp.sz;
            cap = tmp.cap;
            a = tmp.a;

            tmp.sz = tmp.cap = 0;
            tmp.a = nullptr;
        }
        std::cout << "move assignment" << std::endl;
        return *this;
    }

    int& operator[](int i) { return a[i]; }
    const int& operator[](int i) const { return a[i]; }

    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(int x) {
        if (sz == cap) {
            // Separate cap*=2 to provide strong exception guarantee
            // int *a2 = new int[cap *= 2];
            int *a2 = new int[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    size_t sz;
    size_t cap;
    int *a;
};

std::ostream& operator<<(std::ostream& os, const IntArray& ia) {
    for (size_t i = 0; i < ia.size(); i++) {
        os << ia[i] << " ";
    }
    std::cout << "(cap=" << ia.capacity() << ")" << std::flush;
    return os;
}

IntArray createIntArray() {
    IntArray tmp;
    for (int i = 0; i < 20; i++) {
        tmp.push_back(i);
        std::cout << tmp << std::endl;
    }
    return tmp;
}

int main() {
    using namespace std;

    IntArray ia { createIntArray() };

    cout << "ia: " << ia << endl;

    IntArray ia2;

    //ia2 = ia;
    //ia2 = (IntArray&&)ia;
    //ia2 = std::move(ia);

    cout << "ia2: " << ia2 << endl;
    cout << "ia: " << ia << endl;
}

/* Lecture outline:

4.  move assignment

    - code: self-assign check, delete mine, copy rhs, sever rhs, return *this
    - casting to rvalue reference
    - std::move()

*/

mystring.cpp

#include <cstring>
#include <cstdio>

#include "mystring.h"

// default constructor

MyString::MyString()
{
    data = new char[1];
    data[0] = '\0';

    len = 0;
}

// constructor

MyString::MyString(const char *p)
{
    if (p) {
        len = strlen(p);
        data = new char[len+1];
        strcpy(data, p);
    } else {
        data = new char[1];
        data[0] = '\0';
        len = 0;
    }
}

// destructor

MyString::~MyString()
{
    delete[] data;
}

// copy constructor

MyString::MyString(const MyString& s)
{
    len = s.len;

    data = new char[len+1];
    strcpy(data, s.data);
}

// copy assignment

MyString& MyString::operator=(const MyString& rhs)
{
    if (this == &rhs) {
        return *this;
    }

    // first, deallocate memory that 'this' used to hold

    delete[] data;

    // now copy from rhs

    len = rhs.len;

    data = new char[len+1];
    strcpy(data, rhs.data);

    return *this;
}

// operator+

MyString operator+(const MyString& s1, const MyString& s2)
{
    MyString temp;

    delete[] temp.data;

    temp.len = s1.len + s2.len;

    temp.data = new char[temp.len+1];
    strcpy(temp.data, s1.data);
    strcat(temp.data, s2.data);

    return temp;
}

// put-to operator

std::ostream& operator<<(std::ostream& os, const MyString& s)
{
    os << s.data;
    return os;
}

// get-from operator

std::istream& operator>>(std::istream& is, MyString& s)
{
    // this is kinda cheating, but this is just to illustrate how this
    // function can work.

    std::string temp;
    is >> temp;

    delete[] s.data;

    s.len = strlen(temp.c_str());
    s.data = new char[s.len+1];
    strcpy(s.data, temp.c_str());

    return is;
}

// operator[] - in real life this function should be declared inline

char& MyString::operator[](int i)
{
    if (i < 0 || i >= len) {
        throw std::out_of_range{"MyString::op[]"};
    }
    return data[i];
}

// operator[] const - in real life this should be inline

const char& MyString::operator[](int i) const
{
    // illustration of casting away constness
    return ((MyString&)*this)[i];

    // The C-style casting above works, but the proper way
    // to cast away constness in C++ is to do the following:
    //
    // return const_cast<MyString&>(*this)[i];
}

mystring.h

#ifndef __MYSTRING_H__
#define __MYSTRING_H__

#include <iostream>

class MyString {

public:

    // default constructor
    MyString();

    // constructor
    MyString(const char* p);

    // destructor
    ~MyString();

    // copy constructor
    MyString(const MyString& s);

    // copy assignment
    MyString& operator=(const MyString& s);

    // returns the length of the string
    int length() const { return len; }

    // operator+
    friend MyString operator+(const MyString& s1, const MyString& s2);

    // put-to operator
    friend std::ostream& operator<<(std::ostream& os, const MyString& s);

    // get-from operator
    friend std::istream& operator>>(std::istream& is, MyString& s);

    // operator[]
    char& operator[](int i);

    // operator[] const
    const char& operator[](int i) const;

private:

    char* data;

    int len;
};

#endif

rvalue-test.cpp

#include <iostream>
using namespace std;

struct X {
    X() : d{100} {}

    double d;
};

void f1(X& t)       { t.d *= 2;  cout << t.d << endl; }

void f2(const X& t) { cout << "can't change t" << endl; }

void f3(X&& t)      { t.d *= 3;  cout << t.d << endl; }

int main() {
    X x;           // x is an lvalue
                  
    f1(x);         // passing an lvalue to X&       --> ok
    f2(x);         // passing an lvalue to const X& --> ok
    // f3(x);      // passing an lvalue to X&&      --> not ok

    // f1( X{} );  // passing an rvalue to X&       --> not ok
    f2( X{} );     // passing an rvalue to const X& --> ok
    f3( X{} );     // passing an rvalue to X&&      --> ok
}

vec1.cpp

#include <string>
#include <iostream>

template <typename T>
class Vec {
public:
    Vec() : sz{0}, cap{1}, a{new T[cap]} {}

    ~Vec() {
        delete[] a;
    }

    Vec(const Vec&) = delete;
    Vec& operator=(const Vec&) = delete;

    // This is how we can explicitly request compiler-generated versions:
    // Vec(const Vec&) = default;
    // Vec& operator=(const Vec&) = default;

    Vec(Vec&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
        std::cout << "move ctor" << std::endl;
    }

    Vec& operator=(Vec&& tmp) {
        if (this != &tmp) {
            delete[] a;

            sz = tmp.sz;
            cap = tmp.cap;
            a = tmp.a;

            tmp.sz = tmp.cap = 0;
            tmp.a = nullptr;
        }
        std::cout << "move assignment" << std::endl;
        return *this;
    }

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }

    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(T x) {
        if (sz == cap) {
            // Separate cap*=2 to provide strong exception guarantee
            // T *a2 = new T[cap *= 2];
            T *a2 = new T[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    size_t sz;
    size_t cap;
    T *a;
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const Vec<T>& ia) {
    for (size_t i = 0; i < ia.size(); i++) {
        os << ia[i] << " ";
    }
    std::cout << "(cap=" << ia.capacity() << ")" << std::flush;
    return os;
}

Vec<int> createVecInt() {
    Vec<int> tmp;
    for (int i = 0; i < 20; i++) {
        tmp.push_back(i);
        std::cout << tmp << std::endl;
    }
    return tmp;
}

Vec<std::string> createVecStr()
{
    Vec<std::string> tmp;
    for (char c = 'A'; c <= 'Z'; c++) {
        std::string s;
        s += c;
        tmp.push_back(s);
        std::cout << tmp << std::endl;
    }
    return tmp;
}

int main() {
    using namespace std;

    Vec<int> v { createVecInt() };

    Vec<string> v2 { createVecStr() };
}

/* Lecture outline:

1.  turning IntArray into a class template

    - change IntArray to Vec
    - change data type to T
    - add template <typename T>
    - change operator<<() to a function template
    - need to specify element type when declaring Vec - Vec<int> and Vec<string>

*/

vec2.cpp

#include <string>
#include <vector>
#include <iostream>

int main() {
    using namespace std;

    vector<string> v;
    for (char c = 'A'; c <= 'Z'; c++) {
        string s;
        s += c;
        v.push_back(s);

        for (size_t i = 0; i < v.size(); ++i) {
            cout << v[i] << " ";
        }
        cout << endl;
    }
}

/* Lecture outline:

2.  Using vector instead of Vec

    - std::vector works the same way, with a lot more power!

    - range-for loop:
        for (string e : v) { cout << e << " "; }
        for (const string& e : v) { cout << e << " "; }
        for (const auto& e : v) { cout << e << " "; }

3.  Value semantics of STL containers

    - all STL containers (i.e., C++ standard library containers) hold
      their elements by value

*/

vec3.cpp

#include <iostream>
#include "mystring.h"

/*
 * Slightly modified version of Vec class template:
 * 1. copy & move ops are deleted
 * 2. push_back() is changed to take const T&
 */
template <typename T>
class Vec {
public:
    Vec() : sz{0}, cap{1}, a{new T[cap]} {}
    ~Vec() { delete[] a; }

    Vec(const Vec&) = delete;
    Vec& operator=(const Vec&) = delete;
    Vec(Vec&&) = delete;
    Vec& operator=(Vec&&) = delete;

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }
    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(const T& x) {
        if (sz == cap) {
            T *a2 = new T[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    size_t sz;
    size_t cap;
    T *a;
};

int main() {
    using namespace std;

    Vec<MyString> v;
    v.push_back("abc");
    v.push_back("def");
    MyString s{"xyz"};
    v.push_back(s);

    cout << "size:     " << v.size() << endl;
    cout << "capacity: " << v.capacity() << endl;
    for (size_t i = 0; i < v.capacity(); ++i) {
        cout << "v[" << i << "]: " << '"' << v[i] << '"' << endl;
    }
}

/* Lecture outline:

4.  Stack & heap diagram for the following sequence of code:

        Vec<MyString> v;
        v.push_back("abc");
        v.push_back("def");
        MyString s{"xyz"};
        v.push_back(s);

    - Vec<MyString> holds MyString objects by value
    
    - There is no copy construction of MyString objects
        - MyString objects are default-constructed when capacity increases
        - push_back() invokes MyString::operator=()

5.  Placement new

    - std::vector does not default-construct elements on empty slots
    - It simply allocates memory to hold future objects
    - How does vector::push_back() construct an object at existing memory?
    - Placement new syntax:

        new (p) MyString{"xyz"};

*/