C ++ Можете ли вы спроектировать структуру данных, которая хранит указатели в непрерывной памяти и не делает их недействительными? - PullRequest
Новая
       4

C ++ Можете ли вы спроектировать структуру данных, которая хранит указатели в непрерывной памяти и не делает их недействительными?

1 голос
/ 31 января 2020

Я пытаюсь реализовать половинную структуру данных для меня sh представление. Мое текущее препятствие:

Для этого DS вам нужно несколько указателей, пример возможной реализации: 

class HalfEdge {
        Edge * next;
        Edge * prev;
        Edge * pair;
        Vertex * vertex;
        Face * face;
}

В этом нет ничего плохого. Однако, если вы используете указатели (скажем, мы используем интеллектуальные указатели вместо сырых, чтобы избежать известных проблем с указателями), ваши данные теперь редко хранятся в памяти, и вы теряете производительность из-за кэширования. Хуже того, если вы хотите отправить это я sh в графический процессор, теперь вы должны сериализовать вершины и представить, что вы должны делать это каждый кадр!

Таким образом, альтернатива - иметь массивы, а затем сделать это : 

// Somewhere else we have vectors of edges, faces and vertices
// we store their indices in the array rather than pointers.
class HalfEdge {
        uint next_index;
        uint prev_index;
        uint pair_index;
        uint vertex_index;
        uint face_index;
}

Это, в сочетании с массивами, позволит вам непреднамеренно хранить содержимое в памяти, и теперь вы можете отправить me sh в gpu без лишних затрат на создание линеаризованного буфера. Однако это имеет синтаксическую проблему.

Прежде чем вы смогли сделать face->field, теперь вы должны сделать face_array[face_index].field Это очень неуклюже.

Наивно можно подумать, что объединение вершин для выделения и указателей для доступа будет работать, что-то вроде Face* face = &face_array[index], однако любой, имеющий достаточный опыт работы с C ++, знает, что указатель станет недействительным, как только размер массива будет изменен.

Не зная потенциального размера me sh, массив не может быть предварительно выделен, поэтому это невозможно сделать.

Исходя из всего вышесказанного, можете ли вы добиться большего успеха, чем face_array[index].field, если вы хотите, чтобы память была условной?

1 Ответ

1 голос
/ 31 января 2020

Предполагая, что вы сохраняете своих участников в списке, вы можете сделать что-то вроде: 

class HalfEdge {
public:
  Edge& next() { return (*edge_list)[next_index]; }
  Edge& prev() { return (*edge_list)[prev_index]; }
  // ...
  // probably also const-qualified versions is a good idea

private:
  // or global if needed, or whatever
  std::vector<Edge>* edge_list;
  // ...

  std::size_t next_index;
  std::size_t prev_index;
  // ...
};

Это позволит вам получить доступ к значениям в вашей локальной области, например 

HalfEdge he = /* ... */;
auto& edge = he.next();  // which is otherwise equivalent to
auto& edge = edge_list[he.next_index];

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

...