4
\$\begingroup\$

Any improvements that I can make with this code? Also, is there another way to convert a vector to a string variable without using a for ranged-based loop? From the posts I've seen for converting, I only saw printing the vector instead of returning a string.

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iterator>

using namespace std;

std::string AlphabetSoup(string str) {
std::vector<char>letters;

 istringstream iss(str);

 copy(istream_iterator<char>(iss),
        istream_iterator<char>(),
        back_inserter(letters));

 std::sort(letters.begin(),letters.end());

 //Regrouping the characters into a string
 std::string orderedString;
 for(auto element : letters)
 {
     orderedString += element;
 }

 return orderedString;
}
\$\endgroup\$
7
\$\begingroup\$

Don't use using namespace std

You don't need a stringstream or an istringstream or a vector for this. std::sort can be performed on a string directly. An std::string_view can be used to avoid copying (more on this later)


There seems to be 3 options how to make this work best. If you don't care about chewing up your original string you can perform the operations on it directly without ever copying anything. Here you will pass by reference:

std::string& AlphabetSoup(std::string& str) {
   std::sort(str.begin(), str.end());
   str.erase(std::remove(str.begin(), str.end(), ' '), str.end());

 return str; // or omit this and change the return value to void
}

You can also pass by value which will copy your string and leave the original intact:

std::string AlphabetSoup(std::string str) {
   std::sort(str.begin(), str.end());
   str.erase(std::remove(str.begin(), str.end(), ' '), str.end());

 return str;
}

Or you can pass in as a std::string_view which will not copy.

std::string AlphabetSoup(std::string_view str) {
   std::string s(str);
   std::sort(s.begin(), s.end());
   s.erase(std::remove(s.begin(), s.end(), ' '), s.end());
   return s;
}

The method I used to remove the spaces is known as the erase-remove idiom. The character specified in the remove() function is moved to the end of the range (provided as parameters) where they can be efficiently erased. There are faster iterators on sorted sets that can speed things up as @TobySpeight pointed out but I haven't used them. (Namely std::lower_bound and std::upper_bound)


Consider providing test cases and output. This too will help reviewers and make it more likely for you to get solid answers.

\$\endgroup\$
  • 1
    \$\begingroup\$ Your revised code doesn't do the same thing as the original. By using the stringstream and stream iterators, the original strips spaces. Whether that is intentional or not... who knows? \$\endgroup\$ – indi Jul 6 '18 at 3:07
  • \$\begingroup\$ Is it better to make a copy of str or just use the str? \$\endgroup\$ – austingae Jul 6 '18 at 5:38
  • 1
    \$\begingroup\$ If you don't want to modify the original string, you can still use something like the second version, but pass str by value (generally a good plan for anything you intend to copy). \$\endgroup\$ – Toby Speight Jul 6 '18 at 8:16
  • 1
    \$\begingroup\$ You might be able to make a more efficient space-removal on the sorted string, using binary search (std::lower_bound() and std::upper_bound()) to find the first and last element to erase. \$\endgroup\$ – Toby Speight Jul 6 '18 at 8:20
  • \$\begingroup\$ @austingae Depends on your use case. If you need the original string for any reason ever again definately don't chew it up. \$\endgroup\$ – bruglesco Jul 6 '18 at 13:21
6
\$\begingroup\$

Well, never use using namespace something_humungeous_and_growing_like_std;, because there might be conflicts, and silent changes of semantics.

Next, avoid shuffling data around. There's no need to create any extra-copies.

Third, first efficiently discard the dross, then refine the raw ore. Refining the dross too is wasted effort.

std::string AlphabetSoup(std::string s) noexcept {
    auto unwanted = [](char c){ return std::isspace((unsigned char)c); };
    s.erase(std::remove_if(s.begin(), s.end(), unwanted), s.end());
    std::sort(s.begin(), s.end());
    return s;
}
\$\endgroup\$
4
\$\begingroup\$

You should first be sure what exactly you mean by the word "character". When used in C++, it means "byte" and has nothing to do with any writing system. And that in turn means that "ä" can be 1 or 2 or 3 "characters” long.

\$\endgroup\$
  • 1
    \$\begingroup\$ Also, decide on exactly what you mean by "alphabetic order" - it's not necessarily code-point order. \$\endgroup\$ – Toby Speight Jul 12 '18 at 8:25
  • 1
    \$\begingroup\$ @TobySpeight All the idiosyncracies of scripts old and new, limitations of (modern) computers, and desire for a single simple uniform way to handle all the mess: That's Unicode, the many-faceted. \$\endgroup\$ – Deduplicator Jul 12 '18 at 14:31
3
\$\begingroup\$

To answer your specific question: there is a simpler method to convert between strings and vectors of characters. Both can be constructed from a pair of iterators:

std::string s{"some string"};
std::vector<char> v(s.begin(), s.end());
std::string s2(v.begin(), v.end());
assert(s == s2);

However, in most cases this conversion is unnecessary, as std::string provides all the functionality of std::vector<char> already (as demonstrated in the other answers).

\$\endgroup\$
0
\$\begingroup\$

There is of course a much faster sorting for char, namely counting sort. This is only O(n) instead of O(n log n):

#include <array>
#include <string>
#include <climits>
#include <vector>

std::string AlphabetSoup(const std::string& text) {
    std::array<std::size_t, UCHAR_MAX> count{};

    for (unsigned char letter : text) {
        ++count[letter];
    }

    std::vector<char> v;
    v.reserve(text.size());

    char letter { 0 };
    for (int cnt : count) {
        v.insert(v.end(), cnt, letter++);
    }
    return {v.begin(), v.end()};
}
\$\endgroup\$
  • \$\begingroup\$ @TobySpeight you are totally right. \$\endgroup\$ – Surt Jul 13 '18 at 14:23
  • \$\begingroup\$ I've taken the liberty of fixing some of the problems with your code - in particular, the uninitialized std::array which caused it to crash for me. Note also that you could have made v a std::string, so no need for vectors. \$\endgroup\$ – Toby Speight Jul 13 '18 at 14:45
  • \$\begingroup\$ Oh, and you could simply use v.append(cnt, letter++) instead of the insert, once you're using std::string there. \$\endgroup\$ – Toby Speight Jul 13 '18 at 14:56
  • \$\begingroup\$ I disagree that you call it a radix sort, radix uses counting (or bucket) sort repeatedly to do its sort.In this case each bucket is a single value and not a range so it is a counting sort in this case. Other than that it nicely converts my concept code to working code, thanks. \$\endgroup\$ – Surt Jul 13 '18 at 22:29

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.