HW3 EE538
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
HW3 EE538
Q1 Solution
#include "q.h"
#include <iostream>
#include <vector>
// Implement each function of `q.h` here.
// Creates an empty vector.
MyVector::MyVector() {
size_ = 0;
data_ = nullptr;
error_ = ErrorCode::kNoError;
}
// Creates a vector of the given size.
MyVector::MyVector(int size) {
size_ = size;
data_ = new int[size];
error_ = ErrorCode::kNoError;
}
// Copy constructor.
MyVector::MyVector(const MyVector& rhs) {
size_ = rhs.size();
data_ = new int[rhs.size()];
for (int i = 0; i < rhs.size(); i++) {
data_[i] = rhs.data_[i];
}
error_ = ErrorCode::kNoError;
}
// Destructor.
MyVector::~MyVector() {
if (size_ > 0 && data_ != nullptr) {
delete data_;
}
}// Inserts the given value at the back of the vector.
void MyVector::push_back(int value) {
error_ = ErrorCode::kNoError;
int* new_data = new int[size_ + 1];
for (int i = 0; i < size_; i++) {
new_data[i] = data_[i];
}
delete data_;
data_ = new_data;
data_[size_] = value;
size_++;
}
// Removes and returns a value from the backs of the vector.
// Returns -1 if error and sets the error_ variable.
int MyVector::pop_back() {
error_ = ErrorCode::kNoError;
if (size_ == 0) {
error_ = ErrorCode::kPopFromEmptyVector;
return -1;
}
int result = data_[size_ - 1];
int* new_data = new int[size_ - 1];
for (int i = 0; i < size_ - 1; i++) {
new_data[i] = data_[i];
}
delete data_;
data_ = new_data;
size_--;
return result;
}
// Inserts the given value at the front of the vector.
void MyVector::push_front(int value) {
error_ = ErrorCode::kNoError;int* new_data = new int[size_ + 1];
new_data[0] = value;
for (int i = 0; i < size_; i++) {
new_data[i + 1] = data_[i];
}
delete data_;
data_ = new_data;
size_++;
}
// Removes and returns a value from the front of the vector.
int MyVector::pop_front() {
error_ = ErrorCode::kNoError;
if (size_ == 0) {
error_ = ErrorCode::kPopFromEmptyVector;
return -1;
}
int result = data_[0];
int* new_data = new int[size_ - 1];
for (int i = 0; i < size_; i++) {
new_data[i] = data_[i + 1];
}
delete data_;
data_ = new_data;
size_--;
return result;
}
// Inserts the given value after the given index.
void MyVector::insert(int value, int index) {
error_ = ErrorCode::kNoError;
if (index < -1 || index > size_ - 1) {
error_ = ErrorCode::kIndexError;return;
}
int* new_data = new int[size_ + 1];
int i = 0;
for (; i <= index; i++) {
new_data[i] = data_[i];
}
new_data[i] = value;
i++;
for (; i < size_ + 1; i++) {
new_data[i] = data_[i - 1];
}
delete data_;
data_ = new_data;
size_++;
}
// Returns item at the given index. Returns -1 if error and sets
error_.
int MyVector::at(int index) {
error_ = ErrorCode::kNoError;
if (index < 0 || index > size_ - 1) {
error_ = ErrorCode::kIndexError;
return -1;
}
return data_[index];
}
// Returns the first index of the given item in the vector. Returns
-1 if not
// found, and sets error_.
int MyVector::find(int item) {
error_ = ErrorCode::kNoError;for (int i = 0; i < size_; i++) {
if (data_[i] == item) {
return i;
}
}
error_ = ErrorCode::kNotFound;
return -1;
}
// Returns the value of error_
ErrorCode MyVector::get_error() const { return error_; }
// Returns the value of size_
int MyVector::size() const { return size_; }
// Converst to std::vector. Used for testing.
std::vector<int> MyVector::ConvertToStdVector() {
error_ = ErrorCode::kNoError;
std::vector<int> result;
for (int i = 0; i < size_; i++) {
result.push_back(data_[i]);
}
return result;
}
Q2 Solution
#include "q.h"
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
// Implement each function of `q.h` here.
// Given an expression string, find if the input has valid brackets (i.e.{ }
// or [ ] or ( ) ).
bool CPPLib::CheckValidExpression(const std::string& input) {
std::stack<char> stack;
std::set<char> open_brackets = {'{', '[', '('};
std::set<char> close_brackets = {'}', ']', ')'};
std::map<char, char> match = {//
{'}', '{'},
{']', '['},
{')', '('}};
for (auto& e : input) {
if (open_brackets.find(e) != open_brackets.end()) {
stack.push(e);
}
if (close_brackets.find(e) != close_brackets.end()) {
if (stack.empty() || stack.top() != match[e]) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
bool CPPLib::IsPalindrome(const std::string& input) {
int l = 0;
int r = input.size() - 1;
while (l < r) {
if (input[l] != input[r]) {
return false;
}
l++;
r--;
}
return true;
}
int CPPLib::OddChar(const std::string& input) {
char sum = 0;
// We use bitwise XOR.
for (const auto& e : input) {sum ^= e;
}
return sum;
}
Q3 Solution
#include "q.h"
#include <iostream>
#include <vector>
// Implement each function of `q.h` here.
// Copy constructor.
Queue::Queue(const Queue& rhs) { v_ = rhs.v_; }
bool Queue::Enqueue(int value) {
v_.push_back(value);
return true;
}
bool Queue::Dequeue() {
if (v_.size() == 0) {
return false;
}
v_.erase(v_.begin());
return true;
}
bool Queue::IsEmpty() { return (v_.size() == 0); }
// Returns the value in the front of the queue.
int Queue::Front() {
if (v_.size() == 0) {
return -1;
}
return v_[0];
}Q4 Solution
#include "q.h"
#include <iostream>
#include <map>
#include <set>
#include <vector>
// No need for unit tests for this question.
// TODO: Answer each question in the main() function the README file.
// The following functions are used for measuring the time of an operation.
You
// don't need to change them.
//
// StoreStartTime(); -> Stores the current time.
// Operation(); -> The operation we are measuring.
// PrintAndGetDuration(); -> Print the time from StoreStartTime until now.
//
//-------------------------------------------------------------------------
----
// No need to change the following definitions!
class MyClass {
public:
MyClass() {
a_ = 0;
b_ = 0;
ptr_ = new int;
std::cout << "Non-parameterized constructor" << std::endl;
}
MyClass(int a, int b) {
ptr_ = new int;
a_ = a;
b_ = b;
std::cout << "Parameterized constructor" << std::endl;
}
MyClass(int size) {
ptr_ = new int;
a_ = 0;
b_ = 0;
for (int i = 0; i < size; i++) {v_.push_back(i);
}
std::cout << "Parameterized constructor" << std::endl;
}
MyClass(const MyClass &rhs) {
a_ = rhs.a_;
b_ = rhs.b_;
v_ = rhs.v_;
ptr_ = new int;
*ptr_ = *rhs.ptr_;
std::cout << "Copy constructor" << std::endl;
}
~MyClass() {
if (ptr_ != nullptr) {
delete ptr_;
ptr_ = nullptr;
}
std::cout << "Destructor" << std::endl;
}
public:
std::vector<int> v_;
private:
int a_;
int b_;
int *ptr_;
};
//-------------------------------------------------------------------------
----
// No need to change the following definitions!
// These are some simple functions that we will call from main.
void DoSomthing1(MyClass o) { std::cout << "Something 1." << std::endl; }
void DoSomthing2(MyClass &o) { std::cout << "Something 2." << std::endl; }
void DoSomthing3(MyClass &o) { std::cout << "Something 3." << std::endl; }
void DoSomthing4(MyClass &o) {MyClass o2 = o;
std::cout << "Something 4." << std::endl;
}
//-------------------------------------------------------------------------
----
int main() {
// Q1
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q1" << std::endl;
MyClass o1;
std::cout << "o1.v_.size(): " << o1.v_.size() << std::endl;
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: This block calls the non-parameterized constructor. The vector v_
gets
// initialized because it's a member variable. But the non-parameterized
// constructor does not push values to the vector v_ so the size of
v_should
// be 0.
// Q2
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q2" << std::endl;
MyClass o1;
MyClass o2(1, 3);
MyClass o3 = o1;
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: Instance o1 is initialized with a Non-parameterized constructor.
// Instance o2 is initialized with a Parameterized constructor.// Instance o3 is initialized with a copy constructor and it's a copy of
o1.
// There are three destructor calls. Each for each object.
// Q3
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q3" << std::endl;
MyClass o;
DoSomthing1(o);
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: o is initialized with a Non-parameterized constructor.
// Then the instance o is passed in the function DoSomthing1 by value,
hence
// the copy constructor is called to copy theparameter. Since pass by
value
// makes a copy of the passed object, 2 objects get created Therefore,
// destructor gets called twice.
// Q4
// What is the output? Explain why each line (or group of lines) are
printed.
// Why the output is different than the previous question?
{
std::cout << "Q4" << std::endl;
MyClass o;
DoSomthing2(o);
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: o is initialized with a Non-parameterized constructor. Since the
// function DoSomthing2 uses pass by value, there is no copy constructor,
the
// object o is the only object gets initialized, the destructor only gets
// called once.// Q5
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q5" << std::endl;
MyClass o;
DoSomthing3(o);
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: o is initialized with a Non-parameterized constructor. Since the
// function DoSomthing3 uses pass by value, there is no copy constructor,
the
// object o is the only object gets initialized, the destructor only gets
// called once.
// Q6
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q6" << std::endl;
MyClass o;
DoSomthing4(o);
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: o is initialized with a Non-parameterized constructor.
// Then the instance o is passed in the function DoSomthing4 by
reference.
// DoSomthing4 creates an internal object for which the copy constructor
is
// called. Since 2 objects get created, destructor gets called twice,
once at
// the end of DoSomething 4, and once at the end of the Q6 scope.
{
// Q7
// What is the output? Explain why each line (or group of lines) are// printed.
// Notice that std::pair might internally copy objects of MyClass.
Please
// specify those calls.
std::cout << "Q7" << std::endl;
std::pair<MyClass, int> p1 = {MyClass(1, 2), 0};
std::cout << "p1.first.v_.size(): " << p1.first.v_.size() << std::endl;
std::cout << "p1.second: " << p1.second << std::endl;
std::pair<MyClass, int> p2 = p1;
std::cout << "p2.first.v_.size(): " << p2.first.v_.size() << std::endl;
std::cout << "p2.second: " << p2.second << std::endl;
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// ANS: Parameterized constructor is called in the second line, with a_,
b_
// initialized to 1, 2 Also in the second line, the std::pair internally
copy
// objects of MyClass and then call the destructor. Third and fourth line
are
// printing the corresponding values: size of v_ and value of pair
second. The
// fifth line calls a copy constructor to make a copy of p1. The sixth
line
// prints the size of v_ in p2 first class. The seventh line prints the
value
// of p2.second.
// There are two objects that need to be destructed at the end of the
scope.
// Q8
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q8" << std::endl;
for (std::pair<MyClass, int> p = {MyClass(1, 2), 0}; p.second < 3;
p.second++) {
p.first.v_.push_back(p.second);
DoSomthing2(p.first);}
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// At the beginning of the loop, we create a pair using the parameterized
// constructor. The pair will internally call copy constructor and the
// destructor. The for loop indices are created based on the value of
// p.second. In each iteration, push value of p.second into the v_ of
p.first
// (an instance of MyClass). Also call DoSomthing2 to do printing After
// finished using p, which is pass-by-reference. The destructor is called
at
// the end because we only have one object of MyClass in the pair.
// Q9
// What is the output? Explain why each line (or group of lines) are
printed.
// Why the destructor is not called? Is this a problem? If so, what is it
// called?
{
std::cout << "Q9" << std::endl;
MyClass *o;
o = new MyClass(1, 2);
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// Line 2 Creates a MyClass pointer named "o"
// Line 3 calls parameterized constructor with initial input values as 1
// and 2.
// Yes, there is a problem! At the end of the scope o is lost and we will
have
// memory leak.
// Q10
// What is the output? Explain why each line (or group of lines) are
printed.
// Why the destructor is called?
{
std::cout << "Q10" << std::endl;MyClass *o;
o = new MyClass(1, 2);
delete o;
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// Line 2 Creates a MyClass pointer named "o"
// Line 3 calls parameterized constructor with initial input values as 1
// and 2. Line 4 free the memory pointed by pointer "o". Hence the call
to
// destructor.
// Q11
// What is the output? Explain why each line (or group of lines) are
printed.
// Notice that std::map might internally copy objects of MyClass. Please
// specify those calls.
{
std::cout << "Q11" << std::endl;
std::map<int, MyClass> my_map = {//
{0, MyClass()},
{3, MyClass(1, 2)},
{5, MyClass(3, 4)}};
std::set<int> my_set;
for (auto e : my_map) {
my_set.insert(e.first);
}
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// Line 2-5 creates a map variable with integer, MyClass as the key value
pair
// Instance in the first pair is created using non-parameterized
constructor
// std::pair also internally copy objects of MyClass, so copy constructor
is// called.
// Instance in the second pair is created using parameterized
// constructor.
// std::map also internally copy objects of MyClass, so copy
// constructor is called.
// Instance in the third pair is created using
// parameterized constructor.
// std::map also internally copy objects of
// MyClass, so copy constructor is called.
// Destructor is called 6 times to free
// up the memory for the temporary objects that was internally created by
// std::map. In the last loop, in each iteration, we are making a copy of
the
// MyClass instance when iterating through the map. A destructor is
called for
// each object that we copy at the end of each iteration of the loop. A
// destructor is called at the end of the scope once for each item in the
map.
// Q12
// What is the output? Explain why each line (or group of lines) are
printed.
// Notice that std::map and set might internally copy objects of MyClass.
// Please specify those calls.
{
std::cout << "Q12" << std::endl;
std::map<int, MyClass> my_map = {//
{0, MyClass()},
{3, MyClass(1, 2)},
{5, MyClass(3, 4)}};
std::set<int> my_set;
for (const auto &e : my_map) {
my_set.insert(e.first);
}
}
// Similar to the previous question, however in the loop we don't make
copies
// so no copy constructor and no destructor will be called.
std::cout <<
"---------------------------------------------------------------"<< std::endl;
// Q13
// What is the output? Explain why each line (or group of lines) are
printed.
{
std::cout << "Q13" << std::endl;
MyClass *o;
o = new MyClass(1, 2);
delete o;
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// Similar to Q10.
// Q14
// What is the output? Explain why each line (or group of lines) are
printed.
// Explain the time of the measured operations.
{
std::cout << "Q14" << std::endl;
StoreStartTime();
MyClass o(100000000);
PrintAndGetDuration();
StoreStartTime();
for (int i = 0; i < 2; i++) {
MyClass o2 = o;
DoSomthing1(o2);
std::cout << "o2.v_.size(): " << o2.v_.size() << std::endl;
}
PrintAndGetDuration();
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// The 2nd line starts the timer. 3rd line use a parameterized
constructor
// that pushes 100000000 items in the vector. This takes a long time.
// The 4th line// prints the duration of constructing the object.
// The 5th line starts the timer
// again.
// The for loop iterates 3 times. Each iteration, make a copy of the
// instance o, assign to o2 using copy constructor.
// DoSomthing1 pass object by value, it makes a copy.
// Then print the size of v_ of o2.
// After the loop we print duration. Since we have
// pass by value, and also o2 is a copy o, we spend a long time in copy
// constructor function multiple times. At the end of each iteration o2
is
// destructed. At the end of the scope o is destructed.
// Q15
// What is the output? Explain why each line (or group of lines) are
printed.
// Explain the time of the measured operations.
{
std::cout << "Q15" << std::endl;
StoreStartTime();
MyClass o(100000000);
PrintAndGetDuration();
StoreStartTime();
for (int i = 0; i < 2; i++) {
MyClass o2 = o;
DoSomthing2(o2);
std::cout << "o2.v_.size(): " << o2.v_.size() << std::endl;
}
PrintAndGetDuration();
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
// Similar to the previous question except that since DoSomething2 is
// pass-by-reference, it takes less time, and we don't call the copy
// constructor and destructor in that function. Note that we are still
calling
// copy constructor and destructor for o2 at each iteration.
// Q16
// What is the output? Explain why each line (or group of lines) areprinted.
// Notice that std::vector might internally copy objects of MyClass.
Please
// specify those calls.
// Explain the time of the measured operations.
{
std::cout << "Q16" << std::endl;
StoreStartTime();
std::vector<MyClass> my_vector = {MyClass(10000000), MyClass(20000000),
MyClass(30000000), MyClass(40000000),
MyClass(50000000), MyClass(60000000),
MyClass(70000000)};
PrintAndGetDuration();
StoreStartTime();
for (auto e : my_vector) {
std::cout << "e.v_.size(): " << e.v_.size() << std::endl;
}
PrintAndGetDuration();
StoreStartTime();
for (const auto &e : my_vector) {
std::cout << "e.v_.size(): " << e.v_.size() << std::endl;
}
PrintAndGetDuration();
}
std::cout <<
"---------------------------------------------------------------"
<< std::endl;
std::cout << "Done!" << std::endl;
}
// The 2nd line starts the timer. 3-6 line use parameterized constructors
to
// initialize 7 MyClass objects with parameterized constructor, with
different
// input values. std::vector internally calls copy constructor and
destructor.
// When creating my_vector, copy constructor is called for each
// object in my_vector. After that, destructor is called for each object
// created. The first loop makes copies, hence a copy constructor and a
// destructor is called. The second loop calls just creates a reference so
it is// much faster and no copy constructor or destructor is called. Both loops
print
// the size of v_ of MyClass object.
// There are seven destructor calls at the end for each element of the
vector.
Q5 Solution
#include "q.h"
#include <iostream>
#include <unordered_set>
#include <vector>
// Implement each function of `q.h` here.
ListNode *SinglyLinkedList::GetIthPointer(int i) {
if (empty() || i < 0 || i > size() - 1) {
return nullptr;
}
ListNode *p = head_;
int count = 0;
while (p->next != nullptr && count < i) {
p = p->next;
count++;
}
return p;
}
int &SinglyLinkedList::operator[](int i) {
if (GetIthPointer(i) == nullptr) {
return minusOne_;
} else
return GetIthPointer(i)->val;
}
void SinglyLinkedList::push_back(int i) {
// If list empty, create a new node and point head_ to it
if (empty()) {
head_ = new ListNode(i);return;
}
// If not empty, go to the end, create a new node and point the last item
to
// it
auto back_ptr = GetBackPointer();
auto newNode = new ListNode(i);
back_ptr->next = newNode;
}
bool SinglyLinkedList::empty() { return head_ == nullptr; }
int SinglyLinkedList::size() {
if (empty()) {
return 0;
}
int s = 0;
ListNode *p = head_;
while (p) {
s++;
p = p->next;
}
return s;
}
ListNode *SinglyLinkedList::GetBackPointer() {
if (empty()) {
return head_;
}
ListNode *p = head_;
while (p->next != nullptr) {
p = p->next;
}
return p;
}
int SinglyLinkedList::back() {
if (empty()) {
return -1;
}
return GetBackPointer()->val;
}std::vector<int> SinglyLinkedList::convert_to_vector() {
std::vector<int> result;
if (!empty()) {
ListNode *p = head_;
while (p->next != nullptr) {
result.push_back(p->val);
p = p->next;
}
result.push_back(p->val);
}
return result;
}
// Erases element i from the list if it exists and returns a pointer to
item
// i-1. If item i doesn't exist, returns nullptr. The first item in the
list
// has index 0.s
// Example:
// Input: 1 -> 5 -> 10 ->20, i= 2.
// Output: 1 -> 5 -> 20, return value: a pointer to element 5.
ListNode *SinglyLinkedList::erase(int i) {
if (i > size() - 1) {
return nullptr;
}
auto ptr_i = GetIthPointer(i);
auto ptr_before_i = GetIthPointer(i - 1);
if (ptr_before_i) {
ptr_before_i->next = ptr_i->next;
delete ptr_i;
return ptr_before_i;
} else {
head_ = ptr_i->next;
delete ptr_i;
return nullptr;
}
}
// Removes an item from the back of the list. Returns true if it was
// successfull.
bool SinglyLinkedList::pop_back() {
if (empty()) {return false;
}
erase(size() - 1);
return true;
}
SinglyLinkedList::SinglyLinkedList(const std::vector<int> &v) {
head_ = nullptr;
for (auto e : v) {
push_back(e);
}
}
SinglyLinkedList::SinglyLinkedList(const SinglyLinkedList &rhs) {
auto ptr = rhs.head_;
head_ = nullptr;
while (ptr) {
push_back(ptr->val);
ptr = ptr->next;
}
}
ListNode *SinglyLinkedList::head() { return head_; }
void SinglyLinkedList::remove_duplicates() {
std::unordered_set<int> s;
for (int i = 0; i < size(); i++) {
auto val = (*this)[i];
if (std::find(s.begin(), s.end(), val) != s.end()) {
erase(i--);
} else {
s.insert(val);
}
}
}
2022-07-07