C++ Set или List

#stl #cpp

Здравствуйте, для представления смежности графа лучше использовать массив сетов или
листов?
Чем вообще отличается изнутри сет от листа.Спасибо    

Ответы

Ответ 1

Как бы смешно это не звучало, но практика показывает, что для представления графа
в виде adjacency lists лучше всего подходит std::vector, а не std::list.
В использовании std::set обычно нет необходимости.
Вот выдержка из англоязычного StackOverflow:


  ... в 90% случаев std::vector будет наилучшим выбором. Да, связный список выглядит
привлекательнее в подавляющем большинстве случаев, поскольку порядок элементов для
него (как правило) несущественен. Иными словами, добавляемые элементы помещаются в
конец буфера-контейнера [вне зависимости от места их вставки — прим. пер.], а удаляемый
элемент предварительно обменивается местами с конечным, так что вставка и удаление
затрагивают только элемент в конце этого буфера.
  
  Вектор, в свою очередь, копирует свои элементы при каждом расширении своего буфера,
однако на практике это несущественно. Экспонециальный рост гарантирует, что среднее
количество копирований стремится к некоторой константе, как правило трём или около того.
  
  Даже если копирование действительно является для вас проблемой (к примеру, элементы
имеют большой размер), я всё равно не перешёл бы на связный список. Вместо этого я
использовал бы std::deque. Это, по сути, вектор указателей на блоки с элементами. Он
редко копирует что-либо при расширении, а если и копирует, то только эти указатели,
но не сами элементы. Однако вектор является всё же более предпочтительным выбором,
пока вам не требуются возможности, присущие именно деку (вставка в любой из концов
и удаление из них); но даже дек предпочтительнее, чем список. Иными словами, сначала
std::vector, потом std::deque и только в самом конце std::list.


Ответ 2

Относительно устройства этих контейнеров. List реализуется как двусвязный список.
Set представляет собой автоматически  отсортировнный массив элементов. Обычно он реализуется
в виде бинарных деревьев, что обеспечивает быстрый поиск нужного элемента. Кроме того,
set не допускает дублирования элементов (в отличие от multiset). Более подробно - Джосаттис
"С++. Стандартная библиотека."


Ответ 3

Зависит от желаемого. Обход смежных вершин на списке выполнится не медленнее чем
в set или в вектор, зато сэкономит и память, и время в случае разряженного графа. 
Опрос "есть ли ребро между вершинами А и Б" на векторе выполнится за постоянное время,
на сете за логарифм, на списке линейно.