From 362b09086a49bed54182fc177908ba23c1757660 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 10 Jun 2017 23:47:37 +0200
Subject: Adding code to find first unused integer in set.

---
 datastructures/datastructures.tex |  3 +++
 datastructures/firstUnused.cpp    | 12 ++++++++++++
 2 files changed, 15 insertions(+)
 create mode 100644 datastructures/firstUnused.cpp

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 7659a7e..a2c5ff6 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -23,3 +23,6 @@ Dazu: Offset in den inneren Knoten des Baums speichern.
 
 \subsection{Treap (Cartesian Tree)}
 \lstinputlisting{datastructures/treap.cpp}
+
+\subsection{Erste unbenutzte natürliche Zahl}
+\lstinputlisting{datastructures/firstUnused.cpp}
diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp
new file mode 100644
index 0000000..141eb00
--- /dev/null
+++ b/datastructures/firstUnused.cpp
@@ -0,0 +1,12 @@
+// Erste natürliche Zahl nicht im set used.
+set<int> used;
+int unusedCounter = 1;
+
+int getFirstUnused() { // Laufzeit: O(log n) amortisiert.
+  auto it = used.lower_bound(unusedCounter);
+  while (it != used.end() && *it == unusedCounter) {
+    it++;
+    unusedCounter++;
+  }
+  return unusedCounter++; // Evtl. neuen Wert noch hinzufügen.
+}
-- 
cgit v1.2.3