adjacent_find<\/a><\/code> will find the first gap for us. So one solution would be:<\/p>\n\r\n\/\/ assuming our set is in an array or vector\r\nstd::sort(a.begin(), a.end());\r\nauto p = std::adjacent_find(\r\n a.begin(), a.end(), \r\n [] (int x, int y) { return y-x > 1; });\r\nint unused = a.back() + 1;\r\nif (p != a.end())\r\n unused = *p + 1;\r\n<\/pre>\nThe asymptotic complexity of this solution is of course O(n.log(n)), since adjacent_find<\/code> is linear and the complexity of sort<\/a><\/code> dominates. Is there a better solution? It’s not obvious at first glance, but there is a linear time solution to this problem. The key is a divide and conquer strategy using that workhorse of algorithms, partition<\/a><\/code>.<\/p>\nThe smallest unused number<\/strong><\/p>\nLet’s start by assuming that the minimum unused value is zero. We’ll choose a pivot value, m<\/code>, which is the assumed midpoint of the sequence – it doesn’t actually have to be present in the sequence, but we’re going to simply assume that it’s the middle value. Partitioning the sequence about the pivot, we’ll get a situation like this:
\n![\"Partitioned](\"https:\/\/www.elbeno.com\/blog\/wp-content\/uploads\/2017\/06\/min_unused_1.png\")
\nwhere the first value equal to or greater than m<\/code> is at position p<\/code> (which is returned by the call to partition<\/code>). If the lower half of the sequence has no gaps, m<\/code> will be equal to p<\/code>, and we can recurse on the top half of the sequence, setting the new minimum unused value to m<\/code>.<\/p>\nWe know that m<\/code> cannot be less than p<\/code> since there cannot be any repetitions in the set. Therefore, if m<\/code> is not equal to p<\/code>, it must be greater – meaning that there is at least one gap below p, and that we can recurse on the bottom half of the sequence (keeping the minimum unused value as-is).<\/p>\nThe base case of the algorithm is when the sequence we need to partition is empty. At that point we will have found the minimum unused value. Here’s the algorithm in code, with a bit of setup:<\/p>\n
\r\nvoid min_unused()\r\n{\r\n \/\/ initialize RNG\r\n std::array seed_data;\r\n std::random_device r;\r\n std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));\r\n std::seed_seq seq(std::begin(seed_data), std::end(seed_data));\r\n std::mt19937 gen(seq);\r\n\r\n \/\/ fill an array with ints, shuffle, discard some\r\n int a[10];\r\n std::iota(&a[0], &a[10], 0);\r\n std::shuffle(&a[0], &a[10], gen);\r\n int first_idx = 0;\r\n int last_idx = 7; \/\/ arbitrary truncation\r\n\r\n for (int i = first_idx; i < last_idx; ++i)\r\n std::cout << a[i] << '\\n';\r\n\r\n \/\/ the algorithm\r\n int unused = 0;\r\n while (first_idx != last_idx) {\r\n int m = unused + (last_idx - first_idx + 1)\/2;\r\n auto p = std::partition(&a[first_idx], &a[last_idx],\r\n [&] (int i) { return i < m; });\r\n if (p - &a[first_idx] == m - unused) {\r\n unused = m;\r\n first_idx = p - &a[0];\r\n } else {\r\n last_idx = p - &a[0];\r\n }\r\n }\r\n\r\n std::cout << \"Min unused: \" << unused << '\\n';\r\n}\r\n<\/pre>\nYou can also see the algorithm on wandbox<\/a>. I leave it to you to convince yourself that the algorithm works. The asymptotic complexity of the algorithm is linear; at each stage we are running partition<\/code>, which is O(n), and then recursing, but only on one half of the sequence. Thus, the complexity is:<\/p>\n[latex]O(n + \\frac{n}{2} + \\frac{n}{4} + \\frac{n}{8} + ...) = O(\\sum_{i=0}^\\infty \\frac{n}{2^i}) = O(2n) = O(n)[\/latex]<\/p>\n
From concrete to generic: first steps<\/strong><\/p>\nSo, now we have an algorithm that works... for C-style arrays, and in one place only. Naturally we want to make it as generic as we can; what, then, are the steps to transform it into a decent algorithm that can be used just as easily as those in the STL? Perhaps you're already thinking that this is overly concrete - but hey, this is a pedagogical device. Bear with me.<\/p>\n
First, we can pull the algorithm out into a function. You've already seen the setup code, so you should be able to imagine the calling code from here on. While we're at it, let's change the index-based arithmetic to pointers. We can pass the sequence in to the function as an argument; for now, we may as well say that the sequence is a vector<\/a><\/code>, because vector<\/code> is always the right default choice! Our updated function:<\/p>\n\r\n\/\/ version 1: a function that takes a vector\r\nint min_unused(std::vector& v)\r\n{\r\n int* first = &v[0];\r\n int* last = first + v.size();\r\n int unused = 0;\r\n while (first != last) {\r\n int m = unused + (last - first + 1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (int i) { return i < m; });\r\n if (p - first == m - unused) {\r\n unused = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return unused;\r\n}\r\n<\/pre>\nThis is already looking a little clearer. Using pointers removes some of the syntactic noise and allows us to see what's going on better. But, as you may already have thought, once we have vector<\/code>s, the next logical step is to consider using iterators. Let's make that change now so that we can run the algorithm on a subrange within any vector<\/code>.<\/p>\n\r\n\/\/ version 2: use iterators, like a real algorithm\r\ntemplate \r\ninline int min_unused(It first, It last)\r\n{\r\n int unused = 0;\r\n while (first != last) {\r\n int m = unused + (last - first + 1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (int i) { return i < m; });\r\n if (p - first == m - unused) {\r\n unused = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return unused;\r\n}\r\n<\/pre>\nNow instead of using the vector<\/code> directly, now we can pass in begin()<\/code> and end()<\/code>, or any other valid range-delimiting pair of iterators. Note also that because min_unused<\/code> is now a function template, we added inline<\/code> on line 3, meaning that we can put it in a header without causing link errors when it's instantiated the same way in multiple translation units.<\/p>\nThis is a good start, but we can make it more generic yet! At the moment it's still only working on sequences of int<\/code>s, so let's fix that.<\/p>\n\r\n\/\/ version 3: infer the value_type\r\ntemplate \r\ninline typename std::iterator_traits::value_type min_unused(It first, It last)\r\n{\r\n using T = typename std::iterator_traits::value_type;\r\n T unused{};\r\n while (first != last) {\r\n T m = unused + (last - first + 1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (const T& i) { return i < m; });\r\n if (p - first == m - unused) {\r\n unused = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return unused;\r\n}\r\n<\/pre>\nHere we're using iterator_traits<\/a><\/code> to discover the value_type<\/code> of the iterators passed in. This works with anything that satisfies the Iterator concept<\/a>. Consequently we've also now removed the int<\/code>s that were scattered through the code and instead are using T<\/code>s. Note that we are value-initializing<\/a> the T<\/code> on line 6, which will properly zero-initialize integral types.<\/p>\nSince we aren't actually calculating the initial value of unused<\/code>, we need not assume it to be zero; we could let the caller pass it in, and default the argument for convenience. In order to do that, we'll pull out T<\/code> into a defaulted template argument.<\/p>\n\r\n\/\/ version 4: let the user supply the initial minimum\r\ntemplate ::value_type>\r\ninline T min_unused(It first, It last, T init = T{})\r\n{\r\n while (first != last) {\r\n T m = init + (last - first + 1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (const T& i) { return i < m; });\r\n if (p - first == m - init) {\r\n init = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return init;\r\n}\r\n<\/pre>\nA caller-provided minimum might be quite handy - it's common for zero to be a reserved value, or to have a non-zero starting point for values.<\/p>\n
Iterators again<\/strong><\/p>\nAt this point, min_unused<\/code> is starting to look more like a real STL algorithm, at least superficially, but it's not quite there yet. Lines 7 and 10 are doing plain arithmetic, which assumes that the iterators passed in support that. A fundamental concept in the STL is the idea of iterator categories<\/a>: concepts which define operations available on different kinds of iterators. Not all iterators support random access, and any time we are writing a generic algorithm, we had better use the appropriate functions to manipulate iterators rather than assuming valid operations:<\/p>\n\r\n\/\/ version 5: handle iterator arithmetic generically\r\ntemplate ::value_type>\r\ninline T min_unused(It first, It last, T init = T{})\r\n{\r\n while (first != last) {\r\n T m = init + (std::distance(first, last)+1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (const T& i) { return i < m; });\r\n if (std::distance(first, p) == m - init) {\r\n init = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return init;\r\n}\r\n<\/pre>\nIn the code above, the arithmetic on lines 7 and 10 has been replaced with calls to distance<\/a>. This is a key change! Now we are no longer limited to random access iterators like those of vector<\/code> or just plain pointers. Our algorithm now works on all kinds of iterators, but which ones exactly? It behooves us to define exactly what we require of these iterators being used as our arguments. Until C++ has Concepts, we can't enforce this, but we can<\/em> document it, typically by calling the template argument something more descriptive than 'It<\/code>'. Looking at the references for distance<\/code><\/a> and partition<\/code><\/a>, we find that a forward iterator<\/a> is required.<\/p>\nFor many algorithms in the STL, there are more efficient versions available for stronger iterator categories. A good example is partition<\/a><\/code> itself: with just a forward iterator, it may do N swaps, but with a bidirectional iterator, it need only perform, at most, N\/2 swaps. Wherever we want to use different algorithms for different iterator categories, overloading with tag dispatch is a common technique; the STL provides iterator tag types<\/a> for use as arguments to these overloads.<\/p>\nBut with min_unused<\/code>, we don't have any differences in the top level algorithm that would give us greater efficiency based on iterator category. Both distance<\/code> and partition<\/code> do that work themselves.<\/p>\n\r\n\/\/ version 6: document the relaxed iterator category\r\ntemplate ::value_type>\r\ninline T min_unused(ForwardIt first, ForwardIt last, T init = T{})\r\n{\r\n while (first != last) {\r\n T m = init + (std::distance(first, last)+1)\/2;\r\n auto p = std::partition(first, last,\r\n [&] (const T& i) { return i < m; });\r\n if (std::distance(first, p) == m - init) {\r\n init = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return init;\r\n}\r\n<\/pre>\nStrength reduction<\/strong><\/p>\nNow is also a good time to perform some manual strength reduction on our code, making sure that each operation used is the weakest option to do the job. This doesn't really apply to any operation instances in min_unused<\/code>, but in practical terms it typically means avoiding postfix increment and decrement. If the algorithm implements more than trivial mathematics it may also require quite a bit of decomposition to discover all potential efficiencies and opportunities to eliminate operations. For more examples, I recommend watching any and all of Alex Stepanov's excellent series of video lectures<\/a>.<\/p>\nWe do have one operation in this algorithm that stands out: on line 7 there is a divide by 2. Twenty years ago, I might have converted this to a shift, but in my opinion the divide is clearer to read, and these days there is no competitive compiler in the world that won't do this trivial strength reduction. According to my experiments with the Compiler Explorer<\/a>, MSVC and GCC do it even without optimization.<\/p>\nSTL-ready?<\/strong><\/p>\nSo there we have it. Our algorithm is looking pretty good now by my reckoning - appropriately generic and, overall, a good addition to my toolkit.<\/p>\n
Remaining are just a couple of final considerations. The first is ranges: the Ranges TS<\/a> will change the STL massively, providing for new algorithms and changes to existing ones. A specific consequence of ranges is that begin and end iterators need not be the same type<\/a> any more; how that may affect this algorithm I leave as an exercise to the reader.<\/p>\nEven more generic?<\/strong><\/p>\nThe other consideration takes us further still down the path of making our algorithm as generic as possible. A useful technique for discovering the constraints on types is to print out the code in question and use markers to highlight variables that interact with each other in the same colour. This can reveal which variables interact as well as which ones are entirely disjoint in usage - a big help in determining how they should be made into template parameters. In general, examining how variables interact can be a fruitful exercise.<\/p>\n
Thinking about how the variables are used in our case, we see (on line 7) that we need the ability to add the result of distance<\/code> to T<\/code>, and (on line 10) that the difference between T<\/code>s is comparable to the result of distance<\/code>. We are used to thinking about addition and subtraction on integers, where they are closed operations (i.e. adding two integers or subtracting two integers gives you another integer), but there is another possibility. And in fact, there is already a good example of it in the STL.<\/p>\nArithmetic the chrono<\/code> way<\/strong><\/p>\nIt is possible for the type produced by subtraction on T<\/code>s to be something other than T<\/code>. This is what happens with chrono<\/code>, with time_point<\/code><\/a> and duration<\/code><\/a>. Subtracting two time_point<\/code>s yields a duration<\/code>. It is meaningless - and, therefore, illegal - to add two time_point<\/code>s, but duration<\/code>s may be added both to themselves and to time_point<\/code>s.<\/p>\nIn mathematical language, chrono<\/code> models a one-dimensional affine space. (Thanks to Ga\u00c5\u00a1per A\u00c5\u00beman for that particular insight!)<\/p>\nThis is also the case with min_unused<\/code>: T<\/code> is our time_point<\/code> equivalent, and the result of distance<\/code> is our duration<\/code> equivalent, suggesting that we can pull out the difference type as a template parameter:<\/p>\n\r\ntemplate ::value_type,\r\n typename DiffT = typename std::iterator_traits::difference_type>\r\ninline T min_unused(ForwardIt first, ForwardIt last, T init = T{})\r\n{\r\n while (first != last) {\r\n T m = init + DiffT{(std::distance(first, last)+1)\/2};\r\n auto p = std::partition(first, last,\r\n [&] (const T& i) { return i < m; });\r\n if (DiffT{std::distance(first, p)} == m - init) {\r\n init = m;\r\n first = p;\r\n } else {\r\n last = p;\r\n }\r\n }\r\n return init;\r\n}\r\n<\/pre>\nThe advantage here is that we can now use min_unused<\/code> to deal with any code that has different value and difference types, like chrono<\/code>:<\/p>\n\r\n\/\/ a vector of time_points, 1s apart\r\nconstexpr auto VECTOR_SIZE = 10;\r\nstd::vector v;\r\nauto start_time = std::chrono::system_clock::time_point{};\r\nstd::generate_n(std::back_inserter(v), VECTOR_SIZE,\r\n [&] () {\r\n auto t = start_time;\r\n start_time += 1s;\r\n return t;\r\n });\r\nstd::shuffle(v.begin(), v.end(), gen);\r\nv.resize(3*VECTOR_SIZE\/4);\r\n\r\nfor (auto i : v)\r\n std::cout\r\n << std::chrono::duration_cast(i.time_since_epoch()).count()\r\n << '\\n';\r\n\r\n\/\/ we can now find the minimum time_point not present\r\nauto u = min_unused<\r\n decltype(v.begin()), decltype(start_time), std::chrono::seconds>(\r\n v.begin(), v.end());\r\n\r\ncout << \"Min unused: \"\r\n << std::chrono::duration_cast(u.time_since_epoch()).count()\r\n << '\\n';\r\n<\/pre>\n