Как эффективно преобразовать вектор <pair <int, int>> в multimap <int, int>?

Question

How to convert a multimap<int,int> to vector<pair<int,int> > efficiently

EDIT: Извините за беспокойство, я действительно искал преобразование вектора в карту

Answer 1

Тип значения multimap<int,int> равен pair<int,int> - именно то, что вы хотите, чтобы ваш вектор содержал. Таким образом, вы можете использовать конструктор для инициализации вектора из мультикарты:

std::vector< std::pair<int,int> > v( mmap.begin(), mmap.end() );

Или, если у вас есть существующий вектор, в который вы хотите скопировать элементы:

v.resize( mmap.size() );
std::copy( mmap.begin(), mmap.end(), v.begin() );

Вы также можете использовать std::back_inserter, но в целом это будет медленнее из-за перераспределения векторов:

std::copy( mmap.begin(), mmap.end(), std::back_inserter(v) );

EDIT Чтобы ответить на ваш другой вопрос - вы можете преобразовать вектор в мультикарту аналогичным образом. Мультикарта также имеет конструктор, который принимает диапазон итератора:

std::multimap<int,int> mmap(v.begin(), v.end());

Это, конечно, предполагает, что v это std::vector< std::pair<int,int> >.

Answer 2

Я считаю, что наивный подход также самый эффективный: переберите мультикарту и добавьте каждый элемент в вектор. В качестве оптимизации вы должны v.reserve(m.size) перед началом работы.

Элементы обычно хранятся в дереве в мультикарте, в объектах, распределенных по куче. Что касается вектора, они должны находиться в непрерывной памяти: для этого вам действительно нужно скопировать их вместе.