Linked List & Iterators

Forgetful (37)
I'm trying to create a function that inserts a new value before the previous value's position and then return an iterator that points to the new value.

InsertIt(It pos, const T& ele);

also I'm trying to create another function that removes a value from a certain position and returns an iterator pointing to the value that followed the previous value.

RemoveIt(It pos);

I'm having a tough time trying to create these functions could anyone help me?

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
#include <initializer_list>
#include <iostream>

template <typename T>
class List {
  struct Node;  
  class It;
 public:
  List(std::initializer_list<T> ele) {
    this->operator=(ele);  
  }

  void Insert(T ele) {
    Node* node = new Node{ele};
    if (this->size == 0) {
      this->start = this->fin = node;
    } else {
      this->fin->next = node;
      node->prev = this->fin;
      this->fin = node;
    }
    ++this->size;
  }

  List& operator=(std::initializer_list<T> ele) {
    this->size = 0;
    for (auto&& val : ele) this->Insert(val);
    return *this;
  }

  friend std::ostream& operator<<(std::ostream& out, const List& list) {
    for (auto val = list.start; val; val = val->next) {
      out << val->data;
      if (val->next) out << ",";
    }
    return out;
  }

  template <class It>
  List(It begin, It end) {
    for (; begin != end; ++begin) this->Insert(*begin);
  }

  It begin() {
    return It(start);
  }

  It end() {
    return It(NULL);
  }

  It InsertIt(It pos, const T& ele);

  It RemoveIt(It pos);

private:
  struct Node {
    T data;
    Node* next = nullptr;
    Node* prev = nullptr;
  };

  class It {
    friend class List;
    public:
    It& operator=(const It& that) {
      List<char> first(that.begin(), that.end());
    }

    It& operator++() {
      this->cur = cur->next;
      return *this;
    }

    It operator++(int) {
      It temp(*this);
      this->operator++();
      return temp;
    }

    T const *operator->() const { return &(**this); }

    T *operator->() { return &(**this); }

    T& operator*() const {return this->cur->data;}
    
    bool operator!=(It val) const { 
       return !(this->operator==(val));
    }

    bool operator==(It val) const { 
       return this->cur == val.cur;
    }

     private:

     typename List<T>::Node* cur;
     It (List::Node *ptr) : cur(ptr) {}
  };

  Node* start = nullptr;
  Node* fin = nullptr;
  std::size_t size = 0;
};

int main() {
List<char> test = {'H', 'e', 'l', 'l', 'o'};
std::cout << test << std::endl;
List<char> test2 (test.begin(), test.end());
auto iter = test2.begin();
iter++;
iter++;
iter++;
test2.InsertIt(iter++, '!');
test2.RemoveIt(iter);
std::cout << test2 << std::endl;
}

Last edited on
keskiverto (10402)
I'm having a tough time trying to create these functions
1
2
 
  It InsertIt(It pos, const T& ele);
  It RemoveIt(It pos);

We can't see what how you have failed, because you show only the declarations, which seem ok.
Forgetful (37)
I only have declarations for them, I don't really know how to start or how to approach this I tried searching online but can't find much help or don't even know what im searching for.
Forgetful (37)
I have something like this while working on RemoveIt(It pos);

1
2
3
4
5
6
7
8
9
 
It RemoveIt(It pos) {
    for (auto i = begin(); i != end();) {
      if (i == pos) {
        delete i;
      } else {
        ++i;
      }
    }
  }


but doesn't seem to work any pointers or help creating a different function for
It RemoveIt(it pos);
error I get
testings.cpp:62:9: error: cannot delete expression of type 'List<char>::It'
delete i;
^ ~
testings.cpp:128:7: note: in instantiation of member function
'List<char>::RemoveIt' requested here
test2.RemoveIt(iter);
^
1 error generated.
Last edited on
JLBorges (13770)
When authoring any class (particularly a complex class):

a. Identify the class invariant.
b. Verify that the invariant holds after construction, before destruction, and both before and after public operations.
c. Develop the code incrementally, testing each operation and verifying that the invariant holds, before moving on to the next operation.

More information: https://www.artima.com/intv/goldilocks3.html

For example:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
#include <initializer_list>
#include <iterator>
#include <cassert>
#include <iostream>
#include <string>
#include <algorithm>

template < typename T > struct list {

    list() noexcept { assert_sanity() ; }
    list( std::initializer_list<T> ilist ) { for( const T& v : ilist ) push_back(v) ; assert_sanity() ; }

    ~list() { assert_sanity() ; while( !empty() ) pop_back() ; }

    // TO DO: other constructors, copy/move constructors, assignment operator
    // TO DO: assign, swap

    std::size_t size() const { assert_sanity() ; return sz ; }
    bool empty() const { return size() == 0 ; }

    void push_front( const T& v ) {

         assert_sanity() ;

         if( empty() ) first = last = new node{ v, nullptr, nullptr } ;
         else { first->prev = new node{ v, nullptr, first } ; first = first->prev ; }

         ++sz ;

         assert_sanity() ;
    }

    void push_back( const T& v ) {

         assert_sanity() ;

         if( empty() ) push_front(v) ;
         else { last->next = new node{ v, last, nullptr } ; last = last->next ; ++sz ; }

         assert_sanity() ;
    }

    void pop_front() { // invariant: !empty()

        assert_sanity() ;

        if( size() < 2U ) { delete first ; first = last = nullptr ; }
        else { first = first->next ; delete first->prev ; first->prev = nullptr ; }

        --sz ;

        assert_sanity() ;
    }

    void pop_back() { // invariant: !empty()

        assert_sanity() ;

        if( size() < 2U ) pop_front() ;
        else { last = last->prev ; delete last->next ; last->next = nullptr ; --sz ; }

        assert_sanity() ;
    }

    private: struct const_iterator ; struct iterator ; public:

    iterator insert( const_iterator where, const T& value ) {

        assert_sanity() ;

        if( where == begin() ) { push_front(value) ; return begin() ; }
        else if( where == end() ) { push_back(value) ; return { last } ; }
        else {

            node* p_new_node = new node { value, where.current->prev, where.current } ;

            where.current->prev->next = p_new_node ;
            where.current->prev = p_new_node ;
            ++sz ;

            assert_sanity() ;
            return { p_new_node } ;
        }
    }

    iterator erase( const_iterator where ) {

        assert_sanity() ;

        if( where == begin() ) { pop_front() ; return begin() ; }
        else if( where.current == last ) { pop_back() ; return end() ; }

        else {

            where.current->prev->next = where.current->next ;
            where.current->next->prev = where.current->prev ;

            iterator result { where.current->next } ;
            delete where.current ;
            --sz ;

            assert_sanity() ;
            return result ;
        }
    }

    // TO DO: other list operations

    const_iterator begin() const { return { first } ; }
    const_iterator end() const { return { nullptr } ; }
    const_iterator cbegin() const { return { first } ; }
    const_iterator cend() const { return { nullptr } ; }
    iterator begin() { return { first } ; }
    iterator end() { return { nullptr } ; }

    // ...

    private:

        struct node { T value ; node* prev ; node* next ; };

        // TO DO: make these iterators bidirectional and add rbegin, rend, crbegin, crend

        struct const_iterator {

            using iterator_category = std::forward_iterator_tag ;
            using value_type = const T ;
            using pointer = const T* ;
            using reference = const T& ;
            using difference_type = std::ptrdiff_t ;

            const T& operator* () { return current->value ; }
            const T* operator-> () { return &**this ; }

            const_iterator& operator++ () {  current = current->next ; return *this ; }
            const_iterator operator++ (int) { const auto temp = *this ; ++*this ; return temp ; }

            bool operator== ( const const_iterator& that ) const { return current == that.current ; }
            bool operator!= ( const const_iterator& that ) const { return !( *this == that ) ; }

            protected:
                node* current ;
                const_iterator( node* n ) : current(n) {}

            friend list ;
        };

        struct iterator : const_iterator {

            using value_type = T ;
            using pointer = T* ;
            using reference = T& ;

            using const_iterator::const_iterator ;

            T& operator* () { return const_iterator::current->value ; }
            T* operator-> () { return &**this ; }

            iterator& operator++ () {  const_iterator::operator++() ; return *this ; }
            iterator operator++ (int) { const auto temp = *this ; ++*this ; return temp ; }

            friend list ;
        };

        node* first = nullptr ;
        node* last = nullptr ;
        std::size_t sz = 0 ;

        bool is_sane() const { // true if the class invariant holds

            if( first == nullptr || last == nullptr || sz == 0 )
                return first == nullptr && last == nullptr && sz == 0 ;

            if( first->prev || last->next ) return false ;

            if( first == last ) return sz == 1 ;
            if( sz == 1 ) return first == last ;

            std::size_t computed_size = 0 ;
            for( node* p = first ; p ; p = p->next ) ++computed_size ;
            if( sz != computed_size ) return false ;

            computed_size = 0 ;
            for( node* p = last ; p ; p = p->prev ) ++computed_size ;
            return sz == computed_size ;
        }

        #ifdef NDEBUG
            void assert_sanity() const {}
        #else
            void assert_sanity() const { // assert that the list is in a valid state

                assert( is_sane() && "not sane: there is a programming error" ) ;
            }
        #endif // NDEBUG
};

// TO DO: overloaded comparison operators for list

int main() {

    list<std::string> lst { "abcd", "efgh", "ijkl - to be deleted", "mnop", "qrst", "uvwx", "yz12" } ;

    lst.insert( std::find( lst.begin(), lst.end(), "mnop" ), "this was inserted" ) ;
    
    const auto iter = std::find( lst.begin(), lst.end(), "ijkl - to be deleted" ) ; 
    if( iter != lst.end() ) lst.erase(iter) ;

    for( const auto& str : lst ) std::cout << str << '\n' ;
}

http://coliru.stacked-crooked.com/a/070b47ba3c0a58f5
Last edited on
Forgetful (37)
For line 75 
 
 
node* p_new_node = new node { value, where.current->prev, where.current }

could you explain what's going on there im not understanding what is happening
JLBorges (13770)

where.current is the pointer to node identified by the iterator. We want to insert a new node here.

This is the definition of node: struct node { T value ; node* prev ; node* next ; };

With node* p_new_node = new node { value, where.current->prev, where.current } ;,
we create a new node with:
value being the value kept in this new node
where.current->prev (the current node's prev) is the prev of this new node
and where.current (the current node) is the next of this new node.
Last edited on
Forgetful (37)
Oh thanks so much that makes it so clear now thank you
Forgetful (37)
when I try implementing this into my code the insert function it compiles fine but now I get a infinite loop somewhere did I do something wrong?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
It InsertIt(It pos, const T& ele) {
   if(pos == begin()) {
     InsertF(ele);
     return begin();
   } else if(pos == end()) {
     InsertB(ele);
     return fin;
   } else {
     Node* temp = new Node{ele, pos.cur->prev, pos.cur};

     pos.cur->prev->next = temp;
     pos.cur->prev = temp;

     ++size;
     return temp;
   }
  }

1
2
3
4
5
6
7
8
9
10
11
 
int main() {
List<char> test = {'H', 'e', 'l', 'l', 'o'};
std::cout << test << std::endl;
List<char> test2 (test.begin(), test.end());
auto iter = test2.begin();
iter++;
iter++;
test2.InsertIt(++iter, '!');
//test2.RemoveIt(iter);
std::cout << test2 << std::endl;
}
Last edited on
JLBorges (13770)
> I get a infinite loop somewhere did I do something wrong?

Hard to say, without seeing all the code.

The InsertIt function itself does not seem to have an infinite loop
(unless it calls InsertF or InsertB, which then loops for ever).

Verify that the class invariant holds on entry to the function,
and that it continues to hold when the function returns.
Topic archived. No new replies allowed.