ผลต่างระหว่างรุ่นของ "Adt lab/linked lists"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 26: แถว 26:
  
 
== Linked list class ==
 
== Linked list class ==
 +
<source lang="cpp">
 +
typedef int valueType;
 +
 +
struct ListNode
 +
{
 +
  valueType val;
 +
  ListNode* next;
 +
 +
  ListNode(valueType val, ListNode* next=0)
 +
    : val(val), next(next) {}
 +
};
 +
 +
class LinkedList
 +
{
 +
private:
 +
  ListNode* header;
 +
  void free_list();
 +
 +
public:
 +
  LinkedList();
 +
  ~LinkedList();
 +
  void print_list();
 +
  void insert_front(valueType x);
 +
};
 +
 +
LinkedList::LinkedList()
 +
{
 +
  header = new ListNode(0);
 +
}
 +
 +
LinkedList::~LinkedList()
 +
{
 +
  free_list();
 +
}
 +
 +
void LinkedList::print_list()
 +
{
 +
  ListNode* node = header->next;
 +
  while(node != 0) {
 +
    cout << node->val << endl;
 +
    node = node->next;
 +
  }
 +
}
 +
 +
void LinkedList::insert_front(valueType x)
 +
{
 +
}
 +
 +
void LinkedList::free_list()
 +
{
 +
}
 +
</source>
 +
 +
== Copy constructor and assignment operator ==
 +
 +
You can't pass an object of class <tt>LinkedList</tt> that we have written by value to other functions.  For example, if you write
 +
 +
<source lang="cpp">
 +
void test(LinkedList l)
 +
{
 +
  l.append(1000);
 +
}
 +
 +
main()
 +
{
 +
  LinkedList l1;
 +
 +
  test(l1);
 +
 
 +
  l1.append(10);
 +
}
 +
</source>
 +
 +
When you run your program, you may get this run-time error:
 +
 +
*** Error in `./a.out': double free or corruption (fasttop): 0x0000000002138010 ***
 +
 +
This happens because the destructor has been called twice: once for <tt>l1</tt> and another for its copy <tt>l</tt> in function test.  However, its copy, by default, was created by copying every data members of <tt>l1</tt>, i.e., its header and tail pointers point to the same location as of <tt>l1</tt>.  When the list <tt>l</tt> was destroyed, its destructor also destroyed the original list data.
 +
 +
To prevent this problem, you can pass <tt>l1</tt> by reference as in the next code.  In this case l and l1 is the same list.
 +
 +
<source lang="cpp">
 +
void test(LinkedList& l)
 +
{
 +
  l.append(1000);
 +
}
 +
 +
main()
 +
{
 +
  LinkedList l1;
 +
 +
  test(l1);
 +
 
 +
  l1.append(10);
 +
}
 +
</source>
 +
 +
But if you want l and l1 to be different lists, you need to implement its '''copy constructor''' yourself to handle object copy.  (Read more at [https://en.wikipedia.org/wiki/Copy_constructor_(C%2B%2B) copy constructor's article at wikipedia])
 +
 +
Another case when default copying operation does not work is when you use assignments, as in:
 +
 +
<source lang="cpp">
 +
  LinkedList l1, l2;
 +
 +
  l2 = l1;
 +
</source>
 +
 +
In C++, [https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming) Rule of three] states that if you implement any of these methods, you should implement all three:
 +
 +
* destructor
 +
* copy constructor
 +
* copy assignment operator
 +
 +
The following shows the code for copy constructor and copy assignment operator for our LinkedList class.
 +
 +
<source lang="cpp">
 +
class LinkedList
 +
{
 +
// ...
 +
 
 +
public:
 +
  LinkedList();
 +
  LinkedList(const LinkedList& list);
 +
 +
  // ...
 +
  LinkedList& operator=(const LinkedList& list);
 +
};
 +
</source>
 +
 +
<source lang="cpp">
 +
LinkedList::LinkedList(const LinkedList& list)
 +
{
 +
  header = new ListNode(0);
 +
  tail = header;
 +
  ListNode* p = list.header->next;
 +
  while(p != 0) {
 +
    append(p->val);
 +
    p = p->next;
 +
  }
 +
}
 +
 +
LinkedList& LinkedList::operator=(const LinkedList& list)
 +
{
 +
  if(this != &list) {
 +
    free_list();
 +
    header = new ListNode(0);
 +
    tail = header;
 +
    ListNode* p = list.header->next;
 +
    while(p != 0) {
 +
      append(p->val);
 +
      p = p->next;
 +
    }
 +
  }
 +
}
 +
</source>
 +
 +
=== Copy-and-swap idiom ===
 +
 +
Read at [http://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom stackoverflow].
 +
 +
Here is a new version of the assignment operator using the copy-and-swap idiom.
 +
 +
<source lang="cpp">
 +
class LinkedList
 +
{
 +
// ...
 +
public:
 +
  // ...
 +
  LinkedList& operator=(LinkedList list);
 +
 +
  void swap(LinkedList& l1, LinkedList& l2);
 +
};
 +
</source>
 +
 +
<source lang="cpp">
 +
void LinkedList::swap(LinkedList& l1, LinkedList& l2)
 +
{
 +
  std::swap(l1.header, l2.header);
 +
  std::swap(l1.tail, l2.tail);
 +
}
 +
 +
LinkedList& LinkedList::operator=(LinkedList list)
 +
{
 +
  swap(*this, list);
 +
  return *this;
 +
}
 +
</source>
 +
 +
== Iterators ==

รุ่นแก้ไขปัจจุบันเมื่อ 17:36, 1 ตุลาคม 2558

This is part of adt lab

List nodes

typedef

In C++, you can simply declare a new type based on known types using typedef.

typedef int valueType;
valueType x = 10;

We will declare new valueType so that our linked list code works fairly well with any types. We will eventually use template to make generic linked list.

struct

struct ListNode
{
  valueType val;
  ListNode* next;

  ListNode(valueType val, ListNode* next=0)
    : val(val), next(next) {}
};

Linked list class

typedef int valueType;

struct ListNode
{
  valueType val;
  ListNode* next;

  ListNode(valueType val, ListNode* next=0)
    : val(val), next(next) {}
};

class LinkedList
{
private:
  ListNode* header;
  void free_list();

public:
  LinkedList();
  ~LinkedList();
  void print_list();
  void insert_front(valueType x);
};

LinkedList::LinkedList()
{
  header = new ListNode(0);
}

LinkedList::~LinkedList()
{
  free_list();
}

void LinkedList::print_list()
{
  ListNode* node = header->next;
  while(node != 0) {
    cout << node->val << endl;
    node = node->next;
  }
}

void LinkedList::insert_front(valueType x)
{
}

void LinkedList::free_list()
{
}

Copy constructor and assignment operator

You can't pass an object of class LinkedList that we have written by value to other functions. For example, if you write

void test(LinkedList l)
{
  l.append(1000);
}

main()
{
  LinkedList l1;

  test(l1);
  
  l1.append(10);
}

When you run your program, you may get this run-time error:

*** Error in `./a.out': double free or corruption (fasttop): 0x0000000002138010 ***

This happens because the destructor has been called twice: once for l1 and another for its copy l in function test. However, its copy, by default, was created by copying every data members of l1, i.e., its header and tail pointers point to the same location as of l1. When the list l was destroyed, its destructor also destroyed the original list data.

To prevent this problem, you can pass l1 by reference as in the next code. In this case l and l1 is the same list.

void test(LinkedList& l)
{
  l.append(1000);
}

main()
{
  LinkedList l1;

  test(l1);
  
  l1.append(10);
}

But if you want l and l1 to be different lists, you need to implement its copy constructor yourself to handle object copy. (Read more at copy constructor's article at wikipedia)

Another case when default copying operation does not work is when you use assignments, as in:

  LinkedList l1, l2;

  l2 = l1;

In C++, Rule of three states that if you implement any of these methods, you should implement all three:

  • destructor
  • copy constructor
  • copy assignment operator

The following shows the code for copy constructor and copy assignment operator for our LinkedList class.

class LinkedList
{
// ...
  
public:
  LinkedList();
  LinkedList(const LinkedList& list);

  // ...
  LinkedList& operator=(const LinkedList& list);
};
LinkedList::LinkedList(const LinkedList& list)
{
  header = new ListNode(0);
  tail = header;
  ListNode* p = list.header->next;
  while(p != 0) {
    append(p->val);
    p = p->next;
  }
}

LinkedList& LinkedList::operator=(const LinkedList& list)
{
  if(this != &list) {
    free_list();
    header = new ListNode(0);
    tail = header;
    ListNode* p = list.header->next;
    while(p != 0) {
      append(p->val);
      p = p->next;
    }
  }
}

Copy-and-swap idiom

Read at stackoverflow.

Here is a new version of the assignment operator using the copy-and-swap idiom.

class LinkedList
{
// ...
public:
  // ...
  LinkedList& operator=(LinkedList list);

  void swap(LinkedList& l1, LinkedList& l2);
};
void LinkedList::swap(LinkedList& l1, LinkedList& l2)
{
  std::swap(l1.header, l2.header);
  std::swap(l1.tail, l2.tail);
}

LinkedList& LinkedList::operator=(LinkedList list)
{
  swap(*this, list);
  return *this;
}

Iterators