PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Not Frequent
 0/10

More Operations on Ordered Sets

Authors: Darren Yao, Benjamin Qi, Andrew Wang

Using iterators with sets, finding the next element smaller or larger than a specified key in a set.

Resources
IUSACOmodule is based off this
CP2see decription of BSTs and heaps

In ordered sets and maps, accessing or removing the next key higher or lower than some input k is also supported.

Using Iterators

In Bronze, we avoided discussion of any set operations involving iterators.

C++

Java

In Java, iterators are helpful for looping through sets.

Iterators used with HashSet would yield the elements in random order:

1Set<Integer> set = new HashSet<Integer>();
2set.add(1); set.add(3); set.add(0); set.add(-2);
3Iterator it = set.iterator();
4while(it.hasNext()){
5 Integer i = (Integer)it.next();
6 System.out.print(i + " "); // returns 0 1 -2 3
7}

But with TreeSet the elements are in sorted order:

1Set<Integer> set = new TreeSet<Integer>();
2set.add(1); set.add(3); set.add(0); set.add(-2);
3Iterator it = set.iterator();
4while(it.hasNext()){
5 Integer i = (Integer)it.next();
6 System.out.print(i + " "); // returns -2 0 1 3
7}

Instead of creating an iterator and looping with it like in C++, Java provides a for-each loop which creates a hidden iterator and loops with it automatically:

1Set<Integer> set = new TreeSet<Integer>();
2set.add(1); set.add(3); set.add(0); set.add(-2);
3for (int i : set){
4 System.out.print(i + " "); // returns -2 0 1 3
5}

Warning!

You shouldn't modify sets when traversing it with set iterators like in any other iterators for Collections (this INCLUDES when using a for-each loop). The only modification possible is using the iterator remove() method which can only be used once before calling a next() method.

Ordered Sets

C++

The ordered set also allows:

  • lower_bound: returns an iterator to the least element greater than or equal to some element k
  • upper_bound: returns an iterator to the least element strictly greater than some element k.
1set<int> s;
2s.insert(1); // [1]
3s.insert(14); // [1, 14]
4s.insert(9); // [1, 9, 14]
5s.insert(2); // [1, 2, 9, 14]
6cout << *s.upper_bound(7) << '\n'; // 9
7cout << *s.upper_bound(9) << '\n'; // 14
8cout << *s.lower_bound(5) << '\n'; // 9
9cout << *s.lower_bound(9) << '\n'; // 9
10cout << *s.begin() << '\n'; // 1

Warning!

Suppose that we replace s.upper_bound(7) with upper_bound(begin(s),end(s),7), which was the syntax that we used for vectors in the prerequisite module. This will still output the expected results, but its time complexity is linear in the size of the set s rather than logarithmic, so make sure to avoid it!

Java

The ordered set (TreeSet) allows for a multitude of additional operations:

  • first(): returns the lowest element in the set
  • last(): returns the greatest element in the set
  • lower(E v): returns the greatest element strictly less than v
  • floor(E v): returns the greatest element less than or equal to v
  • higher(E v): returns the least element strictly greater than v
  • ceiling(E v): returns the least element greater than or equal to v
1TreeSet<Integer> set = new TreeSet<Integer>();
2set.add(1); // [1]
3set.add(14); // [1, 14]
4set.add(9); // [1, 9, 14]
5set.add(2); // [1, 2, 9, 14]
6System.out.println(set.higher(7)); // 9
7System.out.println(set.higher(9)); // 14
8System.out.println(set.lower(5)); // 2
9System.out.println(set.first()); // 1
10System.out.println(set.last()); // 14

One limitation of the ordered set is that we can't efficiently access the kthk^{th} largest element in the set, or find the number of elements in the set greater than some arbitrary xx. These operations can be handled using a data structure called an order statistic tree.

Ordered Maps

C++

The ordered map also allows:

  • lower_bound: returns the iterator pointing to the lowest entry not less than the specified key
  • upper_bound: returns the iterator pointing to the lowest entry strictly greater than the specified key respectively.
1map<int, int> m;
2m[3] = 5; // [(3, 5)]
3m[11] = 4; // [(3, 5); (11, 4)]
4m[10] = 491; // [(3, 5); (10, 491); (11, 4)]
5cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n'; // 10 491
6cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n'; // 11 4
7m.erase(11); // [(3, 5); (10, 491)]
8if (m.upper_bound(10) == m.end())
9{
10 cout << "end" << endl; // Prints end

Java

The ordered map additionally supports firstKey / firstEntry and lastKey / lastEntry, returning the lowest key/entry and the highest key/entry, as well as higherKey / higherEntry and lowerKey / lowerEntry, returning the lowest key/entry strictly higher than the specified key, or the highest key/entry strictly lower than the specified key.

1TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
2map.put(3, 5); // [(3, 5)]
3map.put(11, 4); // [(3, 5); (11, 4)]
4map.put(10, 491); // [(3, 5); (10, 491); (11, 4)]
5System.out.println(map.firstKey()); // 3
6System.out.println(map.firstEntry()); // (3, 5)
7System.out.println(map.lastEntry()); // (11, 4)
8System.out.println(map.higherEntry(4)); // (10, 491)
9map.remove(11); // [(3, 5); (10, 491)]
10System.out.println(map.lowerKey(4)); // 3

Multisets

A multiset is a sorted set that allows multiple copies of the same element.

C++

In addition to all of the regular set operations,

  • the count() method returns the number of times an element is present in the multiset. However, this method takes time linear in the number of matches so you shouldn't use it in a contest.
  • If you want to remove a value once, make sure to use multiset.erase(multiset.find(val)) rather than multiset.erase(val). The latter will remove all instances of val.
1multiset<int> ms;
2ms.insert(1); // [1]
3ms.insert(14); // [1, 14]
4ms.insert(9); // [1, 9, 14]
5ms.insert(2); // [1, 2, 9, 14]
6ms.insert(9); // [1, 2, 9, 9, 14]
7ms.insert(9); // [1, 2, 9, 9, 9, 14]
8cout << ms.count(4) << '\n'; // 0
9cout << ms.count(9) << '\n'; // 3
10cout << ms.count(14) << '\n'; // 1

Java

While there is no multiset in Java, we can implement one using the TreeMap from values to their respective frequencies. We declare the TreeMap implementation globally so that we can write functions for adding and removing elements from it. The first, last, higher, and lower operations still function as intended; just use firstKey, lastKey, higherKey, and lowerKey respectively.

1static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();
2
3public static void main(String[] args){
4 ...
5}
6
7static void add(int x){
8 if(multiset.containsKey(x)){
9 multiset.put(x, multiset.get(x) + 1);
10 } else {

Priority Queues

Warning!

Priority queues are not implemented in the same way as sets and multisets, but they are included in this section because the operations that they perform can also be performed with sets.

Resources
CSA

A priority queue (or heap) supports the following operations: insertion of elements, deletion of the element considered highest priority, and retrieval of the highest priority element, all in O(logN)O(\log N) time according to the number of elements in the priority queue. Priority queues are simpler and faster than sets, so you should use them instead whenever possible.

C++

C++

1priority_queue<int> pq;
2pq.push(7); // [7]
3pq.push(2); // [2, 7]
4pq.push(1); // [1, 2, 7]
5pq.push(5); // [1, 2, 5, 7]
6cout << pq.top() << endl; // 7
7pq.pop(); // [1, 2, 5]
8pq.pop(); // [1, 2]
9pq.push(6); // [1, 2, 6]

Java

Java

In Java, we delete and retrieve the element of lowest rather than highest priority.

1PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
2pq.add(7); // [7]
3pq.add(2); // [7, 2]
4pq.add(1); // [7, 2, 1]
5pq.add(5); // [7, 5, 2, 1]
6System.out.println(pq.peek()); // 1
7pq.poll(); // [7, 5, 2]
8pq.poll(); // [7, 5]
9pq.add(6); // [7, 6, 5]

Introductory Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

iterators

Show Sketch
CSESNormal
Show Tags

set

Show Sketch
CSESNormal

Harder Example - Bit Inversions

Focus Problem – read through this problem before continuing!

Solution

We'll use iterators extensively.

Solution

Harder Problems

StatusSourceProblem NameDifficultyTagsSolution
SilverNormalExternal Sol
CFNormalCheck CF
SilverNormalExternal Sol
GoldHardExternal Sol
CFVery HardCheck CF
CFInsaneCheck CF

Module Progress:

Give Us Feedback on More Operations on Ordered Sets!

PrevNext