Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Jamin2112 attempts C++ solutions

  1. Sep 22, 2013 #1
    Okay, in this thread I'm going to attempt some problems and I would appreciate it if the C++ purists could offer feedback. I Googled to get some ideas for problems. Here's a preview:

    • Eliminate whitespace from a string
    • Remove duplicate characters from a string (e.g. "AAA BBB" -> "A B")
    • Return the sum of the two largest integers in an integer array
    • Sum the n largest integers in an array of integers where every integer is between 0 and 9

    I will add more problems as I go along in this thread.
     
  2. jcsd
  3. Sep 22, 2013 #2
    Eliminate whitespace from a string:

    Code (Text):

    void eliminate_whitespace(std::string &str) {
       std::string::iterator it = str.begin();
       while (it != str.end()) {
          if (*it == ' ') {
             str.erase(it);
          } else {
             it++;
          }
       }  
    }
     
     
  4. Sep 22, 2013 #3
    Remove duplicate characters from a string (e.g. "AAA BBB" -> "A B"):

    Code (Text):

    void remove_duplicates(std::string &str) {
      std::string::iterator it = str.begin();
       while (it != str.end()) {
          if (*it == *(it + 1)) {
             str.erase(it);
          } else {
             it++;
          }
       }  
    }
     
     
  5. Sep 22, 2013 #4
    Good so far? Anything stylistically poor?
     
  6. Sep 22, 2013 #5

    Borek

    User Avatar

    Staff: Mentor

    You may want to check what "whitespace" is.
     
  7. Sep 22, 2013 #6
    Ok, so it's spaces, tabs and newlines?
     
  8. Sep 22, 2013 #7

    Borek

    User Avatar

    Staff: Mentor

    Yes. Note that newline can be \n, \r or both, depending on the OS conventions.
     
  9. Sep 22, 2013 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The highlighted code invokes undefined behavior when your iterator points to the last character in the string. A better approach: Look at the preceding character rather than the following one. The first character is not a duplicate (there's nothing before it), so start at str.begin()+1. There's a subtlety here: What if the string is empty? (Hint: Use a different comparison operator in your loop.)
     
  10. Sep 22, 2013 #9
    Revised:

    Code (Text):

    void remove_duplicates(std::string &str) {
      std::string::iterator it = str.begin() + 1;
       while (it != str.end() + 1) { // meaning *it != '\0'
          if (*it == *(it - 1)) {
             str.erase(it);
          } else {
             it++;
          }
       }  
    }
     
     
  11. Sep 22, 2013 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That's still undefined behavior (str.end()+1). Don't use == or !=. Using something else. String iterators are random access iterators. The full panoply of comparison operators is available for your use.
     
  12. Sep 22, 2013 #11
    Are you talking about string::compare?
     
  13. Sep 22, 2013 #12
    Return the sum of the two largest integers in an integer array:

    I think the fastest way, on average, is brute force: Iterate through the array to find the largest, iterate through again to find the second largest, then sum the largest and second largest.

    Another way is to quicksort the array and sum the last two elements. Not as fast, on average.

    Yet another way would be to add the elements of the array to a binary tree and keeps track of the largest and second largest added so far. I think that will be still be slower than brute force, on average.
     
    Last edited: Sep 22, 2013
  14. Sep 22, 2013 #13

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    No. I'm talking about (it != str.end()), or even worse (it != str.end()+1) (which you really do not want to do).
     
  15. Sep 22, 2013 #14

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    One pass through the array will suffice. Keep track of the largest and second largest values. If array is less than or equal to the second largest you don't have to update either. If it's greater than the largest, the (former) largest is the second largest and this new value is now your largest value. Otherwise, it's in between your largest and second largest, so this new value is now the second largest. Sum the two at the end.

    Special cases: What if the array is empty? What if it has only one element? *Always* think of those special cases.
     
  16. Sep 22, 2013 #15
    Take a look at how other comparison operators work with iterators.

    One way or another, do not count on any value or specific behaviour past .end(). It is undefined. Keep in mind that .end() is not at the last element of the sequence, but past-the-end.

    In fact, if it's an empty string, even (str.begin() + 1) is technically undefined since str.begin() == str.end(). Adding one to str.begin() puts the iterator past the .end().

    So how would you prevent that from happening? Like D H said, always think of these corner cases. Make tests for them, even. When is there effectively no work needing to be done on the input string? How do you make sure (str.begin() + 1) is always defined?
     
  17. Sep 22, 2013 #16


    The special cases would have to be runtime errors since the function isn't defined for arrays of length 0 or 1.

    Code (Text):

    int sum_largest_two(int* arr, int n) {
        // some sort of error handling here ...
        int largest(arr[0]), secondLargest(arr[0]);
        for (int i = 1; i < n; i++) {
            if (arr[i] > largest) {
                 secondLargest = largest;
                 largest = arr[i];
            } else if (arr[i] < largest && secondLargest < arr[i]) {
                 secondLargest = arr[i];
            }
        }
        return (largest + secondLargest);
    }
     

    EDIT .... I probably should use vectors since we're doing C++.

    Code (Text):

    int sum_largest_two(const std::vector<int> &vec) {
        // some sort of error handling here ...
        int largest(vec[0]), secondLargest(vec[0]);
        for (std::vector::iterator it = vec.begin() + 1; it != vec.end(); ++it) {
            if (vec[i] > largest) {
                 secondLargest = largest;
                 largest = vec[i];
            } else if (vec[i] < largest && secondLargest < vec[i]) {
                 secondLargest = vec[i];
            }
        }
        return (largest + secondLargest);
    }
     
     
  18. Sep 22, 2013 #17
  19. Sep 22, 2013 #18
    I actually don't know the answer to this. If you create a string of length 0, then I think that *str.begin(), as well as *str.end(), is the sentinel character. So the only thing you can do is add a statement that forces the string to length 1 if it's length 0.
     
  20. Sep 22, 2013 #19
    That quote is from my post, not D H's, but no matter.

    You're going to facepalm when you realize the answer. Ask yourself what needs to be done so the output is correct (no repeated sequential characters) when the input size is 0 or 1.
     
  21. Sep 22, 2013 #20

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    ... and some other characters. The definition of "whitespace" depends what locale you are using (e.g. what language your users are working in).

    If you are using unicode characters, there are a whole raft of different "space" characters with different properties to trip up your code.

    Look at the functions in <cctype>, and use them. As well as giving the right results, they are likely to run faster than "if this && that && something_else && yet_another_test" logic.
     
  22. Sep 22, 2013 #21
    There's also a locale aware one in <locale>: http://www.cplusplus.com/reference/locale/isspace/. For removing whitespace, it works nicely with bind and the erase-remove idiom I already mentioned (using C++11).
     
  23. Sep 22, 2013 #22

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    That's usually a poor way to handle the situation. If your function throws an exception, what is the caller supposed to do with it? Unless he/she bothered to read the function documentation (cue hollow laughter, in real life!) he/she probably won't even expect the exception.

    Usually it's better to make a sensible decision about what the return value "means", in the limiting cases. For example returning 0 for an array of length 0, or the single array value for an array of length 1, might be sensible and useful.

    Similarly for your "duplicate characters" function: there's an obvious definition for what you get after removing duplicate characters from a zero-length string, so that isn't an error situation.
     
  24. Sep 22, 2013 #23

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Which is a whole nother ball of wax. A whole lot of other balls of wax, in fact.

    Speaking of balls of wax, Jamin2112, do you know how to write a proper assignment operator? Do you know when you need to write one? Have you heard of the "rule of three" (which sometimes becomes the "rule of five" in C++11)? By focusing on algorithms, you are missing out on huge chunks of what C++ is all about. Object oriented programming is obviously a big part, but there's also templates and template metaprogramming, and functional programming.

    Back to the original ball of wax, C++11 adds a whole lot of machinery for template metaprogramming and functional programming.
     
  25. Sep 22, 2013 #24
    Well, I've read C++ Primer. I know what templates are. Not sure about template metaprogramming.
     
  26. Sep 22, 2013 #25
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...