5
\$\begingroup\$

Example of a C++ function which removes duplicates from a string:

string remove_duplicates(string subject) 
{
  string no_duplicates(""); 

  for(int i = 0; i < (int) subject.length(); i++) {
    bool found = false;

    for(int j = 0; j < (int) no_duplicates.length(); j++) {
      if (no_duplicates[j] == subject[i]) {
        found = true;
        break;
      }
    }

    if (!found) no_duplicates += subject[i];
  }

  return no_duplicates;
}

I often find myself writing the subroutine inside which loops through and checks if something is found, if it is NOT found, I need to execute some action. Another approach would be to check if j == no_duplicates.length(), but this doesn't seem optimum as well.

Any suggestions on how to optimize this?

\$\endgroup\$

3 Answers 3

2
\$\begingroup\$

If you don't need to modify a parameter always use const and try to take references. For your exact problem try to create a simple boolean function, e.g. which checks if a character is already in the string. This simplifies things a lot and improves the readability.

In your case there is fortunately already a function for checking if a char is present, std::string find. You can easily use it, e.g:

std::string remove_duplicates(const std::string& subject) {
    std::string no_duplicates;

    for(std::string::const_iterator it = subject.begin(); it != subject.end(); ++it) {

        if (no_duplicates.find(*it) == std::string::npos) // char not found
            no_duplicates += *it;

  }

  return no_duplicates;
}
\$\endgroup\$
4
  • \$\begingroup\$ Thanks! This helped a lot. :-) Any specific reason for always using const for references? Passing by address I guess is because it is cheaper, since C++ by default copies the string, which is not required. \$\endgroup\$
    – Sirupsen
    Aug 10, 2012 at 22:34
  • \$\begingroup\$ @Sirupsen you don't use always const for references only if you don't want to modify it. This make sure you don't change it by accident and may also allow additional optimization \$\endgroup\$ Aug 10, 2012 at 22:50
  • \$\begingroup\$ Why are you using const_iterator rather than a normal iterator? \$\endgroup\$
    – Sirupsen
    Aug 12, 2012 at 20:51
  • \$\begingroup\$ @Sirupsen because i don't need to modify subject, see const vs. non-const iterators \$\endgroup\$ Aug 12, 2012 at 21:35
2
\$\begingroup\$

In C++11, avoid loops. In addition to what Loki said, avoiding loops would yield the following concise code:

std::string remove_duplicates(std::string const& subject) {
    std::string result;
    char duplicates[std::numeric_limits<char>::max()] = { };

    std::copy_if(begin(subject), end(subject), std::back_inserter(result),
        [&](char c) { return duplicates[c]++ == 0; });

    return result;
}

This advice is not just an arbitrary preference: avoiding loops removes whole classes of potential errors (especially overflows and off-by-one errors) which are fundamentally impossible to make in the above code.

But like Loki’s, this code assumes unsigned characters. Unfortunately, this is far from given; therefore, instead of relying on an implicit conversion between characters and integers, an explicit conversion would be required.

\$\endgroup\$
2
  • \$\begingroup\$ This is a good tip. Practically all C++ I do is for competitive programming, where off-by-one errors can /not/ happen. \$\endgroup\$
    – Sirupsen
    Aug 12, 2012 at 20:31
  • \$\begingroup\$ Although C++11 is not allowed in most competitions... \$\endgroup\$
    – Sirupsen
    Aug 12, 2012 at 20:39
2
\$\begingroup\$

This is a well know problem:
Open up one of Knuths book (I hope you have the set lying around).

Anyway a string is a set of char.
char only has 256 values (assuming 8 bits). So you set up an array of 256 counters (set to zero). Then you just start counting how many of each letter there is. The first element that exceeds 1 means you have duplicates:

bool checkduplicates(string const& subject) 
{
  char no_duplicates[256] = {0}; // initialize counts to zero.

  for(std::size_t i = 0; i < subject.length(); i++)
  {
      // need the static cast to make sure the character
      // is not signed and thus potentially negative.
      std::size_t index = static_cast<unsigned char>(subject[i])
      ++no_duplicates[index];

      if (no_duplicates[index] > 1)
      {   return true;
          // I know this changes the meaning of your code.
          // I am just using it as an example of optimal check-duplicates.
          // It would be easy to convert to your code to use this technique.
      }
  }

  return false;
}

Code review:

The function is called remove duplicates.
But that is not what it does. Use names that reflect the actual action.

string remove_duplicates(string subject) 

Given that the function actually only checks for duplicates I would return a bool as a result (unless the output here is being used for other purposes) and I would pass the parameter by const reference. This prevents a copy (if the compiler is feeling sloppy) but more importantly is an indication that it will not be modified.

Avoid C style casts in C++ code. There is absolutely no need for them. There are a whole set of new C++ casts that are designed to be much more easily seen.

Avoid C++ style casts as much as possible. They are an indication that you are overriding the compiler because it can not do something you want it to do.

  for(int i = 0; i < (int) subject.length(); i++) {

In this case you are using the wrong type and you are just asking the compiler to stop complaining. But this makes code harder to maintain. What happens if a maintainer change types of some variable will the cast still hold true? The compiler will still keep quite about any errors as you have indicated with a cast that you know what you are doing and have told it to shut up.

Use the correct type (or one the compiler will not complain about).

Also prefer pre-increment. It does not make any difference for POD types. But it can and usually does make a difference for class types (potentially container iterators). By using pre-increment your code will still work optimally when the types are changed (and it required no other code changes to keep the code working optimally).

Why are you marking work to be done in one location:

        found = true;
        break;

Then doing the work in another?

    if (!found) no_duplicates += subject[i];

It would be easier to read to move the work to the point where it is needed.

for(int j = 0; j < (int) no_duplicates.length(); j++) {
  if (no_duplicates[j] == subject[i]) {
    no_duplicates += subject[i];
    break;
  }
}
\$\endgroup\$
10
  • \$\begingroup\$ 1) Why not pass simply by reference? 2) Why the explicit (int) for subject.length()? 3) This doesn't do the same as my own function (although could easily be modified to). \$\endgroup\$
    – Sirupsen
    Aug 11, 2012 at 15:29
  • \$\begingroup\$ 1) Because const& reference is an indication you are not going to modify it allowing the compiler more freedom. \$\endgroup\$ Aug 11, 2012 at 15:46
  • \$\begingroup\$ 2) I am saying don't use (int) \$\endgroup\$ Aug 11, 2012 at 15:46
  • \$\begingroup\$ 3) I am just showing the optimal solution for detecting duplicates. Which can be modified easily and adapted fro removing dupes. \$\endgroup\$ Aug 11, 2012 at 15:47
  • 1
    \$\begingroup\$ “I hope you have the set [of Knuth’s books] lying around” – are you mad? In what Universe is that a reasonable assumption? I do happen to have the set lying around, and although I’ve used them occasionally they are far from an ideal reference, and a particularly poor educational tool. Other algorithms books are easier to approach, reasonably complete, and far cheaper. \$\endgroup\$ Aug 11, 2012 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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