3

I have a C++ set<int> s, and an int a which I know is in s. Is there an O(log(size(s))) way for me to figure out the number of elements of s which are less than or equal to a? I could use std::distance(s.begin(), s.find(a)) + 1, but it takes O(size(s)) time.

Alternatively, does the STL provide a container that I can use for a set-like object that allows O(log(size(s))) insertion, removal, and range length queries?

Mees de Vries
  • 639
  • 3
  • 24
  • @jarod42, that answers the first part of my question (with "no, there is no such way for a `set`"), but not the second part ("is there a way to do it with the STL?"). Should I leave my question as is, rewrite it, or ask a separate question? – Mees de Vries Nov 09 '17 at 12:13
  • you can refer to [this answer](https://stackoverflow.com/a/18141241/5980430). AFAICT, there is no equivalent in *std*. – apple apple Nov 09 '17 at 12:15
  • I would says that second part goes under *"recommend or find a book, tool, software library, tutorial or other off-site resource are off-topic "*. – Jarod42 Nov 09 '17 at 12:17

0 Answers0