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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Jamin2112 attempts C++ solutions
  1. Online Survey Solution (Replies: 0)

Loading...