What is time complexity for find method in a set in c++?

Question

set<int> s;

s.insert(1);
s.insert(2);
...
s.insert(n);

I wonder how much time it takes for s.find(k) where k is a number from 1..n? I assume it is log(n). Is it correct?

Solution 1

O( log N ) to search for an individual element.

§23.1.2 Table 69

expression  return            note                                   complexity
a.find(k)   iterator;         returns an iterator pointing to an     logarithmic
            const_iterator    element with the key equivalent to k, 
            for constant a    or a.end() if such an element is not 
                              found

Solution 2

The complexity of std::set::find() being O(log(n)) simply means that there will be of the order of log(n) comparisons of objects stored in the set.

If the complexity of the comparison of 2 elements in the set is O(k) , then the actual complexity, would be O(log(n)∗k).
this can happen for example in case of set of strings (k would be the length of the longest string) as the comparison of 2 strings may imply comparing most of (or all) of their characters (if they start with the same prefix or are equal)

The documentation says the same:

Complexity

Logarithmic in size.

Comments

[snibbets]

Good information, but §23.1.2 Table 69 isn't much good without the name of the book.

[David Rodríguez - dribeas]

@snibbets: When dealing with a standarized language, the book is the standard. At the point of the answer that would be C++03 standard. In the current C++11 standard this would be §23.2.4 Table 102.