5
\$\begingroup\$

I implemented a function removeDuplicates which takes 1 parameter, a std::string, and returns a std::string without the duplicate characters.

Example I/O might look like this:

removeDuplicates("hello"); //--> "helo"
removeDuplicates("this is easy"); //--> "this eay"

Here is the function:

std::string removeDuplicates(const std::string& str)
{
    //Map for storing character count
    std::map<char, unsigned int> ctable{};

    //Count characters
    std::for_each(str.begin(), str.end(), [&ctable](const auto& value) {
        ++ctable[value];
    });

    std::string newstring = "";
    newstring.resize(str.size());

    //Only copy one character of each type to the new string
    std::copy_if(str.begin(), str.end(), newstring.begin(), [&ctable](const auto& value) {
        return ctable.erase(value) > 0;
    });

    //newstring is bigger than necessary if it has duplicates
    newstring.shrink_to_fit();

    return newstring;
}

Is there a more efficient way to do it?

And what can be improved about the actual code of the function (like variable names/comments, ...).

\$\endgroup\$
7
\$\begingroup\$

Design.

Do you actually need to count all the characters?
I would just record that I had already moved them as I moved them from source to destination.

std::set<char>  moved;
std::copy_if(str.begin(), str.end(), newstring.begin(), [&moved](const auto& value) {
    return moved.insert(value).second;
});

Comments

To be honest I don't find your comments objectionable. Maybe slightly too many but not egregiously so.

Remember do not make your comments describe the code. If I can read the code the I will not need the comments. You should use comments to describe WHY and the code shows HOW.

 // Loop over the array
 for_each(array.begin(), array.end() , 

That's a bad comment as I can read the code and see that it loops over the array I don't need the comment to tell me that. Bad comments are worse than no comments. So best to write Self Documenting Code (this just means your variables and function names should be descriptive so I can read the code and understand what is happening).

Code Review.

Don't need the {} to default construct an empty table.

    std::map<char, unsigned int> ctable{};

Rather than std::for_each I would use the new range based for.

    std::for_each(str.begin(), str.end(), [&ctable](const auto& value) {
        ++ctable[value];
    });

    // try
    for(auto value: str) {
        ++ctable[value];
    }

I would avoid the resize() and prefer reserve() in this situation.

    std::string newstring = "";
    newstring.resize(str.size());

Then when inserting into newstring I would use a back inserter. The reserve() makes sure that you will never need to reallocate the space but you don't make the string too long. Then use the back inserter to increase the size of the string as needed. At the end you don't need to shrink to fit.

    std::copy_if(str.begin(), str.end(), std::back_inserter(newstring), [&ctable](const auto& value) {
        return ctable.erase(value) > 0;
    });

The new version of the standard has added std::begin() and std::end(). Prefer to use these rather than the member functions. This will help when your code is templatized and somebody passes an array rather than a standard container.

std::string removeDuplicates(const std::string& str)
{
    std::set<char> moved;    
    std::string    result;
    result.reserve(str.size());

    //Only copy one character of each type to the new string
    std::copy_if(std::begin(str), std::end(str),
                 std::back_inserter(result),
                 [&moved](const auto& value) {return moved.insert(value).second;}
                );

    return newstring;
}
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

Both map and set are pretty heavy-weighted but since you have such a small amount of possible items to go into the set you can just use an array:

std::array<bool, 256> ctable{ false };

or even a bit set:

std::bitset<256> ctable;

You can both use them like this:

std::string newstring;
newstring.reserve(str.size());

//Only copy one character of each type to the new string
std::copy_if(str.begin(), str.end(), std::back_inserter(newstring),
    [&ctable](const auto& value) {
        std::size_t i = static_cast<unsigned char>(value);
        bool has_occured = ctable[i];
        ctable[i] = true;
        return !has_occured;
    });

Run code on IDEone

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I like your use of an array like container to store the state much more efficient for ASCII. \$\endgroup\$ – Martin York Apr 27 '16 at 14:35
  • \$\begingroup\$ it would be nice if you included erase-remove idiom to your answer \$\endgroup\$ – MORTAL Apr 27 '16 at 18:29
  • \$\begingroup\$ @MORTAL: That's not what OP is asking though and seems trivial at this point. \$\endgroup\$ – David Foerster Apr 27 '16 at 18:52
2
\$\begingroup\$

A great deal here depends on whether you need to maintain the original order of the unique letters. If their order doesn't matter, you can simplify the code quite a bit. If you don't care much about speed, removeDuplicates can be reduced to something like this:

std::string removeDuplicates(std::string const &str) { 
    std::set<char> chars { str.begin(), str.end()};

    return std::string(chars.begin(), chars.end());
}

This, however, will return characters in alphabetical order, rather than their original order in the string. If you care more about speed, and don't mind a little extra code, you can do something like this:

std::string removeDuplicates(std::string str) {
    std::sort(str.begin(), str.end());
    auto pos = std::unique(str.begin(), str.end());
    str.resize(pos - str.begin());
    return str;
}

This doubles the code from 2 lines to 4, but it's still pretty short and simple--and if you care about speed, it'll usually be the fastest way to do this job (typically an order of magnitude faster than anything involving a set or map).

If you want to maintain the original order of the characters, I'd probably write code more like this:

std::string removeDuplicates(std::string const &in) {
    std::unordered_set<char> chars;

    std::string ret;

    std::copy_if(in.begin(), in.end(), 
                 std::back_inserter(ret), 
                 [&](char c) { return chars.insert(c).second; });

    return ret;
}

This mostly uses the return value from [unordered_]set.insert to determine whether we were able to insert the next character into the set, which will succeed only if that character wasn't yet in the set (i.e., we haven't seen it yet in this string). Other than that, we just have a simple copy_if to do the work.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ thank you very much. The thing is, they still need to be in order, so the really fast functions you suggested won't be good for my case. I'll keep that in mind though :) \$\endgroup\$ – Rakete1111 Apr 26 '16 at 16:17
2
\$\begingroup\$

you may consider implementing your own remove_if as in STL in order to remove duplicated from std::string since its algorithm is quite easy. so remove_if would be like this

template <typename Container, typename UnaryPredicate>
Container remove_if(Container&& c, UnaryPredicate pred)
{
    for (auto i = c.cbegin(); i != c.cend(); ++i)
    {
        auto j = std::next(i);
        while (j != c.cend())
        {
            if (pred(*i, *j))
                j = c.erase(j);
            else
                ++j;
        }
    }

    return c;
}

to call it, you need to define the unary predicate. in this case is suitable to call std::equal_to<> like so,

template <typename Container>
Container removeDuplicates(Container&& c)
{
    using Pred = std::equal_to<typename Container::value_type>;
    return ::remove_if(std::forward<Container>(c), Pred());
}
|improve this answer|||||
\$\endgroup\$

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.