использовать карту вместо вектора

Question

Я расширяю уже существующий код на C++. Один из членов класса имеет тип вектора другого класса объектов:

class Road 
{ 
    .... 
    vector<Link*> links; //Link is just another class 
} 

Остальные модули используют этот класс и его член через много итераторы последовательности. Теперь, расширяя код, мне нужно добавить элемент в класс Link, называемый linkID, и использовать этот идентификатор ссылки, чтобы найти/получить доступ к моим объектам «Ссылка».

Проблема: Я не собираюсь искать объект Link (используя LinkID) в векторе, итерации по миллионам элементов, чтобы найти конкретный объект Link. Лучшим решением является «карта»! правильно?

.... 
map<linkID,*link> links 
.... 
lnk=links[linkID] 
......... 

Но проблема в том, что я не могу изменить текущий исходный код, за исключением очень незначительных модификаций Лика добавления LinkId и т.д.

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

Answer 1

Лучшее решение - «карта»! правильно?

Да, звучит как карта, это самое простое решение вашей проблемы. Но вместо использования оператора [] я бы использовал методы поиска и вставки.

Первоначально, вы можете изменить код, чтобы использовать карту этого типа std::map< unsigned int, link* >, так как это самое похожее на vector< link* >. Затем вы можете легко переключиться на std::map< LinkId, link* >.

Answer 2

Скрыть карту как вектор невозможно.

В теории вы можете попытаться реализовать новый класс , полученный из вектора (т. Е. Использует std::vector в качестве базового класса). Внутри он мог использовать карту, а снаружи он имел бы интерфейс вектора (и он был бы принят в качестве замены вектора, потому что он был получен из него).

На практике у вас может возникнуть ряд проблем. Вы, очевидно, наследовали бы внутренние структуры данных вектора, так что вам пришлось бы игнорировать их в своей реализации, т. Е. Оставить их пустыми. Вывод из классов STL (кроме basic_) также противоречит рекомендуемой практике и, возможно, рискованному, как отмечает @Als в комментарии ниже.

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

Answer 3

Я думаю, что вы могли бы сделать, это сделать дополненную структуру данных: vectormap, которая позволяет иметь шпоночный доступ к элементам по linkID и который также поддерживает операции std::vector. Оператор [] этого объекта может быть перегружен, так что links[3] дает вам позиционный доступ к вектору, а links[linkID] просматривает ID ссылки на карте.Такие вещи, как push_back, могут поддерживаться, если код им нужен: push_back пришлось бы вставить элемент в вектор, а затем сделать map[item->linkID] = item, чтобы ввести его на карту. Вы, вероятно, получите картину.

Answer 4

Я сделал это много лет назад для сети железных дорог. Базовыми классами были ссылка и узел. Фактические железнодорожные и в конечном итоге маршруты были основаны на вершине этих. IIRC I использовал std::list, чтобы содержать ссылки и узлы и использовать векторы векторов для размещения фактических треков.

Answer 5

Правильное решение, если linkID является членом Link, будет std::set<Link*, OrderByLinkID>. Предикат OrderByLinkID принимает два Link* и возвращает true, если первый имеет меньший элемент linkID.

В результате std :: set по-прежнему содержит Link*, и вы можете перебирать их так же, как std :: vector. Для сравнения: с std :: map вы закончите повторение более std::pair<Link*, LinkID>, что значительно больше.