CODEWITHSUNDEEP
c++stringsearchfind
Lukali
Lukali

Reputation: 343

Can I check for a word inside of an array/vector without looping through it?

I believe that I can say...

for (int i = 0; i < noun[].size(); i++)
 {
    if ( word[0] == noun[i])
    { //do something }
 }

The problem is, that I need to do this many times with many words. And sometimes I'd like to do many words at once. Like if (words[0] == noun[/*any*/] && words[1] == verb [/*any*/]) Is there any way to just tell it to check every element inside the array/vector against it?

Or maybe there is some container similar to an array that allows quick lookup?

I was only able to find a way to do it in python, but I never programmed in python so I'd like a way to do it in C++.

In python I found something like this:

a = [1,2,3,4,5]
b = 4
if b in a:
  print("True!")
else:
  print("False")

from here: Check if a value exists in an array in Cython

Upvotes: 1

Views: 250

Answers (3)

MSalters
MSalters

Reputation: 180145

Considering your examples include verb and noun, you'll be trying to look up words in a (practically) fixed dictionary of sorts. There are many optimized containers for this purpose.

The Standard Library contains std::set<>, and a std::set<std::string> nouns will work. It has O(log N) lookup. Slightly more efficient, there's also std::unordered_map<>, which is still sufficient for your needs - you only need to know if a word occurs in the list of nouns, not what the next noun would be.

Outside the Standard Library, there are more data structures. A trie aka prefix tree shares the prefixes of its entries, which is space-efficient.

Upvotes: 0

HangrY
HangrY

Reputation: 149

The vector container isn't optimized for lookups. What you need is probably need a set. I recommend you check the answer to this question.

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234855

Unless there is some rule about the position of a particular element in a vector implying the position of another element, if present, the algorithm for the detection of presence must be O(N).

If the vector is sorted, for example, then a good positioning rule holds, and there are plenty of O(log(N)) algorithms out there: std::lower_bound is one such function.

Upvotes: 2

Related Questions