3
\$\begingroup\$

I've started learning programming and as matter of practice I've decided to make a program that will output all possible string combinations and put them in a file.
I've manged to do that and it works perfectly fine. Then I added the option to generate words of different length, so the output looks something like this for words between 2 and 4 characters:

aa
ab
ac
ad
....
zzzz

Now I'm wondering what I can improve and what are different approaches to this problem? For learning purposes I'm trying to do this without using any library facilities, not even the standard library. Looking forward to code review and tips.

#include <fstream>

void gen(std::ofstream& f_out, char* word, int pos=0)
{
    if(!word[pos]) return;
    int length=0;
    for(int i=0; word[++i]; length++);
    while(word[pos]<='z') {
        gen(f_out, word, pos+1);
        if(pos==length) f_out << word << std::endl;
        word[pos]++;
    }
    word[pos]='a';
}


int main()
{
    std::ofstream f_out;
    f_out.open("gen.txt");

    char* word;
    int min=2, max=4;
    for(int i=min; i<=max; i++) {
        char* buffor = new char[i+1];
        for(int x=0; x<i; buffor[x]='a',  x++);
        buffor[i]='\0';
        word=buffor;
        gen(f_out, word);
        delete [] word;
    }

    f_out.close();
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ When you say you are trying to do this without an "external library", does that include the standard library? \$\endgroup\$ – indi Jun 17 '18 at 6:56
  • \$\begingroup\$ @indi Yes, kind of. Someone edited my post and replaced what I originaly wrote. What I meant is that I only want to use basics, no <algorithm>, <math>, <array> or <vector> etc. Just one library for output and thats it. \$\endgroup\$ – sptls Jun 17 '18 at 12:38
  • \$\begingroup\$ Yes, "without an external library" is misleading, because the standard library is not "external". I will edit the question again to clarify that (if I can), and then answer. \$\endgroup\$ – indi Jun 17 '18 at 21:41
3
\$\begingroup\$

Let's start with the core premise of what you're trying to do, which is program in C++ without the standard library for "learning purposes". The problem with this is that you're not learning much useful, really. It's a lot like if you were trying to learn to drive a car by manually doing the timing of the crankshaft and spark plugs... a neat trick, sure, but not one that's ever going to be of any practical use when actually driving a car.

Put another way, you can "learn" C++ by re-implementing std::strlen() (poorly)... but your time would be better spent learning to use the actual std::strlen() and all the other wonderful tools in the standard library, for two reasons:

  • Because any actual, non-trivial program you ever write will have to use those tools, so you might as well learn them.
  • Because you will learn more about being an actual good C++ programmer by observing how things are done in the standard library... which is a fantastically well-designed library (mostly), designed by the best C++ programmers in the world.

It's also worth noting that you are using the standard library. There is no such thing as "bare bones" in C or C++ - a truly "bare bones" C or C++ program would do literally nothing useful, and be optimized right down to an empty main() function. I'm not even talking about the use of std::ofstream (although that does make the point). I'm talking about all the hidden stuff you're using. Like, when you use new, you're using the global operator new in header <new>. You're also pulling in whatever new handler has been installed by the runtime, plus the exceptions library by virtue of std::bad_alloc, and more. And all that isn't even to mention all the stuff in the runtime that gets initialized before main().

What I'm saying is that "bare bones" C++ is a fantasy. There's no such thing. C++ (like C, and like everything else) needs a runtime - whether you use the standard one or write one yourself (such as for a very limited embedded system). You are using the standard library. You just don't realize it.

So trying to learn C++ without using the standard library is:

  • not teaching you how to actually write C++
  • not helping familiarize you with the tools that would actually be useful in writing real C++ programs; and
  • misleading you into thinking you're doing everything on your own like a bad-ass hacker, when in reality the standard library is secretly holding your hand the entire time.

But alright, you've chosen to do this without visibly using any standard library components, so let's do it.

void gen(std::ofstream& f_out, char* word, int pos=0)

This isn't really part of the meat of what you're doing, but it is part of real C++ programming. Taking any specific stream type (like ofstream) by reference is almost never the right thing to do. What you want to take here is std::ostream&. That allows this function to work with file streams, but also std::cout, string streams, network streams, and anything else.

int length=0;
for(int i=0; word[++i]; length++);

These two lines are std::strlen(). They really should be separated out into its own function. One function; one job. Right now gen() not only generates the next word, it also checks the length of the word - that's at least two jobs. Checking the word length is something useful on its own, so it should be separated into its own function.

However....

There is a questionable design decision here to have the generating function check the string length each time its called. There are two issues with that:

  1. it requires the word to be null-terminated; and
  2. whoever calls the function already knows how long the word is, so the function is just redoing work unnecessarily.

In modern C++ it is increasingly preferred to pass array data along with its size in some way - either as a pair of pointers, or a pointer and a size. This is exactly why std::string_view was added to C++17, and why std::span is coming in C++20.

If gen() took a pointer and a size, then the first few lines of the function could be:

void gen(std::ofstream& f_out, char* const word, int const length, int pos = 0)
{
    if(pos == length) return;
    while(word[pos]<='z') {
        // ...

That avoids the need to check the length and allows you to take non-null-terminated strings. It make the function faster and more flexible to use.

if(pos==length) f_out << word << std::endl;

Never use std::endl. It is basically always wrong. In this case, it should be:

if(pos==length) f_out << word << '\n';

But if you've refactored the function to take a pointer and a size (and thus, non-null-terminated strings), you would have to use:

if(pos==length) f_out.write(word, length) << '\n';

or:

if(pos==length) f_out.write(word, length).put('\n');

Down to main().

You never confirm that the file actually opened. You can either test is_open(), the fail bit, or you can set stream exceptions before trying to open it.

char* word;
int min=2, max=4;
  1. Don't declare variables until they're needed. word is not needed until 5 lines later... and technically not even then.
  2. Don't declare multiple variables on a single line. That causes all kinds of headaches with syntactic quirks, and makes it harder to see where variables come from.

I would also recommend that min and max be constexpr. You should also assert that max >= min, for safety.

If we remove word (because it's unnecessary), your main loop looks like this:

for(int i=min; i<=max; i++) {
    char* buffor = new char[i+1];
    for(int x=0; x<i; buffor[x]='a',  x++);
    buffor[i]='\0';
    gen(f_out, buffor);
    delete [] buffor;
}

If you refactor gen() to take a pointer and length, rather than just an implicitly null-terminated pointer, this simplifies to:

for(int i=min; i<=max; i++) {
    char* buffor = new char[i];
    for(int x=0; x<i; buffor[x]='a',  x++);
    gen(f_out, buffor, i);
    delete [] buffor;
}

The inner for loop is just std::fill_n() or std::memset(). It should be moved into its own function for clarity.

But there's a bigger issue here, and that's exception safety. If any exceptions are thrown after the allocation of buffor, the memory will leak.

There are multiple ways to fix this situation. The easiest way is to simply declare everything between the allocation and deallocation to be noexcept. Easy, but not really a good solution because noexcept implies "cannot fail"... and any output can fail.

A really ugly solution is to do this:

for(int i=min; i<=max; i++) {
    char* buffor = new char[i+1];
    try
    {
        for(int x=0; x<i; buffor[x]='a',  x++);
        gen(f_out, buffor, i);
        delete [] buffor;
    }
    catch (...)
    {
        delete [] buffor;
        throw;
    }
}

But the best solution is to create a RAII class for your buffer. Something like:

class buffer
{
public:
    explicit buffer(int size) :
        ptr_{new char[size]}
        size_{size}
    {}

    ~buffer()
    {
        if (ptr_)
            delete[] ptr_;
    }

    // Move ops are handy:
    buffer(buffer&& other) noexcept :
        ptr_{other.ptr_},
        size_{other.size_}
    {
        other.ptr_ = nullptr;
        other.size_ = 0;
    }

    buffer& operator=(buffer&& other) noexcept
    {
        // no std::swap, so we have to do this dance:

        auto const temp_ptr = ptr_;
        ptr_= other.ptr_;
        other.ptr_ = temp_ptr;

        auto const temp_size = size_;
        size_ = other.size_;
        other.size_ = temp_size

        return *this;
    }

    // Observers:
    auto pointer() const noexcept { return ptr_; }
    auto size() const noexcept { return size_; }

    // No copying.
    buffer(buffer const&) = delete;
    buffer& operator=(buffer const&) = delete;

private:
    char* ptr_ = nullptr;
    int size_ = 0;
};

That simplifies your main loop to:

for(int i=min; i<=max; i++) {
    auto buffor = buffer{i};
    fill_n(buffor.pointer(), i, 'a'); // for(int x=0; x<i; buffor.pointer()[x]='a',  x++);
    gen(f_out, buffor.pointer(), i);
}

and at the same time, gives you proper exception safety.

But here's an interesting observation. There is no point in allocating a buffer for each size between min and max. Why not just allocate a single buffer of max size, and reuse it?

auto buffor = buffer{max};
for(int i=min; i<=max; i++) {
    fill_n(buffor.pointer(), i, 'a');
    gen(f_out, buffor.pointer(), i);
}

That spares you the cost of deallocating and reallocating the buffer multiple times.

f_out.close();
return 0;

Both of these lines are unnecessary.

There are also a few more suggestions I'd make from a design and usability perspective.

The way your code is written, before someone can use gen() they have to prepare the buffer just right. That just makes gen() more difficult to use. It would be easier to use if gen() has a simpler interface, something like:

void gen(std::ostream& out, int min, int max);

and then gen() handled setting up the buffers, and called a helper function to do the actual recursion stuff.

Another thing that would be nice is if you could actually specify the set of characters to use in the generated strings. That would also sidestep a very technical bug in your code: you assume that the characters 'a' through 'z' have contiguous code points... that's not always true.

You could do something like this:

namespace detail_ {
namespace {

constexpr char DEFAULT_CHARS[] = "abcdefghijklmnopqrstuvwxyz";
constexpr auto DEFAULT_CHARS_SIZE = sizeof(DEFAULT_CHARS) - 1;

void gen_impl_(std::ostream& out, char* buffer, int size, char const* chars, int chars_size, int pos = 0)
{
    // algorithm here
}

} // anonymous namepsace
} // namespace detail_

void gen(std::ostream& out, int min, int max, char const* chars, int chars_size)
{
    // verify arguments

    // create the buffer
    for (auto i = min; i <= max; ++i) // could also check that the output stream is still good
    {
        // fill the buffer with the first char, then:
        detail_::gen_impl_(out, buffer, i, chars, chars_size);
    }
}

void gen(std::ostream& out, int min, int max)
{
    gen(out, min, max, detail_::DEFAULT_CHARS, detail_::DEFAULT_CHARS_SIZE);
}

Now I can use gen() like this:

// generate "aa" to "zzzz"
gen(out, 2, 4);

// generate hexadecimal numbers from 0 to FFFF
gen(out, 1, 4, "0123456789ABCDEF", 16);

without worrying about setting up buffers properly.

An even more interesting design would be to use callbacks, rather than having writing to a stream be the only option. For example:

// generate "aa" to "zzzz", and write them to f_out
gen(2, 4, [&f_out](auto ptr, auto size) { f_out.write(ptr, size).put('\n'); });

// generate hexadecimal numbers from 0 to FFFF, and make sure they're all
// valid hex numbers.
auto validate_hex_number(char const* ptr, int size)
{
    auto n = 0u;
    auto res = std::from_chars(ptr, ptr + size, n, 16);
    if (!res.ec)
    {
        if (n > 0xFFFFu || res.ptr != ptr + size)
            res.ec = std::make_error_code(std::errc::invalid_argument);
    }

    if (res.ec)
        throw std::system_error{res.ec};
}

gen(1, 4, "0123456789ABCDEF", 16, &validate_hex_number);

You could even design it so that if the callback returns false, you stop generating. This would be handy for brute force password cracking, for example.

Summary

Avoiding the standard library is a pointless exercise, because you'll end up reimplementing chunks of it anyway. Here you've had to implement crappy versions of std::strlen(), std::fill_n() (or std::memset()), and std::vector<char> (or std::string). There's no real gain from reimplmenting those things; your time would have been better served designing the gen() algorithm better - for example, having it take different character sets, or using a callback.

  • Use more functions. One function; one job. If you ever see a nested loop, or if a function is more than ~5 lines of functional code (not counting usings, variable declarations, lines with just braces, comments, and so on), that's a sign that it might be possible to break it into simpler functions.
  • Move work out of loops wherever possible.
  • Don't throw information away - if you know the size of a buffer before calling a function, there's no need to make the function recalculate it.
  • Use RAII. If you're writing C++ and you're not using RAII, you're writing garbage C++.
\$\endgroup\$
2
\$\begingroup\$
  • Code.

    • The char * word is redundant. You may work directly on buffor.
    • The for (....); spelling is discouraged. It is OK to write a bodiless loop, but put a semicolon on a separate line. Ditto for if.

    • No naked loops. Every loop embodies an important algorithm, and hence deserves a name. For example,

      for(int x=0; x<i; buffor[x]='a',  x++)
          ;
      

    begs to be void fill (buffor, i, 'a'); function. Similarly,

        for(int i=0; word[++i]; length++)
            ;
    

    computes a length of word; consider factoring it out into a string_length function.

  • Speaking of the string length, you recompute it on each invocation of gen. It is not necessary: the length of the current word is known to caller, and can be passed down via an extra parameter.

  • Algorithm.

    The problem allows an iterative solution. Treat each string as a number in base-26 alphabet. Start with an N-digit a...a, and keep incrementing it until you reach an M+1-digit number.

\$\endgroup\$

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.