[Rcpp-devel] What is the most efficient method to check if a Rcpp vector contains an element?

Hadley Wickham h.wickham at gmail.com
Tue Dec 31 16:29:05 CET 2013

> I believe you are mistaken. sorting is an expensive O( N log(N) ) operation.
> I’d use something like std::find (or std::any_of if you use C++11). Those
> are O(N)
> Otherwise, you might like Rcpp::any or Rcpp::any_of

It depends on the scenario - if you want to look up M values in a
vector of length N, then sorting + binary search will be O(M log(N) +
N log(N)) where scanning each time will be O(MN). If M = 1, there's no
point presorting, but if it's large, it pays to sort first.



More information about the Rcpp-devel mailing list