C++: оптимальный поиск строки среди различных элементов std::map

306

28 августа 2017, 08:24

Всем привет!

Я использую C++ std::map для хранения данных TCP пакетов (в качестве значения map) в зависимости от TCP sequence number пакета (в качестве ключа). Был выбран именно std::map по той причине, что данные пакетов добавляются не по порядку, и их необходимо сортировать по их sequence number. std::map отлично это делает. В результате я получаю целостный TCP поток со всеми его пакетами в необходимом порядке.

После того, как данные всех пакетов добавлены в std::map, выполняется поиск заданной строки (данных, которые гарантированно были получены) по всему map.

Однако, искомая строка может быть расположена частично в одном элементе std::map, а частично - в другом элементе. То есть, искомые данные могут быть "размазаны" по map.

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

Соответственно, вопрос: есть ли способ оптимально найти строку в std::map, если, например начало строки находится в 1-м элементе map, а оставшаяся часть во 2-м элементе??? Может быть, мне необходимо выбрать другую структуру данных?

Спасибо заранее.

Answer 1

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

В общем случае, решение в лоб, обойти строки вручную (без склейки в одну большую строку):

void find_str(const map<int, string>& m, const string& s) {
  auto i = s.begin();
  for (auto const& e : m)
    for (auto const& c : e.second)
      if (c != *i)
        i = s.begin();
      else if (++i == s.end())
          cout << "found" << endl;
}

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

Более каноничный вариант - реализовать свой итератор, умеющий обходить строки в map, и использовать его в стандартных алгоритмах из std.

Рабочий пример на repl.it

Answer 2

Скорее всего, вам в реальной задаче нужно больше, чем просто найти подстроку. Для работы с фрагментированными строками хорошо использовать конечные автоматы. Они могут искать сразу много подстрок, они могут разбирать данные типа HTTP-заголовков, да и сам запрос. Если много потоков, то таблица состояний общая для всех и задана изначально, ее не надо лочить, только запоминать состояния для каждого потока. Разбор можно начинать, когда доступен первый пакет, а потом просто запоминать состояние + к асинхронности. В общем, с КА очень много интересного навертеть можно, потому кода никакого не пишу, это сложно, но эффективно. Но только в том случае, если вам нужно чуть больше, чем найти подстроку в фрагментированной строке.

Кода нет, хоть алгоритм немного опишу:
1) Допустим, у вас уже есть первый пакет, а второго нет.
2) С помощью КА вы уже можете начать делать упреждающий поиск вашей подстроки и чего угодно еще.
3) Поскольку второй пакет пока недоступен, вы запоминаете состояние конечного автомата (это может быть просто указатель - 8 байт), а когда второй пакет придет, продолжите поиск.
4) КА можно заставить работать и в обратную сторону, то есть второй пакет пришел а первый нет.

После того, как данные всех пакетов добавлены в std::map

При использовании КА вам не нужно ждать, пока соберутся все пакеты. Главное - дождаться первого (но это зависит от структуры передаваемых данных, в отдельных случаях можно и первого не ждать). Вы ведь пакеты собираете через что-то типа цикла с epoll?