6
\$\begingroup\$

Assuming there is no punctuation. It should remove spaces and bring all characters down to lowercase.

My aim was to write code that directly represented my idea of how I would have done things. This is relevant because there were many ways I could have implemented the cleanString() method and what you see below is not the first way. This is the way that I actually found logical and understand the code for. The other way was to use #include <algorithm> and transform which did not make sense to me despite working.

Here is my solution:

#include <iostream> 
#include <vector> 
#include <locale>

  std::vector <char> stringToVec(std::string inputString) {
    std::vector <char> letters;
    for (int a = 0; a < inputString.size(); a++) {
      letters.push_back(inputString.at(a));
    }
    return letters;
  }

std::string vecToString(std::vector <char> inputVec) {
  std::string reversedString("");
  for (int a = 0; a < inputVec.size(); a++) {
    reversedString.push_back(inputVec.at(a));
  }
  return reversedString;
}

std::string cleanString(std::string inputString) {
  std::locale loc;
  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    inputString[i] = std::tolower(inputString[i], loc);
  }
  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    if (inputString[i] == ' ') {
      inputString.erase(i, 1);
    }
  }
  return inputString;
}

std::string checkPalindrome(std::string reversedString, std::string originalString) {
  if (cleanString(originalString) == cleanString(reversedString)) {
    return "Yes";
  }
  return "No";
}

std::vector <char> reverseVec(std::vector <char> inputVec) {
  std::vector <char> reversedReturn;
  for (int a = inputVec.size() - 1; a >= 0; a--) {
    reversedReturn.push_back(inputVec.at(a));
  }
  return reversedReturn;
}

int main() {
  std::cout << "Enter the string you would like reversed: ";
  std::string userInput("");
  std::getline(std::cin, userInput, '\n');
  std::string reversedInput(vecToString(reverseVec(stringToVec(userInput))));
  std::cout << "Reversed: " << reversedInput << std::endl;
  std::cout << "Palindrome: " << checkPalindrome(reversedInput, userInput) << std::endl;
  return 0;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Check std::vector::reserve. Without reserve, appending element by element to an empty vector will trigger many expensive copy operations to relocate the string in order to make room for the next chars to append, and might even create a memory overhead (up to 200% of the size which actually is needed). Make a habit to create matching allocations whenever you already know the final vector size (here: letters.reserve(inputString.length()) in stringToVec. Of course it's not a memory/speed issue here ;) \$\endgroup\$
    – jvb
    Jul 30 '17 at 8:08
  • \$\begingroup\$ @jvb, I think many is overstatement here, logn resizes don't seem too many. Also, I think wasting 2x amount of chars is not that bad. Allocator probably wastes memory too, so in a big system doing it once at a time probably will be unnoticeable. \$\endgroup\$ Jul 30 '17 at 8:42
  • 1
    \$\begingroup\$ @Incomputable depends on what you are doing. If you have a innocuous vector<T>, T might be a very complicated (nested/large) thing... deep copying might take a lot of time, and potentially doubling the memory footprint without need is bad style. As I wrote it's not a memory/speed issue here, but sure it's something to consider when working with vector. Just saying, whenever you know the final dimension, make using reserve a habit. \$\endgroup\$
    – jvb
    Jul 30 '17 at 9:50
11
\$\begingroup\$

I think you have a classic case of not knowing the standard.
What you are writing is generally already available via either a normal constructor or a standard algorithm. In a few cases I would have just implemented a minor wrapper class that could be used by these facilities.

Lets have a look at a few and see how you could have utilized the standard:

  std::vector <char> stringToVec(std::string inputString) {
    std::vector <char> letters;
    for (int a = 0; a < inputString.size(); a++) {
      letters.push_back(inputString.at(a));
    }
    return letters;
  }

The first thing to point out is that you are passing the parameter by value std::string inputString. This means you are copying the parameter into the function. This can be expensive (especially with strings and vectors). Also you are not mutating them so much easier to pass by const reference.

  std::vector <char> stringToVec(std::string const& inputString) {
                                    //       ^^^^^^^
    std::vector <char> letters;
    for (int a = 0; a < inputString.size(); a++) {
      letters.push_back(inputString.at(a));
    }
    return letters;
  }

This means you can read the original parameter but can not modify it:

The method at() is a bounds checking access operator. If you know that your index is going to be in range then prefer to use operator[]. In the case above you always know that a is going to be in the correct range because you actively check to make sure it is in the correct range a < inputString.size().

  std::vector <char> stringToVec(std::string const& inputString) {
    std::vector <char> letters;
    for (int a = 0; a < inputString.size(); a++) {
      letters.push_back(inputString[a]);  // Don't need to valid range
                                          // When your loop is already
                                          // guaranteeing the range.
    }
    return letters;
  }

Most algorithms we use tend to use iterators, so get used to using them. So I would re-write the above loop in terms of iterators:

  std::vector <char> stringToVec(std::string const& inputString) {
    std::vector <char> letters;
    for (auto loop = std::begin(inputString), loop != std::end(inputString); ++loop) {
      letters.push_back(*loop);
    }
    return letters;
  }

This is such a common pattern that in C++11 they introduced the range based for expression. Basically this is a for() loop that works with an object that can accept std::begin() and std::end() being called on it. It is basically syntactic sugar to make the above loop simpler to write:

  std::vector <char> stringToVec(std::string const& inputString) {
    std::vector <char> letters;
    for (auto letter: inputString) {
      letters.push_back(letter);
    }
    return letters;
  }

But if we look at std::vector<> we see that it also has a constructor that accepts two iterators so you can simply use this to construct the vector:

  std::vector <char> stringToVec(std::string const& inputString) {
    std::vector <char> letters(std::begin(inputString), std::end(inputString));
    return letters;
  }

Or more simply:

  std::vector <char> stringToVec(std::string const& inputString) {
    return std::vector<char>(std::begin(inputString), std::end(inputString));
  }

We can go through the same processes in reverse of the next function vecToString().

std::string vecToString(std::vector<char> const& inputVec) {
  return std::string(std::begin(inputVec), std::end(inputVec));
}

Just as a little style niggle. The seporation of the template type from the class looks strange.

std::vector <char>
         ^^^^^     That space just looks strange.

Lets move to cleaning the string:

std::string cleanString(std::string inputString) {
  std::locale loc;
  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    inputString[i] = std::tolower(inputString[i], loc);
  }
  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    if (inputString[i] == ' ') {
      inputString.erase(i, 1);
    }
  }
  return inputString;
}

Again looking at your loops. I would convert them to using iterators and then range based for. But these are also classic algorithms supported by the standard.

Converting to lower case:

  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    inputString[i] = std::tolower(inputString[i], loc);
  }

This is a standard transform:

 std::transform(std::begin(inputString), std::end(inputString), // Source
                std::begin(inputString),                        // Destination (can be source) as long as it it is already large enough.
                [&loc](unsigned char c){return std::tolower(c, loc)}
               );

Removing a particular character:

  for (std::string::size_type i = 0; i < inputString.length(); i++) {
    if (inputString[i] == ' ') {
      inputString.erase(i, 1);
    }
  }

This is a standard remove/erase

 auto newEnd = std::remove(std::begin(inputString), std::end(inputString), ' ');
 inputString.erase(newEnd, std::end(inputString));

This is so common we usually write it as a single line:

 inputString.erase(std::remove(std::begin(inputString), std::end(inputString), ' '), std::end(inputString));

Commonly referred to as the erase/remove pattern.

Simple tests can sometime be replaced by the trinary operator. BUT be careful if overused or used in bad places this technique can make the code work (so be careful of using this). But in this instance I think it makes the code easier to read:

if (cleanString(originalString) == cleanString(reversedString)) {
  return "Yes";
}
return "No";

You can simplify this to:

return (cleanString(originalString) == cleanString(reversedString))
    ? "Yes"
    : "No";

Reversing a container:

std::vector <char> reverseVec(std::vector <char> inputVec) {
  std::vector <char> reversedReturn;
  for (int a = inputVec.size() - 1; a >= 0; a--) {
    reversedReturn.push_back(inputVec.at(a));
  }
  return reversedReturn;
}

Like above you can improve your code by using iterators.

std::vector <char> reverseVec(std::vector<char> const& inputVec) {
  std::vector <char> reversedReturn;
  for (auto loop = std::rbegin(inputVec), loop != std::rend(inputVec); ++loop) {
    reversedReturn.push_back(*loop);
  }
  return reversedReturn;
}

The rbegin() and rend() provide `reverse iterators. They go in the opposite direction to your standard iterator but are basically the same.

We can expand this (like above to just constructing the container with the iterators).

std::vector <char> reverseVec(std::vector<char> const& inputVec) {
  return std::vector<char>(std::rbegin(inputVec), std::rend(inputVec));
}

There is also standard algorithm std::reverse() that reverse a container in place.

Using the above:

int main()
{
  std::cout << "Enter the string you would like reversed: ";

  std::string userInput;
  std::getline(std::cin, userInput, '\n');

  auto newEnd = std::remove(std::begin(userInput), std::end(userInput), ' ');
  std::erase(newEnd, std::end(userInput));

  std::transform(std::begin(userInput),  std::end(userInput),
                 std::begin(userInput),
                 [](unsigned char* c){std::tolower(c);});


  std::string reversedInput(std::rbegin(userInput), std::rend(userInput));

  std::cout << "Reversed: " << reversedInput << "\n"
            << "Palindrome: "
            << ((userInput == reversedInput) ? "Yes" : "No")
            << "\n";
}
\$\endgroup\$
1
  • \$\begingroup\$ beware negative chars. And match rend() to rbegin(). \$\endgroup\$ Jul 29 '17 at 20:44
7
\$\begingroup\$

I think you're on the right track with this. I can see a few things that could be cleaned up.

Fewer Copies

Looking at this, I see several places where data is copied and probably doesn't need to be. For example, I don't think you need to convert from a std::string to a std::vector as strings handle all the things you do with the vector natively. You can reverse the string directly by using operator[], at(), or iterators. Which brings me to my next point.

Iterators

Generally, in C++ it's better to use iterators when possible. Rather than getting the length of the string, then iterating over it manually, you simply call the object's begin() method (which returns an iterator), compare it to the result of the object's end() method, and increment it as you go. In this case we want to go from back to front, so we use a reverse iterator by calling rbegin() (short for reverse iterator begin) and comparing to rend() (reverse iterator end). So to reverse a string you could do this:

std::string reverseString(const std::string& inputStr)
{
    std::string result;
    for (auto nextChar = inputStr.rbegin(); nextChar < inputStr.rend(); ++nextChar)
    {
        result.append(1, *nextChar); // Could also use opertor+=() here
    }
    
    return result;
}

By doing that, we've collapsed 3 functions into 1!

Iterate Less Often

In your cleanString() function you iterate over the input string twice. You could do it only once by doing something like this:

std::string cleanString(std::string inputString) {
    std::locale loc;
    std::string result;
    
    for (auto nextChar = inputString.begin(); nextChar < inputString.end(); ++nextChar)
    {
        if (not std::isspace(*nextChar))
        {
            result += std::tolower(*nextChar);
        }
    }
    
    return result;
}

Here we build up the result string by adding the values from the input, but only if they aren't spaces.

Use const

In many of your methods you aren't changing the input value. If the argument isn't modified by the function (and isn't passed to another function which will modify it), you should mark it as const. This tells the compiler that it won't change, and it tells other people reading the code that it won't change. That makes it easier for the compiler to perform optimizations, and makes it easier for readers to reason about the code.

Use References Where Appropriate

Since you've marked this with the "beginner" tag, you might not yet have learned about references. Normally when you pass an argument to a function you are making a copy of that value to use within the function. With a reference, you avoid that copy and instead pass information about where the data is so it can be looked up. The code you write inside the function will look the same, but you'll be working on the original value rather than a copy. If you mark it as const then you'll only be able to read it, and not write to it, so it won't get changed, but you can still access it.

For objects like strings that might be very large, avoiding such a copy can make your code more efficient. This probably isn't a big problem with this code, but is good to learn about for the future.

\$\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.