4
\$\begingroup\$

I'm looking for the most simple and efficient way to track the number of string elements in a container.

Previously, I used std::vector but I tried changing the container to std::unordered_map since I hear that it can be easier and more performant for my use.

My Code :

#include <iostream>
#include <string>
#include <unordered_map>

class Table
{
public:
    void insert(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
        {
            data[name] = 1;
            return;
        }
        data[name]++;
    }
    void remove(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
            return;
        if (--data[name] == 0)
            data.erase(it);
    }
    /* get the number of occurrences */
    int count(const std::string &name)
    {
        auto it = data.find(name);
        if (it == data.end())
            return 0;
        return data[name];
    }
private:
    std::unordered_map<std::string, int> data;
};

int main()
{
    Table table;
    table.insert("Apple");
    table.insert("Apple");
    table.insert("Orange");
    table.insert("Orange");
    table.remove("Orange");
    std::cout << "Number of Apples : " << table.count("Apple") << std::endl;
    std::cout << "Number of Oranges : " << table.count("Orange") << std::endl;
    std::cout << "Number of Lemons : " << table.count("Lemon") << std::endl;
}

The Result :

Number of Apples : 2
Number of Oranges : 1
Number of Lemons : 0
Program ended with exit code: 0

Is there a way to improve the class Table so my program can be more efficient than now?

The program seems to work but I used std::unordered_map for the first time so I'm not really sure if my implementation is correctly done.

\$\endgroup\$
7
\$\begingroup\$
void insert(const std::string &name)
{
    auto it = data.find(name);
    if (it == data.end())
    {
        data[name] = 1;
        return;
    }
    data[name]++;
}

If it is available, you should prefer taking std::string_view parameters over std::string const&. You see, every time you do:

table.insert("Orange");
table.remove("Orange");

a string has to be constructed for "Orange". Especially when all you're doing is removing or getting the count, that's very wasteful. std::string_view is very lightweight, and automatically converts from both C-strings and std::string. Even in the case of insert(), because your inserts are conditional, it's worthwhile.

Now your insert() can be simplified quite a bit because when you do data[???] with an unordered_map, and ??? is not in the map, it automatically gets inserted with a default value. For int, the default value is 0.

So all you need is:

void insert(std::string_view name)
{
    ++data[name];
}

remove() works, but it's not very efficient. The problem is that after you find the element and have the iterator... you throw that information away! Then you use data[name] which has to do another search.

Instead, use what you've got. When you have the iterator, use it.

void remove(std::string_view name)
{
    auto const it = data.find(name);
    if (it != data.end())
    {
        if (--it->second == 0)
            data.erase(it);
    }
}

count() has bit of a bug, and it's one the compiler would have informed you about if you'd made the function const.

The bug is that, as with remove(), after finding the element and getting an iterator to it, you throw that information away and use operator[]... but in this case, operator[] is non-const, meaning it might modify the map. That's not something you want happening if you're just getting a count.

Once again, the solution is to simply not throw the iterator away, but to use it:

int count(std::string_view name) const noexcept
{
    auto const it = data.find(name);
    if (it == data.end())
        return 0;
    return it->second;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You forgot to decrement the count in remove. \$\endgroup\$ – hoffmale Jul 29 '18 at 7:44
  • \$\begingroup\$ Thanks! Wouldn't it be simpler to merge 2 ifs inside remove() so it can be like if (it != data.end() && --it->second == 0) data.erase(it); \$\endgroup\$ – Zack Lee Jul 29 '18 at 8:17
  • \$\begingroup\$ the string will be created anyway in ++data[name]; when calling operator[], won't it? \$\endgroup\$ – RiaD Jul 29 '18 at 13:50
  • 1
    \$\begingroup\$ Strange that none of my comments from last night are showing up. They were: 1) Thanks, hoffmale, fixed; and 2) Zack Lee, that's how I would write it, but I was trying to follow your convention of one test per if. And yes, RiaD, the string will be created every time, but it's insert(), so you shouldn't be using it in a hot loop context anyway. \$\endgroup\$ – indi Jul 29 '18 at 15:40
  • \$\begingroup\$ @indi but what's the point of accepting string_view instead then? It'll be slower if somebody has a std::string and the same if it has something else (cstring/string_view etc). And the same applies to count which may be called often. PS: when you use name without at-sign, the person is not get notified \$\endgroup\$ – RiaD Jul 29 '18 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.