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

Автор evenvalue, 5 месяцев назад, По-английски

Hello Codeforces!

I wanted to discuss something extremely important. About the name for Ordered Sets.

The normal std::set is also ordered, then why is it not called ordered set? Ordered Sets aren't useful because they are just ordered, its because they also allow us to index the set.

Hence I believe Indexed Sets would be a better name for it. If you have any other suggestions for the name lmk!

  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Absolutely agree, petition to call it i_set

»
5 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

true (orz)

»
5 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Wtf strong

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Everyone I know calls it indexed set lol

»
5 месяцев назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

Everyone asks why ordered set, but no one asks how's ordered set :(

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

std::better_set

»
5 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

ChronoSorted Vector

»
5 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Chinese set

»
5 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I see you have nothing better to do

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Well, from my understanding it is called that as short for order statistic sets, since they provide order statistic about the set. But I agree, indexed set is a good name.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ranked Set

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

set2

»
5 месяцев назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

How do you index the std::set? I think, it doesn't have interface to find $$$k$$$-th element.

Though, this set has it.

»
3 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I believe the name comes from ordered statistics.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I believe the name ordered_set was popularized by this blog 10 years ago introducing Policy-based data structures here on Codeforces. The most accurate name for the data structure is probably Order Statistic Tree (USACO Guide also mentions the name here). However, you can abstract it as whatever makes the most sense (and convenient) to you. For me, I use indexed_set because it sounds reasonable enough since you can practically index the set (not multiset) using order_of_key. As a matter of fact, the Competitive Programmer's Handbook also mentions it here.

Or if you're lazy, using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;.