cpp/cs104/iterators/iter2

Viewing cpp/cs104/iterators/iter2_problem by redekopp@usc.edu. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Consider the problem of passing an LList<T> as a const reference to a function. Would you be able to iterate over the values?
<p>
In theory you should be able to since iteration doesn't mean you will change the data. But look carefully at the declarations of
<tt>begin()</tt> and <tt>end()</tt>. Consider some possible attempts to fix this.
<p>
Once you get it to compile try to change the <tt>cout</tt> line in <tt>print_all</tt> to actually modify data. <br>
You should not be allowed to modify data.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

Copied from problem cpp/cs104/iterators/iter1 (author: redekopp@usc.edu)

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <stdexcept>

template <typename T>
struct Item {
T val;
Item<T> *next;
};

template <typename T>
class LList {
public:
LList();
~LList();
bool empty() const;
int size() const;
void insert(int loc, T val);
void pop(int loc);
T& get(int loc);
T const & get(int loc) const;
\hide[
private:
Item<T> *getNodeAt(int loc) const;
]\
private:
Item<T> *head_;
int size_;

public:
class iterator {
// add private data and functions each iterator object needs
private:
friend class LList<T>;
Item<T>* curr_;
iterator(Item<T>* init) : curr_(init) { }
public:
iterator() : curr_(NULL) { }
// Add operator*
T& operator*() { return curr_->val; }
// Add operator->
T* operator->() { return &curr_->val; }

// Add the pre-inc operator (e.g. ++it);
// It should return a reference to itself
iterator& operator++() { curr_=curr_->next; return *this ; }

// Add the post-inc operator (e.g. it++);
// It should return a copy of its old state
iterator operator++(int dummy) {
iterator tmp(curr_);
curr_=curr_->next;
return tmp;
}
bool operator!=(const iterator & other) { return curr_ != other.curr_; }
bool operator==(const iterator & other) { return curr_ == other.curr_; }
};
// Add any necessary member functions of LList to create
\[
REDACTED
\show:
iterator begin() { iterator it(head_); return it; }
iterator end() { iterator it(NULL); return it; }
]\

};

// Assume member functions of LList<T> are implemented
\hide[
template <typename T>
LList<T>::LList()
{
head_ = NULL;
size_ = 0;
}

template <typename T>
LList<T>::~LList()
{
while(head_ != NULL){
Item<T> *temp = head_->next;
delete head_;
head_ = temp;
}
}

template <typename T>
bool LList<T>::empty() const
{
return head_ == NULL;
}

template <typename T>
int LList<T>::size() const
{
return size_;
}

template <typename T>
void LList<T>::insert(int loc, T val)
{
if(!head_ && loc != 0){
throw std::invalid_argument("bad location");
}
else if(loc == 0){
Item<T> *old_head = head_;
head_ = new Item<T>;
head_->val = val;
head_->next = old_head;
size_++;
}
else {
Item<T> *temp = getNodeAt(loc-1);
Item<T> *newitem = new Item<T>;
newitem->val = val;
newitem->next = temp->next;
temp->next = newitem;
size_++;
}
}

template <typename T>
void LList<T>::pop(int loc)
{
if(!head_){
throw std::invalid_argument("bad location");
}
Item<T> *temp = head_;
if(loc == 0){
// take the Item out of the list
head_ = head_->next;
delete temp;
}
else {
temp = getNodeAt(loc-1);
Item<T> *to_pop = temp->next;
temp->next = to_pop->next;
delete to_pop;
}
size_--;
}

template <typename T>
T& LList<T>::get(int loc)
{
Item<T> *temp = getNodeAt(loc);
return temp->val;
}

template <typename T>
T const & LList<T>::get(int loc) const
{
Item<T> *temp = getNodeAt(loc);
return temp->val;
}

template <typename T>
Item<T>* LList<T>::getNodeAt(int loc) const
{
Item<T> *temp = head_;
while(temp && loc != 0){
temp = temp->next;
loc--;
}
if(loc != 0){
throw std::invalid_argument("bad location");
}
return temp;
}
]\

#include <iostream>
using namespace std;
void print_all(const LList<int>& lst)
{
for(LList<int>::iterator it = lst.begin();
it != lst.end();
++it )
{
\[
REDACTED
\show:
cout << *it << endl;
]\
}
}

void change_all(LList<int>& lst)
{
for(LList<int>::iterator it = lst.begin();
it != lst.end();
++it
)
{ *it = 8; }
}

int main()
{
LList<int> lst;
const int numElems = 5;
for(int i=0; i < numElems; i++){
lst.insert(i, i+1);
}
// Print original
print_all(lst);
// Update values
change_all(lst);
// Print updated values
print_all(lst);

for(int i=0; i < numElems; i++){
lst.pop(0);
}
return 0;
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[{}]
C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Consider the problem of passing an LList<T> as a const reference to a function. Would you be able to iterate over the values? <p> In theory you should be able to since iteration doesn't mean you will change the data. But look carefully at the declarations of <tt>begin()</tt> and <tt>end()</tt>. Consider some possible attempts to fix this. <p> Once you get it to compile try to change the <tt>cout</tt> line in <tt>print_all</tt> to actually modify data. <br> You should not be allowed to modify data.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	Copied from problem cpp/cs104/iterators/iter1 (author: redekopp@usc.edu) remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <stdexcept> template <typename T> struct Item { T val; Item<T> next; }; template <typename T> class LList { public: LList(); ~LList(); bool empty() const; int size() const; void insert(int loc, T val); void pop(int loc); T& get(int loc); T const & get(int loc) const; \hide[ private: Item<T> getNodeAt(int loc) const; ]\ private: Item<T> head_; int size_; public: class iterator { // add private data and functions each iterator object needs private: friend class LList<T>; Item<T> curr_; iterator(Item<T>* init) : curr_(init) { } public: iterator() : curr_(NULL) { } // Add operator* T& operator() { return curr_->val; } // Add operator-> T operator->() { return &curr_->val; } // Add the pre-inc operator (e.g. ++it); // It should return a reference to itself iterator& operator++() { curr_=curr_->next; return this ; } // Add the post-inc operator (e.g. it++); // It should return a copy of its old state iterator operator++(int dummy) { iterator tmp(curr_); curr_=curr_->next; return tmp; } bool operator!=(const iterator & other) { return curr_ != other.curr_; } bool operator==(const iterator & other) { return curr_ == other.curr_; } }; // Add any necessary member functions of LList to create \[ REDACTED \show: iterator begin() { iterator it(head_); return it; } iterator end() { iterator it(NULL); return it; } ]\ }; // Assume member functions of LList<T> are implemented \hide[ template <typename T> LList<T>::LList() { head_ = NULL; size_ = 0; } template <typename T> LList<T>::~LList() { while(head_ != NULL){ Item<T> temp = head_->next; delete head_; head_ = temp; } } template <typename T> bool LList<T>::empty() const { return head_ == NULL; } template <typename T> int LList<T>::size() const { return size_; } template <typename T> void LList<T>::insert(int loc, T val) { if(!head_ && loc != 0){ throw std::invalid_argument("bad location"); } else if(loc == 0){ Item<T> old_head = head_; head_ = new Item<T>; head_->val = val; head_->next = old_head; size_++; } else { Item<T> temp = getNodeAt(loc-1); Item<T> newitem = new Item<T>; newitem->val = val; newitem->next = temp->next; temp->next = newitem; size_++; } } template <typename T> void LList<T>::pop(int loc) { if(!head_){ throw std::invalid_argument("bad location"); } Item<T> temp = head_; if(loc == 0){ // take the Item out of the list head_ = head_->next; delete temp; } else { temp = getNodeAt(loc-1); Item<T> to_pop = temp->next; temp->next = to_pop->next; delete to_pop; } size_--; } template <typename T> T& LList<T>::get(int loc) { Item<T> temp = getNodeAt(loc); return temp->val; } template <typename T> T const & LList<T>::get(int loc) const { Item<T> temp = getNodeAt(loc); return temp->val; } template <typename T> Item<T> LList<T>::getNodeAt(int loc) const { Item<T> temp = head_; while(temp && loc != 0){ temp = temp->next; loc--; } if(loc != 0){ throw std::invalid_argument("bad location"); } return temp; } ]\ #include <iostream> using namespace std; void print_all(const LList<int>& lst) { for(LList<int>::iterator it = lst.begin(); it != lst.end(); ++it ) { \[ REDACTED \show: cout << it << endl; ]\ } } void change_all(LList<int>& lst) { for(LList<int>::iterator it = lst.begin(); it != lst.end(); ++it ) { *it = 8; } } int main() { LList<int> lst; const int numElems = 5; for(int i=0; i < numElems; i++){ lst.insert(i, i+1); } // Print original print_all(lst); // Update values change_all(lst); // Print updated values print_all(lst); for(int i=0; i < numElems; i++){ lst.pop(0); } return 0; }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[{}]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.