CODEWITHSUNDEEP
c++searchstdvector
remi
remi

Reputation: 1047

Effective search in sorted string vector

I have a long vector of strings. Example:

std::string data;
data.push_back("abc");
data.push_back("bcd");
//...
data.push_back("zze");
data.push_back("zzz");

The strings in the vector are alphabetically sorted.

I understand I can use std::find to find the existence and position of a string in the std::vector. But since my vector is alphabetically sorted, is there an easy to implement and more effective method to check the existence of a value in the vector?

Upvotes: 0

Views: 1134

Answers (1)

Edgar Rokjān
Edgar Rokjān

Reputation: 17483

If the container is sorted, you might use std::binary_search:

Checks if an element equivalent to value appears within the range [first, last).

std::string some_value = "xyz";

const auto found =
    std::binary_search(std::cbegin(data), std::cend(data), some_value);

So found is true if some_value is found and false in the other case.

If you are interested in getting an iterator which points to the element you are looking for, then consider using std::lower_bound:

const auto it =
    std::lower_bound(std::cbegin(data), std::cend(data), some_value);

if (it != std::cend(data)) {
    // element is found, it points to this element
}

Upvotes: 4

Related Questions