вставка std :: strings в std :: map

Question

У меня есть программа, которая читает данные из файла построчно. Я хотел бы скопировать некоторую подстроку этой строки на карту, как показано ниже:

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

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

Answer 1

Возможно, вы могли бы попробовать другую версию строкового конструктора:

string ( const char * s, size_t n );

Если ваша реализация строки не имеет специализации для char *, она будет вынуждена пересечь заданный диапазон и скопировать каждый символ в отдельности. В этом случае приведенный выше конструктор может быть быстрее (хотя бы предположение).

Answer 2

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

1. Это должен быть map? Вместо этого вы можете попробовать std::tr1::unordered_map и посмотреть, поможет ли это.

2. Насколько быстрым должен быть поиск? Вы можете попробовать std::vector, если вы можете жить с O (n) время поиска.

3. Вам нужно хранить копию каждой подстроки? Не могли бы вы вместо этого просто сохранить указатель?

Answer 3

Вам действительно нужна карта здесь? Насколько я вижу в вашем примере, вы хотите сохранить индекс только в качестве значения ключа, которое, как я полагаю, просто увеличивается для каждой вставки. Вы можете сделать это с помощью std::vector, который, как известно, является самым быстрым контейнером. Просто используйте push_back и получите доступ к значению с помощью at(index).

Answer 4

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

vector <string> v;
string s( "foobar" );

your insert loop:
   v.push_back( s );

Это должно дать вам более низкую оценку того, что возможно относительно скорости.

Кроме того, вам следует рассчитывать время, когда все оптимизации включены (если вы этого еще не сделали). Это может иметь удивительное значение для многих операций стандартной библиотеки.

Answer 5

Я полагаю, что большая часть вашего времени выполнения с картой копирует строки. 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 позаботится об управлении памятью, чтобы не беспокоиться об удалении карты или ее содержимого.

См. Также Повышение интеллектуальных указателей .

Answer 6

Учитывая, что вам нужно поместить данные в std::map<DWORD, std::string>, тогда да, вы выполняете минимальное количество операций копирования, чтобы получить данные на карту.

Answer 7

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

my_map[index].assign(element_begin, element_end)

Редактировать: Как отмечает Нейл, это не поможет, если будут вставлены дубликаты ключей.

Answer 8

вы храните строки, но я думаю, что вы уже прочитали их, и они добавляют их на карту. Это приведет к копии. Если вы храните в нем указатель на строку (строка * вместо строки), вероятно, будет быстрее.