Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Critiques (even pedantic ones) are welcome.

bool unique_chars(std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (auto &c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

EDIT 1:

for (auto &c:s) {         //OLD
for (unsigned char c:s) { //NEW

Reasoning:

  1. char can be either signed or unsigned
  2. if signed then bs[] can be out of bounds
  3. casting to unsigned eliminates issue as negative values will wrap

EDIT 2:

This string is to be made up of characters from the standard ASCII character set, i.e. fitting into a 1 byte char.

EDIT 3:

Renamed function / added test harness with examples. Function parameter changed to const, as string not being modified.

#include <iostream>
#include <bitset>

bool areCharsUnique(const std::string &s) {
    if (s.length()>256) return false;
    std::bitset<256> bs;
    for (unsigned char c:s) {
        if (bs.test(c)) return false;
        bs.set(c);
    }
    return true;
}

int main() {
    std::string s1 = "hi there";
    std::string s2 = "hey man";
    std::cout << areCharsUnique(s1) << std::endl; //0
    std::cout << areCharsUnique(s2) << std::endl; //1
   return 0;   
}
share|improve this question
1  
I know. I've already tested it myself. I wanted to see if the OP had done some other tests. –  Jamal Jan 19 at 5:43
2  
I'm curious why the len <= 256 restriction. I'm assuming it's so that your bitset can hold all possibilities (if there's at most 256 characters, there are at most 256 unique characters). You can pretty safely ease this restriction though since std::string is extremely likely to only hold 256 unique characters (since it's std::basic_string<char> and char is almost always 8 bits). –  Corbin Jan 19 at 8:15
2  
@Corbin I think it's an early return: if the string is long then he knows (without spending further time testing it) that it must contain duplicated characters. –  ChrisW Jan 19 at 15:15
2  
@WayneConrad According to cplusplus.com/reference/string/string/length it's O(1) in C++ 11; it inevitably makes things a little slower for small strings. I worried about whether taking a non-const reference to the contents of a non-const string might be expensive; but maybe the compiler+library is smart enough to defer copying a shared/reference-counted string content until/unless there's a write to the content (copy-on-write). –  ChrisW Jan 19 at 15:37
4  
Post rolled back. Please don't make changes to code that can invalidate answers. –  Jamal Jan 21 at 3:25
show 11 more comments

6 Answers

up vote 10 down vote accepted

@Wayne Conrad has made some good points. I just have a few additional ones:

  • I'm not sure about checking against a maximum value, but I'll address it anyway.

    In case you'd like to change the default 256, consider having a template parameter. That way, the value can be changed at just one location. It'll also give more meaning to that value.

    template <std::size_t maxChars = 256>
    bool unique_chars(std::string &s) {
        if (s.length() > maxChars) return false;
        std::bitset<maxChars> bs;
    
        // ...
    }
    
  • To slightly add on to Wayne's point about const, make sure the argument is const& so that no unnecessary copying is done. In addition, declaring the string argument as const will allow it to be passed in while avoiding casting.

  • Consider renaming the function to something like areUniqueChars(). Otherwise, it may sound like it's returning the number of unique chars.

  • In C++, prefer to put unary operators (such as & and *) next to the type:

    std::string& s;
    

    for (auto& c : s) {}
    
share|improve this answer
2  
It might be more accurate to say that declaring the argument const allows const strings to be passed in without nasty casting. –  200_success Jan 21 at 3:58
add comment

One theoretical place that this code might fail is when the string contains multibyte characters.

For example UTF-8 encoding is being used and string passed to the function is "€Abبώиב¥£€¢₡₢₣₤₥₦§₧₨₩₪₫₭₮漢Ä©óíßä" although no character is being repeated, the function will return true.

But handling this case is not straight forward at all, as standard library doesn't provide any way to iterate over actual characters in a string.

share|improve this answer
add comment

Critiques (even pedantic ones) are welcome.

There's no 'functional specification' included with your question, there is just the code. You should include a functional specification, a.k.a. "the problem" to be solved, or "the requirements". Without one, we can see what the code does, but cannot assess whether what it does matches what it is required .

If the (missing) functional specification said, "string", then perhaps it doesn't mean only std::string ... for example, it might also mean std::wstring.

If so then your unique_chars should be a template function (in the same way that std::basic_string is a template class).

If you were working with very wide multi-byte characters (e.g. std::char32_t) you would prefer std::set or std::unordered_set (a hash set) instead of a std::bitset.

share|improve this answer
add comment

That's pretty good. It's short. The early returns communicate intent well, and since the function is short, they don't get lost. Formatting is good, and the variable names, although very short, are common abbreveviations that work well here.

I'd consider making the argument const, since it's not modified by the function.

I've been out of C++ a long time, so I might be missing something here, but I'd consider auto c:s instead of auto &c:s. I can't see a reason to work with a reference when a character is cheap to copy.

share|improve this answer
add comment

Here's a two-line solution using some of the standard algorithms: first sort a copy of the string, then use adjacent_find to determine if any adjacent characters are identical. If there aren't, adjacent_find will return the end() iterator of the string copy, so you simply compare against that

bool areCharsUnique(std::string s) 
{
    std::sort(begin(s), end(s));
    return std::adjacent_find(begin(s), end(s)) == end(s);
}

Note that the function takes its argument by-value, which allows also temporaries as arguments. As pointed out by @ChrisW in the comments, you could also use const& as argument but then you would need an extra copy in order to be able to sort.

It works on strings of any length and for any character set.

Live Example.

share|improve this answer
    
+1 If the argument were a const reference (not a non-const reference), that too would permit temporaries as arguments. The main reason for passing by value (making a copy) is that you mutate the contents of s so you probably should mutate a copy. –  ChrisW Jan 23 at 10:29
    
@ChrisW agreed yes, although I didn't want to go into detail about move semantics and such. The alternative would be to have two overloads: const& and &&. –  TemplateRex Jan 23 at 10:31
    
I don't think the OP has a keyhole problem: it handles strings of greater than 256, it just handles them efficiently by assuming/knowing that they must contain duplicates. You could remove the if (s.length()>256) return false; and it would still behave correctly. –  ChrisW Jan 23 at 10:32
    
@ChrisW tnx for pointing that out. I still wonder about the 256 wide character set that this implies. My solution should work even for wide character sets (obviously it would need another overload for wstring). –  TemplateRex Jan 23 at 10:35
add comment

Good code.

Consider converting a const std::string& parameter into an iterator pair: no reason to not support std::vector<unsigned char>, std::deque-s, etc. You could add a template helper function to have the code run when passed a string s itself, not begin(s), end(s).

On a pedantic note, if you are eager to try fancy things: I would allow non-one-byte inputs, but add an assertions that all the values are in the range [0 .. 256) when unsigned. You could do it using type traits (or by analyzing sizeof(T) at compile time). Basically, if an input is a string/array/container/range of elements of type of sizeof(T) == 1, you need to do nothing else, while if the input is a bunch of int-s, you may want to assert or throw an exception what/if any of the input "characters" is outside this range.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.