Блог пользователя ACCEPT

question for set in C++
Автор ACCEPT, 14 лет назад, По-английски
is there any function in C++ for set, that return the i-th element of set in O(lgn) or return the place of an element in set?
for example given a set S= {7,8,9,10,11}, then firsrt function for call 2 return 8 and second function for call 8 return 2.
sorry for my very poooooooooooooooor english! 
Теги c++, set
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
No, there isn't.

The only thing that have some kind of such funcionality is lower_bound method.
For example:

set<int> s;
for(int i = 1; i <= 10; ++i)
s.insert(i);

set<int>::iterator it = s.lower_bound(3); //(*it) == 3
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
No, there isn't such functions. You need to implement your own balanced binary search tree for this.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
I know a lot of people who tried to solve this with C++ set. Nobody has succeeded. :)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Suggestion for may be non-portable extension in the STL set class is here.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
many thank's for all!
→ Ответить