Better container for tracking number of string elements?

Question

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

I'm currently using std::vector but I wonder if there's a better container which is more suitable for my purpose.

My Code :

#include <iostream>
#include <string>
#include <vector>

class Table
{
public:
    void insert(const std::string &name)
    {
        data.push_back(name);
    }
    void remove(const std::string &name)
    {
        auto it = std::find(data.begin(), data.end(), name);
        if (it != data.end())
            data.erase(it);
    }
    /* get the number of occurrences */
    int count(const std::string &name)
    {
        auto num = std::count(data.begin(), data.end(), name);
        return static_cast<int>(num);
    }
private:
    std::vector<std::string> data;
};

int main(int argc, const char * argv[])
{
    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;
    return 0;
}

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?

And would you recommend a different container than std::vector for the class Table?

P.S: Usually, from 50 to 500 strings will be stored to a container in my program.

Answer 1

@Deduplicator already did a worthy review of the code itself, so I'm not going to repeat their points. I'll just add a few things:

• Don't use std::endl, ever. It's almost always wrong, and in the few cases it's not, it's better to use an explicit flush anyway. Just use '\n'.
• Add const and noexcept qualifiers to member functions whenever possible. The const helps with correctness, the noexcept can help considerably with performance. In your case count() can be both const and noexcept, and remove can be noexcept.

Now, considering what your code currently does (which I assume accurately reflects your intentions), you can't get any more efficient than a vector. vector just can't be beat. The creator C++ himself didn't believe this, so he tested it himself (he talks about it in this presentation starting at around 40-45 minutes, but his slides were broken, so check this blog post to see them). He tested up to 100,000 elements, so your ~500 element use case is covered.

Okay, so you're already using the best data structure. Can it still be better?

Yes.

The first trick, which @Deduplicator mentioned, is sorting. When a list of elements is sorted, you can do much faster binary searches on it, rather than the linear searches that find() does. So let's start by using a sorted vector:

class Table
{
public:
    void insert(std::string);
    void remove(std::string_view name) noexcept;

    int count(std::string_view name) const noexcept;

private:
    std::vector<std::string> data;
};

As you can see, the class structure itself doesn't change.

Now the simplest thing to do with insert() is simply to push_back() and then sort(). But... that's a little inefficient given that you know the vector is already sorted except for that one last element.

So what would be better would be to find the place where the new value should be inserted, and then insert it there. For that, there's std::upper_bound(), which does a binary search and returns the first value greater than the given value. So if the list is {"apple", "orange", "orange", "pear"}, searching with "orange" would return an iterator to "pear"; if the list is {"apple", "pear"}, it would still return an iterator to "pear". This is ideal because it works whether the value is already in the list or not, and if it is, it gives us the end of the repetitions, so that an insertion will trigger the smallest amount of shuffling around.

So insert() might look like this:

void Table::insert(std::string name)
{
    auto const p = std::upper_bound(data.begin(), data.end(), name);
    data.insert(p, std::move(name));
}

As for remove() it works just fine as is! (It could be a little better. First you could use a binary search rather than std::find(). Then, rather than removing the first value you find, you could remove the last. This will trigger less moving around of stuff in the vector. For that you could use reverse iterators and std::lower_bound().)

For count() it also works just fine as it is! (Once again, it could be better. You could use std::equal_range() to find the full range of matches quickly, then just subtract the iterators you get as result for the count.)

So this is all cool, and should be a bit faster than what you've got. But can we do even better?

Yes.

Consider: Is there any reason to store multiple copies of a string in the data? If someone adds "apple" 10 times, is it really necessary to add 10 "apple"s? Why not just keep "apple" and a count of 10?

To do this, you need to modify your data structure a little bit. Rather than data being a vector<string>, it should be a vector<tuple<string, int>>. That tuple stores the name and the count.

So the data structure now looks like this:

class Table
{
public:
    void insert(std::string);
    void remove(std::string_view name) noexcept;

    int count(std::string_view name) const noexcept;

private:
    std::vector<std::tuple<std::string, int>> data;
};

Note the only change is to the type of data. The class's interface is unchanged.

So what would insert() look like. Well, the first thing you'd have to do is a lower_bound() search to find the value. Then:

• If the result of lower_bound() is not data.end(), and it points to a value equal to name, just increment the count.
• Otherwise, add a new element to the vector with a count of 1.

That might look like this:

void Table::insert(std::string name)
{
    // A lambda comparator is needed to compare a string to a
    // tuple<string, int>. All it needs to do is get the first
    // element (the string), and do a normal comparison.
    auto const p = std::lower_bound(data.begin(), data.end(), name,
        [](auto&& v, auto&& e) { return v < std::get<0>(e); });

    // If the result is not end, and the string matches...
    if (p != data.end() && std::get<0>(*p) == name))
    {
        // ... update the count.
        ++std::get<1>(*p);
    }
    else
    {
        // ... otherwise, add a new item with a count of 1. Because
        // we used lower_bound, p either points to end or the first
        // element greater than name, so it's the right place to
        // insert before.
        data.emplace(p, std::move(name), 1);
    }
}

remove() also has a special case to consider. First you find the item you want - you can use std::binary_search() for that. Then (assuming you find an item), you decrement its count. Now the special case is if the count is zero, you have to remove the item from the table.

That might look like this:

void Table::remove(std::string_view name) noexcept
{
    auto const p = std::binary_search(data.begin(), data.end(), name,
        [](auto&& v, auto&& e) { return v < std::get<0>(e); });

    if (p != data.end())
    {
        --std::get<1>(*p);
        if (std::get<1>(*p) == 0)
            data.erase(p);
    }
}

And from that, count() should be obvious:

void Table::count(std::string_view name) const noexcept
{
    auto const p = std::binary_search(data.begin(), data.end(), name,
        [](auto&& v, auto&& e) { return v < std::get<0>(e); });

    if (p != data.end())
    {
        return std::get<1>(*p);
    }
    else
    {
        return 0;
    }
}

That will give you the most compact, and almost certainly the fastest results.

The two key factors here are:

• Compact data representation. vector is as compact as it gets, but using a single tuple with a name and a count is also much more compact that storing a name multiple times.
• Sorting. Sorted data is predictable, which means you can optimize accessing it with tools like binary_search() and lower_bound() and the other binary search algorithms.

Put together, that will match the observable behaviour of your code, but should be many times faster.

Answer 2

Of course there is lots to improve:

1. Always ask the compiler. A reasonably-high warning-level helps..

2. You need to #include <algorithm> for std::find().

3. Don't name a function-argument if you don't use it. In the case of main(), you could even leave them off. And there you may also omit return 0; while we are at it.

4. Avoid allocation, it's expensive. Every time you accept a std::string const&, you should re-asses your options:

   • Do you always store it somewhere? Accept a std::string instead.
   • Do you only inspect it, and don't depend on the 0-terminator? std::string_view excels there.
   • Do you only inspect it, but need the 0-terminator? Sorry, there's no standard view for you yet, you have to make do.
   • Do you sometimes store it somewhere? Maybe combine the two above.

   Of course, using universal references and perfect forwarding is also an interesting idea.

5. Use the right data-structure.

   • If equal objects are just copies, use a std::map, std::unordered_map, or something like that.
   • Otherwise, consider a std::multiset, std::unordered_multiset, or the like.
   • And finally, it might pay to keep the array ordered, or explicitly order it before removals / queries. It depends on the use-patterns.