Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

evenvalue's blog

Renaming Ordered Sets to something better
By evenvalue, 5 months 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

»
5 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Absolutely agree, petition to call it i_set

→ Reply
»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

true (orz)

→ Reply
»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Wtf strong

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Everyone I know calls it indexed set lol

→ Reply
»
5 months ago, # |
  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
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

std::better_set

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    ah yes, betset for short

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    please stop making me think of what would bitter_set for short is..

    → Reply
»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

ChronoSorted Vector

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

Chinese set

→ Reply
»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I see you have nothing better to do

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Did you use magic to spy on him and see it?

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      idk whether he used magic to spy on me or not, but what he said was not untrue

      → Reply
»
5 months ago, # |
← 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
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ranked Set

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

set2

→ Reply
»
5 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I believe the name comes from ordered statistics.

→ Reply
»
4 months ago, # |
  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