вставка станд.:: строки в к станд.:: карта
У меня есть программа, которая считывает данные из файла линию за линией. Я хотел бы скопировать некоторую подстроку той строки в к карте как указано ниже:
std::map< DWORD, std::string > my_map;
DWORD index; // populated with some data
char buffer[ 1024 ]; // populated with some data
char* element_begin; // points to some location in buffer
char* element_end; // points to some location in buffer > element_begin
my_map.insert( std::make_pair( index, std::string( element_begin, element_end ) ) );
Это std::map<>::insert() операция занимает много времени (Она удваивает время парсинга файла). Существует ли способ сделать это менее дорогой операцией?
Спасибо, PaulH
Править: чтобы быть более конкретным, я хочу знать, что я делаю минимальное количество операций копии для получения данных из файла в к карте.
8 ответов
Чтобы немного ответить на ваш дополнительный вопрос. Попробуйте временно изменить карту на вектор строк, а затем вставьте фиксированное строковое значение в вектор. Например:
vector <string> v;
string s( "foobar" );
your insert loop:
v.push_back( s );
Это должно дать вам нижнюю границу возможной скорости.
Кроме того, вам следует рассчитать время с включенной оптимизацией (если вы еще этого не сделали). Это может иметь большое значение для многих операций стандартной библиотеки.
Вам действительно нужна карта? Насколько я могу видеть в вашем примере, вы хотите сохранить только индекс как значение ключа, которое, как я полагаю, просто увеличивается при каждой вставке. Вы можете сделать это с помощью std :: vector , который, как известно, является самым быстрым контейнером. Просто используйте push_back и получите доступ к значению с помощью в (индексе) .
Возможно, вы могли бы попробовать другую версию конструктора строк:
string ( const char * s, size_t n );
Если ваша реализация строки не имеет специализации для char * , он будет вынужден пройти указанный диапазон и скопировать каждый символ по отдельности. В этом случае приведенный выше конструктор может быть быстрее (хотя это всего лишь предположение).
Есть несколько вещей, которые вы можете попробовать. Накладные расходы связаны как с структурой данных, так и с созданием самой строки.
Это должна быть карта
std :: tr1 :: unordered_mapи посмотреть, поможет ли это.Насколько быстрым должен быть поиск? Вы можете попробовать
std :: vector, если можете жить с временем поиска O (n).Вам нужно хранить копию каждой подстроки? Не могли бы вы вместо этого просто сохранить указатель?
Если ваш компилятор не может оптимизировать избыточные копии во вставке, вы можете использовать оператор скобок для назначения непосредственно в карту:
my_map[index].assign(element_begin, element_end)
Изменить: как указывает Нил, это не поможет, если есть возможность быть вставлены дубликаты ключей.
Я считаю, что большую часть времени при выполнении с картой вы копируете строки. std :: map любит иметь собственную копию всего. Поэтому при вставке std :: map создает копию ключа и значения.
Давным-давно, когда процессоры были медленными, а память была маленькой, программисты использовали указатели на «большие» элементы данных и передавали указатель вместо того, чтобы каждый раз копировать данные. Указатель - это объект гораздо меньшего размера, чем строка, и для его копирования требуется меньше времени. Возможно, вам следует сохранить указатели на строки в карте:
#include <map>
#include <string>
#include "boost/shared_ptr.hpp"
typedef boost::shared_ptr<string> Shared_Str_Ptr;
typedef std::map< DWORD, Shared_Str_Ptr> Map_Container;
//...
Map_Container my_map;
Shared_Str_Ptr p_str(new std::string("Hello"));
my_map[5] = p_str;
shared_ptr позаботится об управлении памятью за вас, поэтому не нужно беспокоиться при удалении карты или ее содержимого.
См. Также Повышение интеллектуальных указателей .
вы храните строки, но я предполагаю, что вы их уже прочитали, и они добавляют их на карту. Это приведет к копии. Если вы сохраните в нем указатель на строку (строка * вместо строки), вероятно, будет быстрее.
Учитывая, что вам нужно поместить данные в std::map, то да, вы делаете минимальное количество операций копирования, чтобы получить данные на карту.