Как преобразовать отсортированный std :: список std :: pair в std :: map

Question

У меня есть std::list< std::pair<std::string,double> >, который, как я знаю, отсортирован по std::string element.

Поскольку я хотел бы сделать много std::find_if на основе элемента std::string, я считаю, что std::map<string,double,MyOwnBinaryPredicate> с lower_bound и upper_bound будет более адекватным.

Дело в том, что я хочу insert элементов в std::map эффективным способом.Поэтому я хочу использовать дополнительный итератор для ускорения insert.

Я считаю, что самый простой способ - использовать const_reverse_iterator, чтобы пройти через std::list и использовать begin()the std::map.

Вы бы сделали это таким образом, или это плохая идея?

Спасибо!

Answer 1

Если у вас уже есть отсортированный список, который отсортирован по предикату Predicate, вы можете просто сделать следующее:

std::list< std::pair<std::string, double> > sorted_list;
std::map<string, double, Predicate> map(sorted_list.begin(), sorted_list.end());

Конструктор map имеет линейную сложность по времени, если ваш список уже отсортирован, O (n * log n) в противном случае. Затем вы можете работать с картой напрямую, как и с любой другой.

Если позже вы захотите вернуть результаты в свой список, вы можете просто сделать наоборот:

sorted_list.assign(map.begin(), map.end());

Answer 2

Вы можете использовать std :: copy и std :: insertter:

std::copy(the_list.begin(),the_list.end(),std::inserter(the_map,the_map.begin()));  

потому что итератор для списка имеет тип значения, совместимый с итераторами отображения .

Answer 3

Я бы просто повторил список и вставил каждую пару в карту или использовал бы аккуратный метод, описанный Лютером Блиссеттом.
Тот факт, что я не понимаю, что вы пытаетесь сделать, означает, что это приведет либо кнечитаемый код или то, что у вас нет доступа.
Почему вы делаете это таким образом?
Можете ли вы изменить код для возврата вам карты вместо списка в первую очередь?