We forgot to #include <string>
.
This definition looks like C:
typedef struct
{
⋮
}
Tracking;
In C++, we normally write
struct Tracking
{
⋮
};
I don't think there's anywhere we still need typedef
in modern C++.
We use the wrong type for an index into a string. Strings can be longer than INT_MAX
, so we should use std::size_t
for char_index_in_original_string
.
Although the contract of std::list
says that its iterators remain valid when different elements are removed, it's hard to reason about this in the code, so I would avoid storing iterators if at all possible.
When we first see a particular character, a Tracking
is default-constructed here:
if (map_char_to_tracking[s[i]].char_count_in_string == 1)
This is a bug, because the default initialisation can leave any value in its char_count_in_string
field (we're probably getting away with 0 because the list is allocating nodes in previously unused memory, but we can't rely on that).
Instead we should find()
the appropriate node, or perhaps try_emplace()
a suitable zero value. If we correctly use absence from the list as indicator of "never seen", then we only need a boolean to distinguish "seen once" from "seen multiple times". In fact, we don't even need that - when seen a second time, we can just replace the char_index_in_original_string
with a sentinel value to indicate that.
I don't think we need the unique_chars
set - we have the information in the map, and just need to extract it appropriately.
I would do that by having a view on the map that filters out the "seen twice or more" elements, then we can use std::ranges::min
over the positions.
Unordered map is probably less efficient than plain std::map
here (though we'd need a reasonable-sized benchmark to prove that).
Fixing the above problems, and using shorter names, we get a much simpler function using the same principles:
#include <algorithm>
#include <map>
#include <ranges>
#include <string>
std::size_t first_unique_char_index(const std::string& s)
{
if (s.empty()) {
return std::string::npos;
}
// Map from char to where it's first seen, or to 'npos' if seen more than once.
std::map<char, std::size_t> first_seen;
for (std::size_t i = 0; i < s.size(); ++i) {
auto [iter, is_new] = first_seen.try_emplace(s[i], i);
if (!is_new) {
iter->second = std::string::npos;
}
}
return std::ranges::min(first_seen | std::views::values);
}
The function could be made more general as a template, so that it could work on other string types (such as string literals, or wide strings):
#include <algorithm>
#include <map>
#include <ranges>
#include <string_view>
std::size_t first_unique_char_index(auto const& input)
{
const std::basic_string_view s{input};
if (s.empty()) {
return std::string::npos;
}
// Map from char to where it's first seen, or to 'npos' if seen
// more than once.
using char_type = decltype(s)::value_type;
std::map<char_type, std::size_t> first_seen;
for (std::size_t i = 0; i < s.size(); ++i) {
auto [iter, is_new] = first_seen.try_emplace(s[i], i);
if (!is_new) {
iter->second = std::string::npos;
}
}
return std::ranges::min(first_seen | std::views::values);
}
Take care to observe that extracting single characters for strings doesn't make sense for string types not having a 1-to-1 correspondence with abstract characters - e.g. UTF-8 and UTF-16 strings. Those really ought to be converted to UCS-4.
The tests don't need to flush (with std::endl()
) every line of output - just terminate with plain '\n'
.
The tests would be better if they were self-checking - i.e. the program should return 0 if all tests produce the expected result, and non-zero if any of them fail.
It's good that we have tests for a selection of different cases (empty input, and with 0 or 1 unique characters). We need another test such as "mazaba"
to demonstrate that we return the first unique character in the string, rather than the first or last alphabetically.
I prefer to put the trivial tests (empty string) first in the test set. That helps introduce the reader to the function's constraints as early as possible.