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

Question

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

I'm sure you can use some [algorithms](http://en.cppreference.com/w/cpp/algorithm) to do this. Obviously these would internally have a loop of some kind but you don't have to do it yourself. — Kevin, Mar 05 '18 at 17:13
@KillzoneKid so a noun can be any noun from a list of nouns, e.g. Alice, Thomas, Mark, etc. My words vector would consist of words that make up a string entered by the user. — Lukali, Mar 05 '18 at 17:31
i believe you are looking for `std::find`. Of course that will loop through the vector, just as the python example will be doing, its just that you dont have to code the loop — pm100, Mar 05 '18 at 17:43

score 2 · Accepted Answer · answered Mar 05 '18 at 17:15

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.

HangrY · Answer 2 · 2018-03-06T09:05:53.043

0

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.

edited Mar 06 '18 at 09:05

answered Mar 05 '18 at 17:37

HangrY

139
8

If it's just a matter of in the array or not, a `set` would probably be preferable to a map (what would the value of the key/val pairs be?) – scohe001 Mar 05 '18 at 18:07
Just checked the set implementation, you are right. Just edited. – HangrY Mar 06 '18 at 09:06

score 0 · Answer 3 · answered Mar 06 '18 at 09:35

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.

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

3 Answers3