title: How to reduce time complexity under c++ with nested loops and regex?
body: <p>I have such function.</p>
  
  <p>Input argument - vector of user names, vector of strings, number of top users.</p>
  
  <p>First I count amount of occurancies for each user in strings. If there are several occurancies in one string - it still counts as 1.</p>
  
  <p>Then I sort it by amount of occurancies. If amount of occurancies are equal - sort alphabetically user names.</p>
  
  <p>And function return top N users with the most occurancy.</p>
  
  <pre><code>std::vector&lt;std::string&gt; GetTopUsers(const std::vector&lt;std::string&gt;&amp; users,
      const std::vector&lt;std::string&gt;&amp; lines, const int topUsersNum) {
      std::vector&lt;std::pair&lt;std::string, int&gt;&gt; userOccurancies;
  
      //count user occurancies
      for (const auto &amp; user : users) {
          int count = 0;
          for (const auto &amp;line : lines) {
              std::regex rgx("\\b" + user + "\\b", std::regex::icase);
              std::smatch match;
              if (std::regex_search(line, match, rgx)) {
                  ++count;
                  auto userIter = std::find_if(userOccurancies.begin(), userOccurancies.end(),
                      [&amp;user](const std::pair&lt;std::string, int&gt;&amp; element) { return element.first == user; });
                  if (userIter == userOccurancies.end()) {
                      userOccurancies.push_back(std::make_pair(user, count));
                  }
                  else {
                      userIter-&gt;second = count;
                  }
              }
          }
      }
  
      //sort by amount of occurancies, if occurancies are equal - sort alphabetically
      std::sort(userOccurancies.begin(), userOccurancies.end(),
          [](const std::pair&lt;std::string, int&gt;&amp; p1, const std::pair&lt;std::string, int&gt;&amp; p2)
      { return (p1.second &gt; p2.second) ? true : (p1.second == p2.second ? p1.first &lt; p2.first : false); });
  
      //extract top N users
      int topUsersSz = (topUsersNum &lt;= userOccurancies.size() ? topUsersNum : userOccurancies.size());
      std::vector&lt;std::string&gt; topUsers(topUsersSz);
      for (int i = 0; i &lt; topUsersSz; i++) {
          topUsers.push_back(userOccurancies[i].first);
      }
  
      return topUsers;
  }
  </code></pre>
  
  <p>So for the input</p>
  
  <pre><code>    std::vector&lt;std::string&gt; users = { "john", "atest", "qwe" };
      std::vector&lt;std::string&gt; lines = { "atest john", "Qwe", "qwe1", "qwe," };
  
      int topUsersNum = 4;
  </code></pre>
  
  <p>output will be <code>qwe atest john</code></p>
  
  <p>But it looks very complex. O(n^2) for loops + regex inside. It must be O(n^3) or even more.</p>
  
  <p>Can you give me please advices how to make it with less complexity in c++11?</p>
  
  <p>And also give me advices about code. </p>
  
  <p>Or maybe there are better board for questions about complexity and performance?</p>
  
  <p>Thank you.</p>
  
  <p><strong><em>UDP</em></strong></p>
  
  <pre><code>   std::vector&lt;std::string&gt; GetTopUsers2(const std::vector&lt;std::string&gt;&amp; users,
      const std::vector&lt;std::string&gt;&amp; lines, const size_t topUsersNum) {
      std::vector&lt;std::pair&lt;std::string, int&gt;&gt; userOccurancies(users.size());
  
      auto userOcIt = userOccurancies.begin();
      for (const auto &amp; user : users) {
          userOcIt-&gt;first = std::move(user);
          userOcIt-&gt;second = 0;
          userOcIt++;
      }
  
      //count user occurancies
      for (auto &amp;user: userOccurancies) {
          int count = 0;
          std::regex rgx("\\b" + user.first + "\\b", std::regex::icase);
          std::smatch match;
          for (const auto &amp;line : lines) {
              if (std::regex_search(line, match, rgx)) {
                  ++count;
                  user.second = count;
              }
          }
      }
  
      //sort by amount of occurancies, if occurancies are equal - sort alphabetically
      std::sort(userOccurancies.begin(), userOccurancies.end(),
          [](const std::pair&lt;std::string, int&gt;&amp; p1, const std::pair&lt;std::string, int&gt;&amp; p2)
      { return (p1.second &gt; p2.second) ? true : (p1.second == p2.second ? p1.first &lt; p2.first : false); });
  
      //extract top N users
      auto middle = userOccurancies.begin() + std::min(topUsersNum, userOccurancies.size());
      int topUsersSz = (topUsersNum &lt;= userOccurancies.size() ? topUsersNum : userOccurancies.size());
      std::vector&lt;std::string&gt; topUsers(topUsersSz);
      auto topIter = topUsers.begin();
      for (auto iter = userOccurancies.begin(); iter != middle; iter++) {
          *topIter = std::move(iter-&gt;first);
          topIter++;
      }
  
      return topUsers;
  }
  </code></pre>
  
  <p>Thanks to @Jarod42. I updated first part. I think that allocate memory to vector once at constructor is faster than call <code>emplace_back</code> every time, so I used it. If I am wrong - mark me.</p>
  
  <p>Also I use c++11, not c++17.</p>
  
  <p>time results:</p>
  
  <pre><code>Old: 3539400.00000 nanoseconds
  New: 2674000.00000 nanoseconds
  </code></pre>
  
  <p>It is better but still looks complex, isn't it?</p>