Требования к типам указателей распределителя стандартной библиотеки

Я пытаюсь написать класс разреженной матрицы quadtree. Короче говоря, quadtree_matrix<T> — это либо нулевая матрица, либо четверка (ne, nw, se, sw) из quadtree_matrix<T>.

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

Мне придется выделить два разных типа данных: либо T, либо node, которые содержат четыре указателя (либо на T, либо на node). Для всех алгоритмов, которые я буду рассматривать, я точно знаю, какие данные ожидать, потому что я знаю, каковы размеры подматриц, с которыми я сталкиваюсь в любой точке алгоритма (мне даже не нужно хранить эти размеры).

Я, конечно, буду использовать два разных распределителя: это нормально, поскольку типы распределителей предоставляют шаблон rebind и конструктор копии шаблона (и предназначены для использования в качестве типов значений, как предполагают члены get_allocator стандартных контейнеров, возвращая копию) .

Проблема в том, что функции-члены распределителя используют определенный тип pointer, который не обязательно должен быть ванильным указателем. Некоторые распределители (ускоренные межпроцессные распределители) широко используют эту функцию.

Если бы типы указателей распределителя были указателями садового типа, у меня не было бы проблем: по крайней мере, я мог бы использовать указатели для пустоты и переинтерпретировать_приводить их к нужному типу (либо node*, либо T*). Я мог бы также использовать союз (вероятно, лучше).

Насколько я знаю, нет требований к PODness для типов allocator::pointer. Они должны быть только итераторами с произвольным доступом.

Теперь мой вопрос:

Учитывая шаблон класса распределителя A<T> (или его эквивалент A::rebind<T>::other), есть ли какие-либо гарантии относительно:

  1. Возможность статического преобразования A<T>::pointer в A<U>::pointer при условии, что U является доступной базой T ?
  2. Возможность статического приведения A<T>::pointer к A<U>::pointer при условии, что T является доступной базой U, а "тип среды выполнения" (что бы это ни значило в данном контексте) каста равен U ?
  3. Тип A<void>::pointer (если это имеет смысл)?

Или есть решение моей проблемы, о котором я не подумал?


c++ language-lawyer standard-library allocator
person Alexandre C.    schedule 25.03.2011    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Из таблиц в 20.1.5/2 ясно видно, что тип A<T>::pointer должен быть "указателем на T". Поскольку эти типы указателей обычно конвертируются, ваши 1 и 2 верны. Отсюда следует, что A<void>::pointer должно быть void*.

РЕДАКТИРОВАТЬ: в 20.1.5/4 также есть явная формулировка (это относится к тому, что стандартные контейнеры могут предполагать в отношении распределителей):

Указатель членов typedef, const_pointer, size_type и разность_типов должны быть T*,T const*, size_t и ptrdiff_t соответственно.

person Mark B    schedule 25.03.2011
comment
Значит, нет места для причудливых распределителей памяти? Распределители разделяемой межпроцессной памяти Boost возвращают тип offset_ptr<T>, который является не T*, а случайным итератором. - person Alexandre C.; 25.03.2011
comment
@Alexandre: я считаю, что в документации по boost они на самом деле ссылаются на это как на одну из причин, по которой интерпроцесс boost не может предоставить стандартные распределители и почему им нужны пользовательские контейнеры. - person Joseph Garvin; 25.03.2011
comment
Хорошо, поэтому я предполагаю, что они настоящие указатели. Я беспокоился о сторонних классах распределителей, которые могут не использовать подлинные типы указателей как pointer. Поскольку стандартные классы контейнеров могут это предполагать, я так и сделаю. Спасибо за Ваш ответ ! - person Alexandre C.; 25.03.2011

arrow_upward
0
arrow_downward

Нет, не совсем.

Существует требование, чтобы A‹T›::pointer можно было преобразовать в A‹T›::const_pointer и A‹T›::void_pointer, но это все, что я могу найти.

A‹void›::pointer, скорее всего, будет void*, если только у вас нет специальной специальной памяти.

person Bo Persson    schedule 25.03.2011

arrow_upward
0
arrow_downward

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

Поэтому я бы рекомендовал двухэтапный подход:

  • Напишите небольшой интеллектуальный указатель, который использует данный распределитель для выполнения уничтожения (вместо delete)
  • Используйте boost::variant на ваших указателях

Таким образом, вы получаете как автоматическое управление памятью, так и компактность.

person Matthieu M.    schedule 25.03.2011
comment
Мне не нужна безопасность во время выполнения варианта boost (который добавляет флаг) или ссылка на распределитель рядом с каждым указателем. Это увеличивает нагрузку на каждый узел (это будет означать 6n накладных расходов вместо 4n с n = числом ненулевых записей). Я вполне могу (и на самом деле должен, если мне не нужно место над головой) приспособить уничтожение контейнера вручную. - person Alexandre C.; 25.03.2011
comment
Правда, я этого не уточнил. Я хотел бы сравнить схемы quadtree с традиционными алгоритмами разреженных матриц. Сам класс будет прост в использовании, но его реализация не может быть. - person Alexandre C.; 25.03.2011
comment
@Alexandre C: Я понимаю :) И это твои усилия :p - person Matthieu M.; 25.03.2011