CODEWITHSUNDEEP
c++searchfind
Pekov
Pekov

Reputation: 537

Alternative of std::find that works faster

I have code that finds the new words in a container and adds them to the class private variable dict. The function Learner::Learn needs to be optimized so that it runs faster. The elements in the dict vector could repeat each other, but 'newWords' should always return the count of the new (non-repeated) words.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Learner {
private:
  vector<string> dict;

public:
  int Learn(const vector<string>& words) {
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        dict.push_back(word);
      }
    }
    return newWords;
  }

I tried this way, but the execution time is the same:

class Learner {
 private:
  vector<string> dict;

 public:
  int Learn(const vector<string>& words) {
    std::size_t index = dict.size();
    dict.resize(dict.size() + words.size());
    vector<string>::iterator nth = dict.begin() + index;
    int newWords = 0;
    for (const auto& word : words) {
      if (find(dict.begin(), dict.end(), word) == dict.end()) {
        ++newWords;
        *nth++ = word;
      }
    }
    return newWords;
  }

I should avoid using push_back() method somehow.

Upvotes: 0

Views: 1422

Answers (2)

Jarod42
Jarod42

Reputation: 217348

Trie is a efficient alternative, but not in std, so you have to write it yourself or use external library.

In std, std::set/std::map and unordered versions (std::unordered_set/std::unordered_map) might help

Upvotes: 1

Botje
Botje

Reputation: 30840

If you always keep words sorted you could use a binary search for a total runtime of O(n log n), but you have to shift the entire vector to insert things in the middle. (which will bring it back to O(n^2))

You should switch to another container for a significant improvement though:

  • std::set (O(log n) lookup, O(log n) insert)
  • std::map (O(log n) lookup, O(log n) insert)
  • std::unordered_set (O(1) lookup, O(1) insert)

Upvotes: 3

Related Questions