evenvalue's blog

Renaming Ordered Sets to something better
By evenvalue, 2 years ago, In English

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!

  • Vote: I like it
  • +69
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +31 Vote: I do not like it

Absolutely agree, petition to call it i_set

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

true (orz)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Wtf strong

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Everyone I know calls it indexed set lol

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +69 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

std::better_set

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

ChronoSorted Vector

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Chinese set

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

I see you have nothing better to do

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

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

Though, this set has it.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

I believe the name comes from ordered statistics.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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>;.

→ Reply