Return to Revisions

I see some things that may help you improve your program.

Provide a complete program

Part of the interface of a function is the associated list of required #includes which these functions are missing. Also, although it wasn't strictly necessary here, it often helps reviewers to include a sample main() that shows how to call the function(s).

Be careful with signed and unsigned

Several places in the code compares an int i to a std::string length(), but std::string::size_type can be unsigned and int is signed. Instead, declare both variables as std::string::size_type types. Better still, see the next suggestion.

Use "range for" and simplify your code

Instead of indexing through a string, iterators are often faster. Using a "range for" can both simplify and speed up your code.

Try to reserve space where known

If a std::unordered_map runs out of space, it must reallocate and rebuild which slows things down. That is probably not happening here, but I'd be inclined to write charCounter.reserve(26); to make sure we have at least enough for 26 letters. Different locales might have greater number of letters but few locales have fewer and reserving a little extra won't hurt. Either way, it demonstrates to the reviewer that you've considered this factor.

Prefer direct increment and decrement

The assembly languages of most processors include increment and decrement instructions which are often faster than the associated add instructions. For that reason, as well as for clarity, I'd omit the use of the lambda and simply rewrite the functions as inline code.

Consider additional early bailout

The code for isAnagram2 already has an early bailout, but it's unlikely to be useful:

if (s1.length() == 0 && s2.length() == 0)
        return true;

The reason is that the loops below will simply collapse and the function will not save much, if any, time. Within isAnagram2 the comment indicates that you've thought of the instance that the second string might contain a new character, but it uses a rather ungainly way of testing for it, invoking find for every letter.

Minimize processing per letter

Since your routine is going to process every letter, but only check for empty() once at the end, I'd omit the charCounter.erase(c) for each letter. It's better to minimize processing in tight loops, often for both clarity and speed.

If it's simpler, it's probably also faster

Here's the rewrite that incorporates most of the above:

bool isAnagram3(const std::string& s1, const std::string& s2)
{
    std::unordered_map<char, int> charCounter;
    charCounter.reserve(26);
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
        }
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
        }
    }
    return std::all_of(charCounter.begin(), charCounter.end(), [](auto &p){
        return p.second == 0; 
    });
}

Test your code

If the goal here was speed, it's good to test for that by timing the various proposed algorithms. On my machine (a Linux box with i7 processor using gcc 12.1.1 with -O2 optimizations) and a sample file that I created with most lines around 950 characters, your two versions both took around the same time, with the second version averaging slightly longer (by < 1%). By contrast, the routine above ran about 4 times as fast (averaged 26% of the time of your isAnagram1()). This is going to be machine, memory, compiler and data dependent, so testing in a wide variety of those factors would likely be helpful for production code.

Your questions

As mentioned above, my testing indicates that your second version is actually slightly slower on the strings I used. YMMV.

As for cache, it's important but not perhaps in the way you mention. The most frequently used data structure is the unordered_map which is probably small enough to fit in the cache. The size of the strings is not likely to make much difference, so I see no advantage to processing both simultaneously.

Further speed might be obtained by parallelizing the algorithm, which is not too difficult, or by using a simple std::array instead of a std::map if your input is solely ASCII text (that is, not a large Unicode alphabet). Indeed, a quick check using std::array<int, 256> for charCounter showed a 2x speed improvement over the routine shown above.

Updated alternative version

As mentioned above, using std::array<int, 256> is one way to improve the speed of the code considerably. This also incorporates AJNeufeld's suggestion in a comment about using an overall counter to further simplify. It also processes the shortest string first, which should help. With the strings I have been using to test, this code is around 10x faster than the original two versions.

bool isAnagram4(const std::string& a, const std::string& b)
{
    auto s1{a.size() < b.size() ? a : b};
    auto s2{a.size() < b.size() ? b : a};
    int count{0};
    std::array<int, 256> charCounter{};
    for (auto c : s1) {
        if (isalpha(c)) {
            ++charCounter[std::tolower(c)];
            ++count;
        }
    }
    if (count > s2.length()) {
        return false;
    }
    for (auto c : s2) {
        if (isalpha(c)) {
            if (--charCounter[std::tolower(c)] < 0)
                return false;
            --count;
        }
    }
    return count == 0;
}