std::set<char> vs std::string for String module

[braw-lee]

Easy extension with use of std::set<char>

Firstly please checkout this function faker::Helper::generateStringWithGuarantee()

This function takes 3 arguments : (GuaranteeMap, a set of char , length of required string) and generates
the required string.

This function can be easily used to extend the guarantee functinality to all other functions of string module

We just need to define the char set for particular functions and faker::Helper::generateStringWithGuarantee()
will handle the rest.

For example: std::set for a octal function will be {'0','1','2','3','4','5','6','7'}

Pass this set to the above function and octal() now supports string guarantees

Issue with time complexity

Now getting random chars from std::set<char> will be costly than getting random chars from a std::string or std::vector<char>
I looked on internet and couldn't find an optimized way to get random item from std::set

Why not use std::string

So faker::Helper::generateStringWithGuarantee() can be implemented with string instead of std::set
but there will be some major problems.

If I keep rejecting invalid chars while fetching random chars from the string it can pose problems in specific cases like the
following one

lets say targetCharacters = "1234567890"

but "123456789" these chars have reached their atmost limit according to GuaranteeMap so probability of getting the only valid char
i.e '0' is 1/10 and if we still need to fetch lets say 10 more chars, the string generation might take 10+ seconds or even more

This will not be a problem with std::set as we erase invalid chars from the targetCharacters set and we will always be fetching
random chars from a set of valid chars.

Conclusion

To implement string generation guarantees, we need to use std::set instead of std::string and tradeoff the time complexity of
generating random char from O(1) to O(n) where n is the size of targetCharacters

Instead of having best case TC O(1) and worst case TC O(random) it is better to have O(n) TC for all cases

[braw-lee]

@cieslarmichal what are your thoughts? And I am interested if anyone has an alternative approach

[cieslarmichal]

Lets consider your example: targetCharacters = "1234567890", we used "123456789" characters due to atmost guarantee, so why cant we delete them from string? so when we iterating lets say we used '1' so delete '1' from "1234567890" etc.

[braw-lee]

std::set will provide faster searching for that function as well

[cieslarmichal]

Ok I have an idea, maybe if there are some guarantees provided we use std::set with characters, and if not just std::string so it would be faster if one doesnt use guarantees?

[braw-lee]

yes statictically these edge cases will be very less

[cieslarmichal]

@braw-lee what do you think about that idea? 💡

[braw-lee]

yes, sounds like a good approach