\(\newcommand{\Set}[1]{\{#1\}}\) \(\newcommand{\Setdef}[2]{\{{#1}\mid{#2}\}}\) \(\newcommand{\PSet}[1]{\mathcal{P}(#1)}\) \(\newcommand{\Card}[1]{{\vert{#1}\vert}}\) \(\newcommand{\Tuple}[1]{(#1)}\) \(\newcommand{\Implies}{\Rightarrow}\) \(\newcommand{\Reals}{\mathbb{R}}\) \(\newcommand{\Seq}[1]{(#1)}\) \(\newcommand{\Length}[1]{{\vert{#1}\vert}}\) \(\newcommand{\Arr}[1]{[#1]}\) \(\newcommand{\Floor}[1]{{\lfloor{#1}\rfloor}}\) \(\newcommand{\Ceil}[1]{{\lceil{#1}\rceil}}\) \(\newcommand{\Path}[1]{(#1)}\) \(\newcommand{\IRange}[2]{[#1\,..\,#2]}\) \(%\newcommand{\Lg}{\lg}\) \(\newcommand{\Lg}{\log_2}\) \(\newcommand{\BigOh}{O}\) \(%\newcommand{\BigOh}{\mathcal{O}}\) \(\newcommand{\Oh}[1]{\BigOh(#1)}\)

Introduction: sets and maps

In this and the next round we are interested in the abstract data types for dynamic sets and maps. Here “dynamic” means that the elements, or key-value associations in maps, are inserted, searched for and removed all the time in an online fashion.

Sets

A basic API for a set abstract data type could be

  • insert(e) for inserting the element e in the set,

  • search(e) for finding whether the element e is in the set, and

  • remove(e) for deleting the element e from the set.

The figure below shows the set diagrams for two sets of strings, where the latter is obtained by inserting a new string in it.

_images/sets-insert.png

In Scala, this API corresponds to the collection.mutable.Set trait, which is implemented, among others, in the mutable TreeSet and HashSet classes. The methods corresponding to the ones in the asbtract API are

  • s.add(e) or s += e for inserting an element e into the set s,

  • s.contains(e) or s(e) for checking whether the set s contains the element e, and

  • s.remove(e) or s -= e for removing the element e from the set s.

In Java, the counterpart is the java.util.Set interface. In C++, the standard library contains two classes, set and unordered_set, implementing a variant of the API (the difference is explained below).

Maps

For maps, also called dictionaries in some programming languages, the API allows associating each key to a value.

_images/maps.png

In Scala collection.mutable.Map trait, the methods are called

  • m.update(k,v) or simply m(k) = v for setting the value of the key k to v in the map m,

  • m.apply(k) or simply m(k) for getting the value associated with the key k in the map m, and

  • m.remove(k) for removing the key k from the map m.

In the Java java.util.Map interface the methods are called put, get, and remove.

In the C++ standard library map and unordered_map classes, the methods are called

  • insert, or simply m[k] = v, for a map m, key k, and value v,

  • m.at(k), or simply m[k], and

  • m.erase(k).

Ordered sets and maps

In this round, we will in fact consider ordered sets and ordered maps that

  • ​ assume an ordering \(\le\) between the elements/keys, and

  • ​ allow efficient searching for the smallest, next smallest, etc element/key.

_images/maps-ordered.png

The abstract API of ordered sets extends the basic API with

  1. min for getting the smallest element in the set,

  2. max for getting the largest element in the set,

  3. predecessor(e) for getting the largest element that is smaller than e, and

  4. successor(e) for getting the smallest element that is larger than e.

Our goal is to have data structures and algorithms allowing the operations to be done in logarithmic time in the size of the set. Furthermore, the elements can be listed in ascending order in linear time. Note the difference to the priority queue API of the previous round (Section Priority queues with binary heaps): searching and removing arbitrary elements, as well as finding the minimum and successor elements, are now also supported.

Implementations in some programming languages:

  • ​ In Scala, the TreeSet class implements a variant of the API allowing ordered iteration over the elements in the set. In the class, head and firstKey give the smallest element, while last and lastKey return the largest element. Similarly, maxBefore and minAfter give the predecessor and successor elements.

    Some notes:

    1. min and max are slow, linear time generic operations.

    2. In the current Scala version, val s = collection.mutable.Set() creates a new “hash set” (covered in the next round) in which the ordering-based operations above take linear time in the worst case. Use val s = collection.mutable.TreeSet() to create an ordered set.

  • ​ In Java, the java.util.TreeSet API is close to the abstract one:

    • first gives the smallest element,

    • last gives the largest element,

    • higher(e) gives the smallest element that is larger than e, and

    • lower(e) gives the largest element that is smaller than e.

  • ​ The C++ standard library has the set class.

For maps, the corresponding classes are