What Is a Sorted Set? Order, No Repeats, and a Game Example

What is a sorted set? It is a collection that keeps two promises at once: it never holds the same value twice, and it always keeps its values in order. You can add a value, take one out, and read the smallest or largest value at any time without sorting anything yourself.

Tank City Reboot has two free tank games set inside a computer that play in your browser with no account: every enemy, power-up and wall is named for a real computing or security idea, explained on the page.

This guide explains the two promises, the three operations you use most, and a real example from the second game, Tank City Zero Day. Its enemies plan their routes with a sorted set, and the way it uses one shows why you would pick this tool.

What is a sorted set?

A set is a collection with no repeats. Add the number 5 twice and the set still holds one 5. A sorted set is a set that also keeps its items in order, from smallest to largest by default, or in any order you define with a comparison rule.

Microsoft's documentation describes the .NET type SortedSet as a collection of objects kept in sorted order (SortedSet on Microsoft Learn). Other languages have the same idea under other names, such as an ordered set or a tree set. The idea is the same: no repeats, always in order.

The two promises: no repeats and always in order

No repeats. When you add a value that is already there, nothing changes. In .NET, Add tells you what happened: it returns false when the item was already in the set, and it does not throw an error (Add on Microsoft Learn). That makes a sorted set a handy way to remove duplicates from a list.

Always in order. You do not sort the set after a change. It keeps the order itself, so the smallest value is always one step away. In .NET, the Min property gives you the smallest value as defined by the comparer, the rule that says which of two items comes first.

Because the items are always in order, you can also walk through them from first to last, and ask for the biggest value as easily as the smallest.

The three operations you use most

• Add. Put a value in. It lands in its right place, and a repeat is ignored.
• Remove. Take a value out, wherever it sits. In .NET this is an O(log n) operation, which means the work grows slowly as the set grows: a set of a million items needs only about twenty steps.
• Min. Read the smallest value. Take it out with Remove when you want to process it.

The important part is that Remove works on any item, not only the first one. Hold on to that point, because it decides whether a sorted set or a simpler tool fits your job.

A worked example: keep the next task in order

Say you run a to-do list where each task has a number, and the lowest number goes first. Follow these steps with a sorted set:

1. Start with an empty set.
2. Add 7, then 2, then 9. The set now reads 2, 7, 9, even though you added 7 first.
3. Add 7 again. Nothing changes, because 7 is already there.
4. Read the minimum. It is 2. Remove it, and the set reads 7, 9.
5. Add 5. The set reads 5, 7, 9.

At every step the set was ready to hand you the next task. You never wrote a sort. That is the whole appeal of the tool.

How a tank game uses a sorted set to plan routes

In Tank City Zero Day, enemy tanks need to know the cheapest way across the arena. The arena is a grid of 25 by 25 cells. For every cell, the game works out the cheapest distance to a goal, such as your tank or the cells beside the core. A step costs 1, and a step onto firewall costs 4, because the firewall has to be shot through first. Steel, coolant and the core cannot be crossed, so the search skips them.

This is Dijkstra's algorithm, which our guide to Dijkstra's algorithm explains. The key rule is simple: always look at the unfinished cell with the lowest distance so far. The set of unfinished cells is the open set, and a sorted set fits it well.

In the game's code, the open set is a SortedSet of pairs, each holding a distance and a cell number. Each turn the game takes the smallest pair with Min, removes it, and looks at the cell's neighbours. Because the distance comes first in each pair, the smallest pair is the cheapest cell.

Why the game picks a sorted set over a plain list

A list that you sort every time would waste work. A sorted set keeps the cheapest cell on hand after each change. There is also a second reason, and it is the one about Remove.

Sometimes the search finds a shorter route to a cell that is already waiting in the set. The game then removes that cell's old pair from the middle of the set and adds the new, cheaper pair. This works because a sorted set can remove any item in O(log n) time. The code also skips any pair it takes out whose distance is larger than the one stored for the cell, as a safety check.

That is the difference from a queue that only gives you the front item, which our guide to priority queues covers. A plain priority queue is great when you only ever take the top. A sorted set is the better fit when you also need to take out an item from the middle.

You can see the result in Tank City Zero Day. The enemy map toward your tank is rebuilt every 0.3 seconds, and the map toward the core every 0.2 seconds at most, when walls change. Enemies follow the cheapest path through the firewall, so shooting a wall can send them a new way.

When to use a sorted set, and when not to

• Use it when you need no repeats and a steady order, you read the smallest or largest often, or you must remove items from anywhere in the collection.
• Use a plain list when repeats are fine and order does not matter. It is simpler and faster to build.
• Use a hash set when you only need to ask "is this value in here?" and do not care about order. It answers that question quickly but keeps no order.
• Use a priority queue when you only ever take the top item, and you never need to pull one out of the middle.

One thing to watch: two items that the comparison rule treats as equal count as repeats. If your rule only looks at distance, two cells with the same distance would collapse into one. That is why the game stores the cell number in the pair next to the distance, so no two pairs are ever equal.

Common mistakes

• Expecting repeats to be kept. If you need to count how often a value appears, a sorted set is the wrong tool.
• Changing an item's sort value while it is inside the set. The set will not notice. Remove the item first, change it, and add it back, which is what the game does with a cell's pair.
• Using a bad comparison rule. A rule that says two different items are equal drops one of them without a warning.

Frequently asked questions

What is the difference between a set and a sorted set?

Both refuse repeats. A sorted set also keeps its items in order, so you can read the smallest or largest value and walk through the items from first to last.

Is a sorted set the same as a sorted list?

No. A sorted list may hold repeats. A sorted set holds each value once.

How fast is a sorted set?

In .NET, removing an item is an O(log n) operation. That stays fast even for very large sets, because the work grows only a little each time the set doubles.

Is a sorted set a priority queue?

Not exactly. Both can give you the smallest item next. A sorted set also removes items from the middle and refuses repeats, which a plain priority queue usually does not.

Get started

Try the worked example in your own language: add a handful of numbers, add a repeat on purpose, and take the minimum out three times.

To see a sorted set at work in a game, play Tank City Reboot. It is free, plays in your browser on a computer or a phone, and needs no account.