|
10-19-2007, 12:16 PM
| #1 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| Pleas take a look & give a critique Code: #ifndef LIST_H
#define LIST_H
/* -- BEGIN CLASS LIST --
*/
template <typename T>
class List{
/* -- BEGIN PRIVATE DEFINITIONS --
*/
private:
/* -- BEGIN CLASS NODE --
*/
struct Node{
T data;
Node *next, *prev;
Node(const T& d) : data(d), next(0), prev(0) {};
Node(const Node& src) : data(src.data), next(src.next), prev(src.prev) {};
Node& operator=(const Node& src){
if(this != &src){
Node *n, *p;
try{
n = new Node(*src.next); // Test for self-assignment
p = new Node(*src.prev);
}
catch(...){
delete n, p; // If self-assignment occurred, throw an exception
throw;
}
delete next, prev;
n = src.next;
p = src.prev;
}
return *this;
};
}; /* -- END CLASS NODE --
*/
/* List Private Fields:
*/
Node *head, *tail; // Pointers to first and last Nodes in List
unsigned int size; // Number of elements in List
bool empty; // TRUE if NO elements in List, FALSE if ( >= 1 ) elements in List
/* -- BEGIN PUBLIC DECLARATIONS --
*/
public:
/* -- BEGIN CLASS ITERATOR --
*/
class Iterator{
private:
Node *curr;
public:
/* Iterator Constructor:
*/
Iterator(Node* n = 0) : curr(n) {};
/* Overloaded Operators:
NOTE: Postfix & Prefix operators preform the same
function.
*/
Iterator& operator++() { curr = curr->next; return *this; };
Iterator& operator++(int) { curr = curr->next; return *this; };
Iterator& operator--() { curr = curr->prev; return *this; };
Iterator& operator--(int) { curr = curr->prev; return *this; };
bool operator!=(const Iterator& i) { return i.curr != curr; };
bool operator==(const Iterator& i) { return i.curr == curr; };
const T& operator*() const { return curr->data; };
Node* get_curr() const { return curr; }
}; /* -- END CLASS ITERATOR --
*/
/* -- PUBLIC INTERFACE --
*/
/* List Constructors:
*/
List<T>(); // Creates an instance of List
List<T>(const List& src); // Copies an existing List
List<T>& operator=(const List& src); // Copies an existing List through assignment
~List<T>(); // Deletes all instances of Node & List
/* List Functions:
*/
bool is_empty(){ return empty; } // Returns 1 if the List is Empty
unsigned int size_of(){ return size; } // Returns an integer (size of List)
void push_front(const T&); // Appends to beginning of List
void pop_front(); // Deletes Node in head position
void push_back(const T&); // Appends to end of List
void pop_back(); // Deletes Node in tail position
void insert(const T&); // Assumes List is sorted, inserts with <
void remove(const T&); // Removes all elements w/matching value
void sort(); // Sorts List with <
void swap(Node*); // Swaps next and prev pointers for specified Node
void reverse(); // Reverses order of List
void unique(); // Removes duplicate values
void clear(); // Deletes all elements in List
void display(); // Displays values to std::cout
/* Iteration-based Functions:
*/
Iterator begin() const { return Iterator(head); }; // Beginning of List (head)
Iterator end() const { return Iterator(0); }; // End of List (tail->next = 0)
Iterator rbegin() const { return Iterator(tail); }; // Beginning of List (tail)
Iterator rend() const { return Iterator(0); }; // End of List (head->prev = 0)
Iterator at(Node* x) const { return Iterator(x); }; // Returns an Iterator at specified Node
Iterator at(Iterator i) const { return Iterator(i.get_curr()); };
Iterator at(int n) const {
Iterator iter = begin();
for(int i = 0; i < n; i++){
iter++;
}
return iter;
}
Iterator insert(Iterator, const T&); // Insert at specified position, return position
Iterator remove(Iterator); // Removes element at specified position, return position
}; /* -- END CLASS LIST --
*/
/* LIST CONSTRUCTOR:
*/
template <typename T>
List<T>::List() : head(0), tail(0), size(0), empty(1) {}
/* LIST COPY-CONSTRUCTOR:
*/
template <typename T>
List<T>::List(const List& src) : head(0), tail(0), size(0), empty(1){
clear();
for(Iterator i = at(src.head); i != end(); i++){
push_back(*i);
}
/* Implementation w/out Iterators
clear();
for(Node* curr = src.head; curr != (src.tail)->next; curr = curr->next){
push_back(curr->data);
}
*/
}
/* LIST ASSIGNMENT OPERATOR:
*/
template <typename T> List<T>&
List<T>::operator=(const List& src){
if(this != &src){
Node *h, *t;
try{
h = new Node(*src.head); // Test for self-assignment
t = new Node(*src.tail);
}
catch(...){
delete h, t; // If self-assignment occurred, throw an exception
throw;
}
delete head, tail;
h = src.head;
t = src.tail;
}
return *this;
}
/* LIST DESTRUCTOR:
*/
template <typename T>
List<T>::~List(){
clear();
delete head;
delete tail;
}
/* FUNCTION: push_front(const T&)
PURPOSE: Creates an instance of Node in the
head position.
*/
template <typename T> void
List<T>::push_front(const T& x){
if(!empty){
head->prev = new Node(x);
(head->prev)->next = head;
head = head->prev;
head->prev = 0;
}
else{
head = tail = new Node(x);
empty = !empty;
}
size++;
}
/* FUNCTION: pop_front()
PURPOSE: deletes the Node in the head position
*/
template <typename T> void
List<T>::pop_front(){
if(!empty){
if(head != tail){
Node *curr(head);
(head->next)->prev = 0;
head = head->next;
delete curr;
}
else{
Node* curr = head;
head = tail = 0;
delete curr;
empty = !empty;
}
size--;
}
}
/* FUNCTION: push_back(const T&)
PURPOSE: Creates an instance of Node in the
tail position
*/
template <typename T> void
List<T>::push_back(const T& x){
if(!empty){
tail->next = new Node(x);
(tail->next)->prev = tail;
tail = tail->next;
tail->next = 0;
}
else{
head = tail = new Node(x);
empty = !empty;
}
size++;
}
/* FUNCTION: pop_back()
PURPOSE: deletes the Node in the tail position
*/
template <typename T> void
List<T>::pop_back(){
if(!empty){
if(head != tail){
Node* curr(tail);
(tail->prev)->next = 0;
tail = tail->prev;
delete curr;
}
else{
Node* curr = head;
head = tail = 0;
delete curr;
empty = !empty;
}
size--;
}
}
/* FUNCTION: insert(const T&)
PURPOSE: Assumes List is sorted, Inserts with <
*/
template <typename T> void
List<T>::insert(const T& x){
if(!empty){
Iterator i = begin();
while(i != end() && *i <= x){
i++;
}
if(i == begin()){ push_front(x); }
else if(i == end()){ push_back(x); }
else{
Node* curr = i.get_curr();
Node* temp = new Node(x);
(curr->prev)->next = temp;
temp->prev = curr->prev;
temp->next = curr;
curr->prev = temp;
size++;
}
}
else{
head = tail = new Node(x);
empty = !empty;
size++;
}
}
/* FUNCTION: remove(const T&)
PURPOSE: Removes all elements w/matching value (x)
*/
template <typename T> void
List<T>::remove(const T& x){
if(!empty){
Iterator i = begin();
while(i != end()){
if(*i == x){
if(i == begin()){
pop_front();
i = begin();
}
else if(i == rbegin()){
pop_back();
i = begin();
}
else{
Node* curr = i.get_curr();
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
curr = head;
size--;
}
}/* -- END IF(*i == x) --
*/
else{
i++;
}
}/* -- END WHILE --
*/
}
}
/* FUNCTION: sort()
PURPOSE: Sorts List with <
*/
template <typename T> void
List<T>::sort(){
}
/* FUCNTION: swap(Node*)
PURPOSE: Swaps next and prev pointers for specified Node
*/
template <typename T> void
List<T>::swap(Node* x){
Node* temp = x->next;
x->next = x->prev;
x->prev = temp;
}
/* FUNCTION: reverse()
PURPOSE: Reverses the order of the List
*/
template <typename T> void
List<T>::reverse(){
if(!empty){
for(Iterator i = begin(); i != end(); i--){
swap(i.get_curr());
}
Node* temp = head;
head = tail;
tail = temp;
}
}
/* FUNCTION: unique()
PURPOSE: Removes duplicate values
*/
template <typename T> void
List<T>::unique(){
}
/* FUNCTION: clear()
PURPOSE: deletes all elements in List
*/
template <typename T> void
List<T>::clear(){
if(!empty){
while(!empty){
if(!empty){ pop_front(); }
if(!empty){ pop_back(); }
}
}
}
/* FUNCTION: display()
PURPOSE: displays values to std::cout
*/
template <typename T> inline void
List<T>::display(){
if(!empty){
for(Iterator i = begin(); i != end(); i++){
std::cout << *i << std::endl;
}
}
}
#endif
|
| sh3rpa is offline |  |
|
10-19-2007, 01:19 PM
| #2 | |
| The larch Join Date: May 2006
Posts: 3,222
| While it is hard to comment on all of it, there are some very strange things going on. For example Node assignment: Code: Node& operator=(const Node& src){
if(this != &src){
Node *n, *p;
try{
n = new Node(*src.next); // Test for self-assignment
p = new Node(*src.prev);
}
catch(...){
delete n, p; // If self-assignment occurred, throw an exception
throw;
}
delete next, prev;
n = src.next;
p = src.prev;
}
return *this;
};
But a Node is such a simple thing that it shouldn't need any special copy construction and assignment. Just make sure that a Node cannot possibly be available to the user (why does get_curr return a Node*). The list's assignment has similar flaws and absolutely doesn't do what it is supposed to do. Why not simply base it on the copy-constructor + swap idiom (which was discussed recently)? Another good constructor to have is one that takes two iterators (a range). Other nitpicks are some naming conventions, e.g I'd expect a method named size() not size_of() and the signature of swap(Node*) is rather unexpected, even for internal use only. There are also some meaningless tests, e.g Code: if(!empty){
while(!empty){
Similarly: Code: if(!empty){
for(Iterator i = begin(); i != end(); i++){
And in the end, the List doesn't need a special member for empty, because in an empty list head and tail should be 0, so these could be used for these tests. --- Concerning Iterators: the *overload should return a non-const reference, so you could also modify items in the list. (It's the const_iterator that returns a const reference.) -------------- To test your list, you might use a class like this: Code: struct Tester
{
static int constructor;
static int copy_constructor;
static int destructor;
Tester() {++constructor;}
Tester(const Tester&) {++copy_constructor;}
~Tester() {++destructor;}
static void print()
{
std::cout << "Constructor: " << constructor <<
"\nCopy constructor: " << copy_constructor <<
"\nDestructor: " << destructor << '\n';
}
};
__________________ I might be wrong. Quote:
| |
| anon is offline | |
|
10-19-2007, 02:11 PM
| #3 |
| Algorithm Dissector  Join Date: Dec 2005 Location: New Zealand
Posts: 2,733
| This is an absolute WTF: Code: template <typename T> void
List<T>::swap(Node* x){
Node* temp = x->next;
x->next = x->prev;
x->prev = temp;
}
Stop reinventing the standard C++ library!
__________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger |
| iMalc is offline | |
|
10-19-2007, 02:28 PM
| #4 | |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| Quote:
| |
| sh3rpa is offline | |
|
10-19-2007, 02:30 PM
| #5 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| but I would like to know what is bazaar about it. That might be more helpful... |
| sh3rpa is offline | |
|
10-19-2007, 02:34 PM
| #6 |
| Registered User Join Date: Jan 2005
Posts: 7,252
| swap usually swaps two nodes. Your swap doesn't swap two nodes, it just makes the next and prev pointers point backwards, ruining the list: Code: 1-->2-->3-->4-->NULL (next pointers) NULL<--1<--2<--3<--4 (prev pointers) swap(3); 1-->2-->3-->2 4-->NULL (next pointers) NULL<--1<--2 4<--3<--4 (prev pointers) |
| Daved is offline | |
|
10-19-2007, 03:02 PM
| #7 | |
| The larch Join Date: May 2006
Posts: 3,222
| Well, the issue is that the function is named unconventionally. It is used for reversing the list, and in this usage it does the right thing. (It should not be a public method though.) However, it would be much less confusing to use: swap(prev, next);
__________________ I might be wrong. Quote:
| |
| anon is offline | |
|
10-19-2007, 04:11 PM
| #8 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| my value look-up: Code: const T& operator*() const { return curr->data; };
|
| sh3rpa is offline | |
|
10-19-2007, 04:18 PM
| #9 |
| Registered User Join Date: Jan 2005
Posts: 7,252
| Both. |
| Daved is offline | |
|
10-19-2007, 04:23 PM
| #10 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| also, for reverse(), would it be more efficient to just exchange values? |
| sh3rpa is offline | |
|
10-19-2007, 04:31 PM
| #11 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| And how would you modify the value? Code: Iterator i(list.begin()); *i = 10; ?????????? |
| sh3rpa is offline | |
|
10-19-2007, 04:35 PM
| #12 |
| Registered User Join Date: Jan 2005
Posts: 7,252
| You should have both versions of operator*, the const version and the non-const version. If you do, then *i = 10 will work in changing the data (it will call the non-const version, which returns a reference and so the value stored in the list will be updated through the reference). >> for reverse(), would it be more efficient to just exchange values? No. You should move pointers around. The function name swap threw me off, it is normally used for something else. |
| Daved is offline | |
|
10-19-2007, 06:17 PM
| #13 |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| This is the test I have for the operator*: List.h Code: #ifndef LIST_H
#define LIST_H
template <typename T> class List{
private:
struct Node{
T data;
Node *next, *prev;
Node(const T& d, Node* n = 0, Node* p = 0) : data(d), next(n), prev(p) {};
};
unsigned int size;
Node *head, *tail;
public:
class Iterator{
private:
Node* curr;
public:
Iterator(Node* c = 0) : curr(c) {};
T& operator*() { curr->data; };
const T& operator*() const { return curr->data; };
};
List<T>();
Iterator begin() const { return Iterator(head); };
};/* -- END CLASS LIST
*/
/* CONSTRUCTOR
*/
template <typename T>
List<T>::List() : head(0), tail(0), size(0) {}
#endif
Code: #include <iostream>
#include "List.h"
int main(){
List<int> list;
List<int>::Iterator i = list.begin();
*i = 10;
std::cout << *i << "\n";
return 0;
}
|
| sh3rpa is offline | |
|
10-19-2007, 06:30 PM
| #14 |
| Registered User Join Date: Jan 2005
Posts: 7,252
| Don't you have to add something to the list before you modify it? If that was an STL list you'd probably make your program crash because the list is empty but you're using an iterator to a non-existent first object. |
| Daved is offline | |
|
10-19-2007, 10:01 PM
| #15 | |
| Registered Abuser Join Date: Sep 2007 Location: USA/NJ/TRENTON
Posts: 127
| Quote:
Now I'm wondering about at() Should the handle of at() look like: Code: Iterator at(int); Code: list.at(n) = aNumber; | |
| sh3rpa is offline | |
 |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Give me some opinions on setting up a server | Shadow | A Brief History of Cprogramming.com | 12 | 04-19-2004 10:38 AM |
| Can you give me your tip plz :) | dionys | C Programming | 6 | 04-11-2004 11:14 PM |
| can anyone help me give a code about a program that will input positive numbers... | vigen00 | C Programming | 1 | 10-01-2001 10:39 AM |
| How To Give A Font Colour ? | Unregistered | Windows Programming | 1 | 09-14-2001 01:22 PM |
| Just to give you an idea of what we're going through... | rick barclay | A Brief History of Cprogramming.com | 8 | 09-13-2001 02:09 PM |
Linear Mode
