Skip to main content
Mention moving struct definition into function (since it's gone by the time we reach my version)
Source Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

Since this type is used only within the function, it can be defined within that scope, making the global namespace a tiny bit tidier.

Since this type is used only within the function, it can be defined within that scope, making the global namespace a tiny bit tidier.

Source Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

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.