Временная сложность функции Boost Graph vertex() в adjacency_list ⇐ C++

[Anonymous]

Меня смущает временная сложность функции Boost Graph vertex() при работе со списком adjacency_list.
Эта страница в руководстве выглядит как утверждают, что функция vertex() выполняется за постоянное время, даже если параметр шаблона VertexList равен listS.

• vertex()
  Эта операция имеет постоянное время для vecS и для listS.

Однако это для меня загадка, как функция может работать с постоянным временем, когда базовая структура данных представляет собой std::list. Я просмотрел сгенерированный объектный код и обнаружил, что функция vertex() компилируется в итеративный цикл, когда VertexList=listS, а не в постоянный поиск, когда VertexList=vecS.
Наконец, я создал небольшую тестовую программу, которая подтверждает, что время выполнения масштабируется в зависимости от значения индекса, передаваемого в vertex() при использовании listS.
Как это складывается?
Есть ли какой-то особый способ заставить vertex() работать за постоянное время, или я неправильно понял документацию, или документация просто неверна?
// Sample code showing non-constant run time of vertex()
boost::adjacency_list<
boost::vecS,
boost::listS, // program is fast when I change this to vecS
boost::undirectedS> g;

// Generate random graph with 10000 vertices.
std::mt19937 rng(1234);
boost::generate_random_graph(g, 10000, 20000, rng, false);

// Repeated lookup of vertex in graph
// takes 10 seconds for listS, 0.02 seconds for vecS
int result = 0;
std::uniform_int_distribution vdist{0, int(boost::num_vertices(g) - 1)};
for (int i = 0; i < 1000000; ++i) {
int v = vdist(rng);
result += boost::out_degree(boost::vertex(v, g), g);
}
std::cout

Подробнее здесь: https://stackoverflow.com/questions/792 ... cency-list