Разбивает строку в пар ключ-значение (на карте) C++

Question

У меня есть строка, как это:

"CA: ABCD\nCB: ABFG\nCC: AFBV\nCD: 4567" 

Теперь ": " расколы ключ от стоимости, а \n отделяющий пары. Я хочу добавить пары ключ-значение в карту на C++.

Есть ли эффективный способ сделать это с учетом оптимизации?

Answer 1

У меня здесь есть два метода. Первый из них - простой, очевидный метод, который я использую все время (производительность редко бывает проблемой). Второй метод, вероятно, более эффективен , но я не сделал никаких официальных таймингов.

В моих тестах второй метод примерно в 3 раза быстрее.

#include <map> 
#include <string> 
#include <sstream> 
#include <iostream> 

std::map<std::string, std::string> mappify1(std::string const& s) 
{ 
    std::map<std::string, std::string> m; 

    std::string key, val; 
    std::istringstream iss(s); 

    while(std::getline(std::getline(iss, key, ':') >> std::ws, val)) 
     m[key] = val; 

    return m; 
} 

std::map<std::string, std::string> mappify2(std::string const& s) 
{ 
    std::map<std::string, std::string> m; 

    std::string::size_type key_pos = 0; 
    std::string::size_type key_end; 
    std::string::size_type val_pos; 
    std::string::size_type val_end; 

    while((key_end = s.find(':', key_pos)) != std::string::npos) 
    { 
     if((val_pos = s.find_first_not_of(": ", key_end)) == std::string::npos) 
      break; 

     val_end = s.find('\n', val_pos); 
     m.emplace(s.substr(key_pos, key_end - key_pos), s.substr(val_pos, val_end - val_pos)); 

     key_pos = val_end; 
     if(key_pos != std::string::npos) 
      ++key_pos; 
    } 

    return m; 
} 

int main() 
{ 
    std::string s = "CA: ABCD\nCB: ABFG\nCC: AFBV\nCD: 4567"; 

    std::cout << "mappify1: " << '\n'; 

    auto m = mappify1(s); 
    for(auto const& p: m) 
     std::cout << '{' << p.first << " => " << p.second << '}' << '\n'; 

    std::cout << "mappify2: " << '\n'; 

    m = mappify2(s); 
    for(auto const& p: m) 
     std::cout << '{' << p.first << " => " << p.second << '}' << '\n'; 
} 

Выход:

mappify1: 
{CA => ABCD} 
{CB => ABFG} 
{CC => AFBV} 
{CD => 4567} 
mappify2: 
{CA => ABCD} 
{CB => ABFG} 
{CC => AFBV} 
{CD => 4567} 

Answer 2

Этот формат называется «Значение тега».

Наиболее важным критерием, в котором такое кодирование используется в отрасли, является, по-видимому, финансовый протокол FIX (= для разделителя значений ключа и '\001' как разделитель позиций). Поэтому, если вы находитесь на оборудовании x86, то лучшим вариантом будет «gsub» для анализа протокола SSE4 FIX и повторное использование открытых источников HFT-магазинов.

Если вы все еще хотите делегировать часть векторизации компилятору и можете сэкономить несколько наносекунд для удобства чтения, то самым изящным решением является сохранение результата в std::string (данные) + boost::flat_map<boost::string_ref, boost::string_ref> (просмотр). Парсинг - это вопрос вкуса, while-loop или strtok было бы проще всего проанализировать компилятор. Парсер, основанный на усилении духа, был бы проще всего для человека (знакомого с повышающим духом) читать.

С ++ для цикла на основе раствора

#include <boost/container/flat_map.hpp> 
#include <boost/range/iterator_range.hpp> 

#include <boost/range/iterator_range_io.hpp> 
#include <iostream> 

// g++ -std=c++1z ~/aaa.cc 
int main() 
{ 
    using range_t = boost::iterator_range<std::string::const_iterator>; 
    using map_t = boost::container::flat_map<range_t, range_t>; 

    char const sep = ':'; 
    char const dlm = '\n'; 

    // this part can be reused for parsing multiple records 
    map_t result; 
    result.reserve(1024); 

    std::string const input {"hello:world\n bye: world"}; 

    // this part is per-line/per-record 
    result.clear(); 
    for (auto _beg = begin(input), _end = end(input), it = _beg; it != _end;) 
    { 
     auto sep_it = std::find(it, _end, sep); 
     if (sep_it != _end) 
     { 
      auto dlm_it = std::find(sep_it + 1, _end, dlm); 
      result.emplace(range_t {it, sep_it}, range_t {sep_it + 1, dlm_it}); 
      it = dlm_it + (dlm_it != _end); 
     } 
     else throw std::runtime_error("cannot parse"); 
    } 

    for (auto& x: result) 
     std::cout << x.first << " => " << x.second << '\n'; 

    return 0; 
} 

Answer 3

Вот решение, используя strtok в качестве средства расщепления. Обратите внимание, что strtok изменяет вашу строку, она помещает '\ 0' в разделительный символ.

#include <iostream> 
#include <string> 
#include <map> 
#include <string.h> 

using namespace std; 



int main (int argc, char *argv[]) 
{ 
    char s1[] = "CA: ABCD\nCB: ABFG\nCC: AFBV\nCD: 4567"; 
    map<string, string> mymap; 
    char *token; 

    token = strtok(s1, "\n"); 
    while (token != NULL) { 
     string s(token); 
     size_t pos = s.find(":"); 
     mymap[s.substr(0, pos)] = s.substr(pos + 1, string::npos); 
     token = strtok(NULL, "\n"); 
    } 

    for (auto keyval : mymap) 
     cout << keyval.first << "/" << keyval.second << endl; 

    return 0; 
} 

Answer 4

Формат достаточно прост, что синтаксический разбор «вручную» ИМО является лучшим вариантом, в целом остается вполне читаемым.

Это также должно быть достаточно эффективным (в key и value строки всегда одинаковы - пусть clear ред, так перераспределении внутри основного контура должны просто остановиться после нескольких итераций); ret также должен претендовать на NRVO, OTOH в случае проблем с которыми вы всегда можете изменить на выходной параметр.

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

std::map<std::string, std::string> parseKV(const std::string &sz) { 
    std::map<std::string, std::string> ret; 
    std::string key; 
    std::string value; 
    const char *s=sz.c_str(); 
    while(*s) { 
     // parse the key 
     while(*s && *s!=':' && s[1]!=' ') { 
      key.push_back(*s); 
      ++s; 
     } 
     // if we quit due to the end of the string exit now 
     if(!*s) break; 
     // skip the ": " 
     s+=2; 
     // parse the value 
     while(*s && *s!='\n') { 
      value.push_back(*s); 
      ++s; 
     } 
     ret[key]=value; 
     key.clear(); value.clear(); 
     // skip the newline 
     ++s; 
    } 
    return ret; 
} 

Answer 5

Я сомневаюсь, что вы должны беспокоиться об оптимизации для чтения этой строки и преобразование его в std::map.Если вы действительно хотите оптимизировать эту карту с фиксированным содержимым, измените ее на std::vector<std::pair<>> и отсортируйте ее один раз.

Тем не менее, самый элегантный способ создания std::map со стандартными функциями C++ выглядит следующим образом:

std::map<std::string, std::string> deserializeKeyValue(const std::string &sz) { 
    constexpr auto ELEMENT_SEPARATOR = ": "s; 
    constexpr auto LINE_SEPARATOR = "\n"s; 

    std::map<std::string, std::string> result; 
    std::size_t begin{0}; 
    std::size_t end{0}; 
    while (begin < sz.size()) { 
     // Search key 
     end = sz.find(ELEMENT_SEPARATOR, begin); 
     assert(end != std::string::npos); // Replace by error handling 
     auto key = sz.substr(begin, /*size=*/ end - begin); 
     begin = end + ELEMENT_SEPARATOR.size(); 

     // Seach value 
     end = sz.find(LINE_SEPARATOR, begin); 
     auto value = sz.substr(begin, end == std::string::npos ? std::string::npos : /*size=*/ end - begin); 
     begin = (end == std::string::npos) ? sz.size() : end + LINE_SEPARATOR.size(); 

     // Store key-value 
     [[maybe_unused]] auto emplaceResult = result.emplace(std::move(key), std::move(value)); 
     assert(emplaceResult.second); // Replace by error handling 
    } 
    return result; 
} 

Выполнение этого не может быть идеальным, хотя каждый C++ программист понимает этот код.

Answer 6

Если вы беспокоитесь о производительности, вам следует, вероятно, пересмотреть необходимость конечного результата в качестве карты. Это может привести к тому, что в памяти будет много буферов символов. В идеале отслеживание только символа * и длины каждой подстроки будет быстрее/меньше.

Answer 7

Очень простое решение, использующее boost, следующее: оно работает также с частичными токенами (например, ключ без значений или пустые пары).

#include <string> 
#include <list> 
#include <map> 
#include <iostream> 

#include <boost/foreach.hpp> 
#include <boost/algorithm/string.hpp> 

using namespace std; 
using namespace boost; 

int main() { 

    string s = "CA: ABCD\nCB: ABFG\nCC: AFBV\nCD: 4567"; 

    list<string> tokenList; 
    split(tokenList,s,is_any_of("\n"),token_compress_on); 
    map<string, string> kvMap; 

    BOOST_FOREACH(string token, tokenList) { 
     size_t sep_pos = token.find_first_of(": "); 
     string key = token.substr(0,sep_pos); 
     string value = (sep_pos == string::npos ? "" : token.substr(sep_pos+2,string::npos)); 
     kvMap[key] = value; 

     cout << "[" << key << "] => [" << kvMap[key] << "]" << endl; 
    } 

    return 0; 
}