Linked List & Iterators

[Forgetful]

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?

#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;
}

[keskiverto]

I'm having a tough time trying to create these functions

  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]

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]

I have something like this while working on RemoveIt(It pos);

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.

[JLBorges]

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:

#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

[Forgetful]

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]

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.

[Forgetful]

Oh thanks so much that makes it so clear now thank you

[Forgetful]

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?

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;
   }
  }

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;
}

[JLBorges]

> 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.