Эффективная структура выходных данных в C++

Question

Я работаю над проблемой интервального разбиения (например: http://kartikkukreja.wordpress.com/2013/09/26/interval-partitioning-problem/), где мне приходится писать оптимальные расписания в выходной файл. В настоящее время я использую map> для хранения интервалов, назначенных нескольким разделам. Первый int обозначает номер раздела, а соответствующий ему вектор обозначает интервалы, назначенные этому разделу.

Чтобы записать содержимое в файл, я повторяю все ключи карты и выписываю вектор для каждого ключа. Является ли это наиболее эффективной структурой данных для хранения данных (partition_number, interval)? или Могу ли я использовать что-то другое, кроме карты, чтобы я мог писать вывод гораздо быстрее?

Answer 1

Это очень зависит от того, что вы пытаетесь вывести. Например, лучшей структурой данных для решения этой проблемы является std::forward_list<std::pair<int,int>>, где первым int будет время, а второе int будет числом требуемых в настоящее время разделов.

Учитывая запросы:

Ваш std::forward_list будет содержать std::pair s:

(время, перегородки)
{0, 1},
{1, 2},
{3, 3},
{4, 1},
{5, 2},
{6, 1}, {
7, 0}

Имейте в виду, что, когда вы работаете с файлом IO, НЛ собирается быть львиная доля стоимости. Таким образом, на данный момент это просто вопрос о том, сколько усилий вы хотите поместить в демпинг этих данных. Если печать первой необходимости, как это не достаточно, дайте мне знать, и я, вероятно, может зацепить что-то еще выше:

std::cout << "(time, partitions)" << std::endl; 
for(auto i = partitions.begin(); i != partitions.end(); ++i){ 
    std::cout << std::setw(5) << i->first << std::setw(1) << ',' << std::setw(12) << i->second << std::endl; 
}