ООП интерфейс при использовании индексов для ссылок - PullRequest
Новая
       30

ООП интерфейс при использовании индексов для ссылок

4 голосов
/ 28 марта 2019

TL; DR: у меня есть связанная структура данных, и я решил использовать не указатели, а индексы в контейнере для выражения этих ссылок. Могу ли я моделировать отдельные элементы как отдельные объекты для более удобочитаемого кода без затрат на хранение нескольких ссылок на массив?

Предположим, у меня есть связанная структура данных. Для простоты, давайте в качестве примера рассмотрим двусвязный список с операцией удаления узла. Классический способ моделирования это будет использовать указатели: 

struct Node {
  Node *prev, *next;
  void remove() { next->prev = prev; prev->next = next; }
};

Но у указателей есть ряд недостатков. Они могут тратить пространство, так как размер указателя обычно не может быть выбран в соответствии с вариантом использования. Они делают для плохого формата провода. Если я сохраню узлы в векторе, изменение размера может сделать недействительными указатели. Копирование структур данных становится сложнее. Так что вместо этого я мог бы перейти на индексы в некоторый массив: 

struct Node {
  int prev, next;
};
struct LinkedList {
  std::vector<Node> nodes;
  void remove(int i) {
    Node& n = nodes[i];
    nodes[n.next].prev = n.prev;
    nodes[n.prev].next = n.next;
  }
};

Но теперь операция, которая ранее была методом отдельного узла, стала методом класса контейнера. Этот семантический сдвиг затрудняет чтение кода. Чтобы избежать этой проблемы, я мог бы пойти на представление, основанное на паре контейнера и индекса узла. 

struct Node { int prev, next; };
struct LinkedList;
struct NodeRef {
  int i;
  LinkedList& l;  // This reference here is what's worrying me
  NodeRef(int index, LinkedList& list) : i(index), l(list) {}
  NodeRef prev() const;
  NodeRef next() const;
  void remove();
};
struct LinkedList {
  std::vector<Node> nodes;
  NodeRef root() { return NodeRef(0, *this); }
};
NodeRef NodeRef::prev() const { return NodeRef(l.nodes[i].prev, l); }
NodeRef NodeRef::next() const { return NodeRef(l.nodes[i].next, l); }
void NodeRef::remove() {
  Node& n = l.nodes[i];
  l.nodes[n.next].prev = n.prev;
  l.nodes[n.prev].next = n.next;
}

Так что теперь я могу использовать NodeRef для выражения моего алгоритма в приятной объектно-ориентированной манере, с узлом в качестве сущности, с которой я могу работать, и в то же время используя индексы вместо указателей за кулисами.

Но когда у меня есть какой-то сложный алгоритм, работающий с несколькими узлами одновременно, тогда у меня будет несколько объектов NodeRef, ссылающихся на один и тот же базовый объект LinkedList. Это кажется расточительным, как с точки зрения потребления памяти, так и работы по их копированию. Я бы предположил , что компилятор может сможет обнаружить некоторую избыточность и избавиться от нее. Но могу ли я что-нибудь сделать, чтобы помочь этому оптимизировать использование только одной ссылки, хотя семантически у меня есть несколько?

Ответы [ 3 ]

1 голос
/ 28 марта 2019

Вы можете потребовать, чтобы LinkedList было предоставлено, когда вы хотите воздействовать на NodeRef, а затем иметь доступ к объекту или лямбде, который хранит вашу единственную ссылку и упаковывает вызовы в NodeRef.

Например, чтобы удалить узлы из списка, вы можете использовать: 

struct NodeRef
{
  int i;
  // LinkedList& l;  // Remove this
  NodeRef(int index) : i(index) {}
  NodeRef prev(LinkedList& l) const;
  NodeRef next(LinkedList& l) const;
  void remove(LinkedList& l);
};
// Require that a list is supplied instead of storing a ref
void NodeRef::remove(LinkedList& l)
{
  Node& n = l.nodes[i];
  l.nodes[n.next].prev = n.prev;
  l.nodes[n.prev].next = n.next;
}

// create a lambda with a captured list that wraps the call
LinkedList linkedList;
//...
auto remover = [&linkedList](NodeRef node)
{
  node.remove(linkedList);
};
//...
NodeRef nodeRef(0);
remover(nodeRef);

Не уверен, что это именно то, что вам нужно, но он избегает множественных ссылок на список и может позволить повторное использование NodeRef объектов.

0 голосов
/ 29 марта 2019

Вы можете сделать все LinkedList s общим пулом Node s: 

struct LinkedList {
  static std::vector<Node> nodes; // <-- static
  void remove(int i) {
    Node& n = nodes[i];
    nodes[n.next].prev = n.prev;
    nodes[n.prev].next = n.next;
  }
};

Таким образом, для NodeRef одного индекса вполне достаточно для идентификации ссылочной Node.

Обратите внимание, что в зависимости от того, как часто LinkedList s и Node s создаются, изменяются и уничтожаются, вы можете столкнуться с проблемами производительности из-за пропусков кэша, поскольку Node s, которые являются соседями в списке, могут не быть соседями вообще в памяти. Эта проблема может существовать с вашим текущим подходом уже. В этом случае глобальный пул Node сделает его еще хуже.

Кроме того, если у вас многопоточное приложение, вам придется использовать обычные механизмы блокировки, которые еще больше замедлят ваше приложение.

0 голосов
/ 28 марта 2019

Другим вариантом может быть использование шаблонов для хранения статического указателя на список, общий для всех производных классов. Использование разных int для дифференциации ваших списков и NodeRef. Вы вынуждены снова управлять этими типами во время компиляции, возможно, не идеально, но это решает проблему с несколькими ссылками. 

#include <vector>

template <int X>
struct LinkedList;

template <int X>
struct NodeRef
{
  static LinkedList<X>* l;
  int i;
  NodeRef(int index) : i(index) {}
  NodeRef prev() const;
  NodeRef next() const;
  void remove();
};

struct Node { int prev, next; };

template <int X>
struct LinkedList 
{
  LinkedList() 
  {
      NodeRef<X>::l = this;
  }
  std::vector<Node> nodes;
  NodeRef<X> root() { return NodeRef<X>(0); }
};


// Use the static pointer
template<int X>
void NodeRef<X>::remove()
{
  auto& l = *NodeRef<X>::l;
  Node& n = l.nodes[i];
  l.nodes[n.next].prev = n.prev;
  l.nodes[n.prev].next = n.next;
}



int main()
{
    LinkedList<0> linkedList;

    // All node refs templated by 0 share the list pointer
    auto nodeRef = linkedList.root();
}
...