Adding code to find first unused integer in set.

1 files changed, 12 insertions, 0 deletions

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.
+}