Sort string's characters into alphabetic order

Question

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;
}

Answer 1

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.

Answer 2

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;
}

Answer 3

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.

Answer 4

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).

Answer 5

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()};
}