Parent directory
Makefile
intarray1.cpp
intarray2.cpp
intarray3.cpp
mystring.cpp
mystring.h
rvalue-test.cpp
vec1.cpp
vec2.cpp
vec3.cpp
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
#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
*/
#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
*/
#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()
*/
#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];
}
#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
#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
}
#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>
*/
#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
*/
#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"};
*/