C++

Forum

 
implementing a portion of template class list

aura (1)
Using friend of class to access private data member for insert(), here's what I have:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template<class T>
typename list<T>::iterator list<T>::insert(iterator it,const T& d){
     node* it2;
     /*if (!it){ //??
          it2->pred = NULL;
          it2->succ = NULL;
          return it2;
     }*/
     it2->pred = it->pred;
     it2->succ = it->succ;
     if (it->pred) { it->prev->succ = it2; }
     it->pred = it2->succ;
     return it2;
};


Here's my broken erase:

1
2
3
4
5
6
7
8
 
template<class T>
typename list<T>::iterator list<T>::erase(iterator it){
     node* tmp;
     tmp = it->pred;
     it->pred = tmp->pred;
     it(tmp->pred){ tmp->pred->succ = it; }
     return it->pred;
};


I am also not entirely sure what to do with my node code:

1
2
3
4
5
6
7
8
9
 
template<class T>
struct list<T>::node
{
     T datum;
     node *pred,*succ;
     node(const T& d,node* p,node* s)
     : datum(d), pred(p), succ(s)
     {}
};


Thanks for reading, and any reply is appreciated.

EDIT: Changes made to code. Here's the full code in case the pieces up there are too confusing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include <iterator>
using namespace std;

template<class T>
class list {
public:
// types
     class iterator;
     typedef std::reverse_iterator<iterator> reverse_iterator; // std:: is redundant
     typedef T* pointer;
     typedef const T* const_pointer;
     typedef T& reference;
     typedef const T& const_reference;
     typedef const iterator const_iterator;
     typedef const reverse_iterator const_reverse_iterator;
// ctor/dtor
     list();
     template<class InputIterator> list(InputIterator,InputIterator);
     ~list();
// modifiers
     iterator insert(iterator,const T& =T());
     iterator erase(iterator);
     void push_front(const T& d) { insert(begin(),d); }
     void push_back(const T& d) { insert(end(),d); }
     void pop_front() { erase(begin()); }
     void pop_back() { erase(--end()); }
// list operations
     void unique();
// capacity
     bool empty() const { return begin()==end(); }
// element access
     reference front() { return *begin(); }
     const_reference front() const { return *begin(); }
     reference back() { return *--end(); }
     const_reference back() const { return *--end(); }
// iterator                         
     iterator begin() { return head->succ; }
     const_iterator begin() const { return head->succ; }
     iterator end() { return head; }
     const_iterator end() const { return head; }
     reverse_iterator rbegin() { return reverse_iterator(end()); }   // explicit ctor
     const_reverse_iterator rbegin() const { return reverse_iterator(end()); }
     reverse_iterator rend() { return reverse_iterator(begin()); }
     const_reverse_iterator rend() const { return reverse_iterator(begin()); }
private:
     struct node;
     node* head;
};

template<class T>
struct list<T>::node
{
     T datum;
     node *pred,*succ;
     node(const T& d,node* p,node* s)
     : datum(d), pred(p), succ(s)
     {}
};

template<class T>
typename list<T>::iterator list<T>::insert(iterator it,const T& d){
     node* it2;
     /*if (!it){ //??
          it2->pred = NULL;
          it2->succ = NULL;
          return it2;
     }*/
     it2->pred = it->pred;
     it2->succ = it->succ;
     if (it->pred) { it->prev->succ = it2; }
     it->pred = it2->succ;
     return it2;
};

template<class T>
typename list<T>::iterator list<T>::erase(iterator it){
     node* tmp;
     tmp = it->pred;
     it->pred = tmp->pred;
     it(tmp->pred){ tmp->pred->succ = it; }
     free(tmp);
     return it->pred;
};

template<class T>
class list<T>::iterator
: public std::iterator<bidirectional_iterator_tag,T> {   // std:: is necessary
public:
     iterator(node* =0);
     reference operator*() const;
     pointer operator->() const;
     iterator& operator++();
     const_iterator operator++(int);
     iterator& operator--();
     const_iterator operator--(int);
     bool operator==(const_iterator&) const;
     bool operator!=(const_iterator&) const;
private:
     node* current;
};
Last edited on
jsmith (5804)
Not sure what your question is, but I can see that both erase and insert are broken:
insert because you never actually allocate a new node for the element, and erase
because you aren't checking boundary conditions (erasing the front element will
crash since you don't check if there is a previous element before accessing it).

Topic archived. No new replies allowed.