Geek asks and answers

A linked list in C ++ using references instead of pointers

Suppose I want to create an unmodifiable linked list (i.e., it can only be traversed, no nodes can be added or deleted after it is created). This can be easily implemented:

struct ListNode
{
  int value;
  ListNode* nextNode;
}

My question is: is it possible to use links instead of pointers?

struct ListNodeWithRefs
{
  int value;
  ListNodeWithRefs &nextNode;
}

I'm not sure if this will provide any performance, but ... this question arose during coding, and my answer so far is no, but I could have missed something.

Basically, nothing prevents you from using links and building lists like this:

ListNodeWithRefs::ListNodeWithRefs(ListNodeWithRefs &next):
  nextNode(next)
{}

But there is a problem with the chicken and the egg, because it nextalso forces its element to nextexist when it is created, and so on ...

: , :

struct ListNodeConst
{
  int value;
  const ListNode* nextNode;
}
+5
7

sbi, : fooobar.com/questions/268252/...

// Beware, un-compiled code ahead!
template< typename T >
struct node;

template< typename T >
struct links {
  node<T>& prev;
  node<T>& next;
  link(node<T>* prv, node<T>* nxt); // omitted
};

template< typename T >
struct node {
  T data;
  links<T> linked_nodes;
  node(const T& d, node* prv, node* nxt); // omitted
};

// technically, this causes UB...
template< typename T >
void my_list<T>::link_nodes(node<T>* prev, node<T>* next)
{
  node<T>* prev_prev = prev.linked_nodes.prev;
  node<T>* next_next = next.linked_nodes.next;
  prev.linked_nodes.~links<T>();
  new (prev.linked_nodes) links<T>(prev_prev, next);
  next.linked_nodes.~links<T>();
  new (next.linked_nodes) links<T>(next, next_next);
}

template< typename T >
void my_list<T>::insert(node<T>* at, const T& data)
{
  node<T>* prev = at;
  node<T>* next = at.linked_nodes.next;
  node<T>* new_node = new node<T>(data, prev, next);

  link_nodes(prev, new_node);
  link_nodes(new_node, next);
}
+3

cons- :

data List a = Empty | Node a (List a)

List a Empty node ( ).

++, ( ), .

template <typename T>
struct ListBase {
    enum class Kind { Empty, Node };
    explicit ListBase(Kind k): _kind(k) {}

    Kind _kind;
};

:

template <typename T>
struct EmptyList: ListBase<T> {
    EmptyList(): ListBase<T>(Kind::Empty) {}
};

template <typename T>
struct ListNode: ListBase<T> {
    ListNode(T const& t, ListBase<T>& next):
        ListBase<T>(Kind::Node), _value(t), _next(next) {}

    T _value;
    ListBase<T>& _next;
};

; EmptyList<T>.

: _kind - OO, , .

+3

. :

  • node, nextNode .
  • Node , ?
+2

?

: . . , .

, node , , .

.

. , .

+2

@Vlad, , . , , . , "" , NULL, , , , , , .

. , , , - ( ).

template<class T>
struct node{
    T value; // mutable?
    node const& next;
    struct circulator{
        node const* impl_;
        circulator& circulate(){impl_ = &(impl_->next); return *this;}
        T const& operator*() const{return impl_->value;}
        friend bool operator==(circulator const& c1, circulator const& c2){return c1.impl_ == c2.impl_;}
        friend bool operator!=(circulator const& c1, circulator const& c2){return not(c1==c2);}
    };
    circulator some() const{return circulator{this};}
};

, (, ), const ! value , mutable (, ?). ( , ).

node/list, ( ). , , "rho".

    node<int> n1{5, {6, {7, n1}}};
    auto c = n1.some();
    cout << "size " << sizeof(node<int>) << '\n';
    do{
        cout << *c << ", ";
        c.circulate();
    }while(c != n1.some()); //prints 5, 6, 7

, (?). ( - , , gcc clang). "" . , , :

circular_list<int> l{1,2,3,4}; // couldn't do this for obscure reasons

, , , , , "" ? ? ?

, , -, .

!

0

I may be out of order but it works

    struct Node;
struct Node {

    using link = std::reference_wrapper<Node>;

    Node( char data_  =  0) 
        : next({*this})
        , data( data_ == 0 ? '?' : data_ ) 
    {}

    bool is_selfref() const noexcept {
        return (this == & next.get());
    }

    char data;
    link next;
};

Routine tests

 Node A('A');     
 Node B('B');     
 Node C('C');     
 assert( A.is_selfref() == B.is_selfref() == C.is_selfref());

 A.next = B;  B.next = C;

 assert(! A.is_selfref() && ! B.is_selfref() );
 assert(  C.is_selfref() );

 assert( 'A' == A.data );
 assert( 'B' == A.next.get().data );
 assert( 'C' == A.next.get().next.get().data );

 // C.next == C

 // for those who feel safe seeing the END
 Node END(127);
 C.next = END;

Of course, as long as all the Nodes remain in the area, everything is in order with us. Otherwise, no. Strange and wonderful. Very limited utility?

0
source

It was pretty complicated, but it worked:

#include <iostream>
#include <typeinfo>

class Last {
  public:

    int x;
    int last;

    Last(int i) {
      std::cout << "parent constructor(" << i << ")\n";
      x = i;
      last = 1;
    }
};

struct fourptr {
    int v1, v2;
    void *p1, *p2;
    };

class chain : public Last {
  public:

    chain(int i) : Last(i) {
    std::cout << "child constructor(" << i << ")\n";
    last = 0;
    }

    void viewandnext() {
      struct fourptr *fp = (struct fourptr *) this;
      std::cout << x << ", this = " << this
                << ", sizeof *this = "<< sizeof * this
                << ", * this = {" << fp->v1 << ", " << fp->v2 << ", "
                << fp->p1 << ", " << fp->p2 << "}"
                << "\n";
      if (last == 0) ((chain &)next).viewandnext();
    }

  Last & fn(int x) {
    Last * e = (x>0) ? new chain(x-1) : new Last(x-1);
    return *e;
  }

    Last & next = fn(x); // This is not a pointer but a reference
};



int main(void) {
  chain &l = *(new chain(8));
  std::cout << "sizeof l = "<< sizeof l << "\n";
  l.viewandnext();
}
0
source

More articles:


All Articles