Блог

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) {
    Nodeamp; n = nodes[i];
    nodes[n.next].prev = n.prev;
    nodes[n.prev].next = n.next;
  }
};
  

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

 struct Node { int prev, next; };
struct LinkedList;
struct NodeRef {
  int i;
  LinkedListamp; l;  // This reference here is what's worrying me
  NodeRef(int index, LinkedListamp; 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() {
  Nodeamp; n = l.nodes[i];
  l.nodes[n.next].prev = n.prev;
  l.nodes[n.prev].next = n.next;
}
  

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

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

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

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

 struct NodeRef
{
  int i;
  // LinkedListamp; l;  // Remove this
  NodeRef(int index) : i(index) {}
  NodeRef prev(LinkedListamp; l) const;
  NodeRef next(LinkedListamp; l) const;
  void remove(LinkedListamp; l);
};
// Require that a list is supplied instead of storing a ref
void NodeRef::remove(LinkedListamp; l)
{
  Nodeamp; 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 = [amp;linkedList](NodeRef node)
{
  node.remove(linkedList);
};
//...
NodeRef nodeRef(0);
remover(nodeRef);
  

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

Другим вариантом может быть использование шаблонов для хранения статического указателя на список, общего для всех производных классов. Использование разных значений 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()
{
  autoamp; l = *NodeRef<X>::l;
  Nodeamp; 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();
}
  

Вы могли бы заставить все LinkedList использовать один пул Node файлов:

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

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

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

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