3

This problem has kept me from pursuing a project I'm working on because it influences the entire structure of the application. This question has been briefly touched on here, but I feel that it wasn't seen by many people and therefore wasn't very well answered.

I'm working on an application in charge of navigating and manipulating a binary search tree. This application is controlled through a selection menu, with some options leading to submenus. The most hack-ish approach to this problem is something like this:

int main(int argc, char *argv[])
{
    // Create the object using the data in the file at path argv[1].
    BinarySearchTree tree(argv[1]);

    bool exit = false;
    while (!exit) {
        // Print the menu out here with std::cout statements.
        // This always adds several lines that don't do much.

        // Store the users input in a variable here.
        // Coding a way that ensures something valid is input adds
        // many more lines of clutter.

        // If-elseif-else or switch statement here. More complexity with more
        // submenus that look exactly like this here. You get how complex
        // this will get.
    }
}

Anyone who wants to type good code doesn't want their main function to be this long and messy. Breaking it into other functions sitting in my main file doesn't really help much either, it's still messy and not very object-oriented. A possible solution would be to put each menu into their own class like this.

int main(int argc, char *argv[])
{
    BinarySearchTree tree(argv[1]);
    MainMenu main_menu;
    main_menu.run();
}

Definitely the cleanest main method, but not a viable option since my tree object can no longer be accessed from within the MainMenu methods, and I definitely don't want to pass it around endlessly within my class methods since that'd be terrible style. So finally some middle ground I came up with was like this.

int main(int argc, char *argv[])
{
    BinarySearchTree tree(argv[1]);

    MainMenu main_menu();
    bool exit = false;
    while (!exit) {
        unsigned long prompt = main_menu.prompt();

        // The switch statement here. Still a lot of complexity I don't like
        // because this can go on for quite a while depending on how deep my
        // submenus go or how much I need to do for specific commands.
    }
}

Ok, all my sample code is out of the way. I don't like any of them, and I haven't found any truly better solutions on the internet. I'm an undergrad, so I don't have any practical experience in this. Is there some widely accepted best-practice in the industry that I don't know about? How would you approach this personally? Remember, this is being implemented in C++ so I'm trying to be as object-oriented as possible. However, if there's a functional way you know of that works really well that you'd like to share, I'd be open to it.

  • What benefit does it have, in your opinion, to move the code from one function (main) into another one (run)? For that matter, what benefit does using a class have here? The answer to both questions is, of course, "none". Merely moving a code into a class doesn’t make the code OOP. – Konrad Rudolph Nov 9 '14 at 9:40
  • Before you answer your own question, @Konrad, maybe I can explain the situation more. The code above is example code, example code that I don't like. If you had read it, I don't like the run function. And what benefit does using a class have? It doesn't always, but moving it out of main does. Maybe I had tried putting all of my code in main. Maybe it ended up being a function that's a couple hundred lines long, with control flow statements that ended up taking half my page width. Maybe I didn't want to debug that crap later. But right, no benefit. Why do most languages have functions again? – Jared Nov 11 '14 at 19:27
  • My point was (and remains) that moving everything from one function to another does not make sense. And that’s what you’re doing (modulo some unimportant stuff). And it really makes no difference whether it’s in a function called main or a function called run. In particular, having a function “a couple hundred lines long” is simply always bad. Likewise, having a class with only one member function just doesn’t make sense – just use a regular function instead, without the class. – Konrad Rudolph Nov 12 '14 at 9:01
2

First off, there is absolutely nothing about C++ which forces (or even encourages) you to use OOP. This is a common misunderstanding. Other languages lend themselves to OOP much better than C++, and while C++ supports OOP, it supports other paradigms much better.

That said, your problem is classic, and lends itself well to the command pattern. It’s worth noting that this can also be implemented without the use of a subclass hierarchy but let’s stick to the “classical” OOP implementation here.

A command is a subclass of the general command base class:

struct command {
    virtual std::string description() const = 0;
    virtual void run(context&) = 0;
    virtual ~command() = default;
};

using command_ptr = std::unique_ptr<command>;

The context object contains the necessary information to fulfil the command. In your case, this could be the BinarySearchTree. So yes, you do need to pass this around. There’s no clean way around this. In fact, this is not a bad thing: it’s certainly not “terrible style” as you claim – quite the opposite!

Here is a simple command implementing this:

struct open_command : command {
    std::string description() const override {
        return "Open a file";
    }

    void run(context& context) override {
        // TODO implement.
    }
};

Now your menu structure would contain a list of commands and show them in a loop. Simplified:

struct menu {
    menu(context& context, std::vector<command>& commands)
        : context{context}, commands{commands} {}

    void show() {
        for (int i{}; i < commands.length(); ++i)
            show(i, commands[i].description());

        show(0, "Exit");

        int choice{};
        for (;;) {
            choice = input();
            if (choice == 0) return;
            if (choice > 0 and choice <= commands.length())
                break;
        }

        commands[choice - 1].run(context);
        // Don’t leave the menu:
        show();
    }

    // TODO:
    int choice() const;
    void show(int, std::string) const;

private:
    context& context;
    std::vector<command_ptr> commands;
};

Now the interesting thing is this: A submenu would also be a subclass of command, and could wrap the menu class. That way, you can elegantly nest command menus arbitrarily deeply.

Finally, to use this menu, you’d initialise it thusly:

std::vector<command_ptr> cmds {
    make_unique<open_command>(),
    make_unique<save_command>(),
    make_unique<edit_submenu>(
        bst,
        std::vector<command_ptr>{
            make_unique<edit_delete_command>(),
            make_unique<edit_insert_command>(),
            …
        }
    ),
    …
};
menu menu{bst, cmds};
menu.show();

This creates some commands, of which one (edit_submenu) is a submenu, initialises a menu and shows it.

That’s it, in a nutshell. The above code requires C++14 (actually, just C++11 + std::make_unique). It can easily be rewritten to run on C++03 but C++11 is just less painful.

Two tangential remarks:

  1. iostreams are not designed for interactive input and output. Using them to implement such an interactive menu works badly, since they cannot cope well with the peculiarities of user input. Unfortunately there is no good CLI library for C++ that I know of. The de-facto standard for CLI in the Unix world is the GNU readline library but (a) it only has a C API, and (b) its license forbids its use in anything but GNU licensed software.

    There is no really good solution for this. However, most command line applications would eschew an interactive CLI in favour of command line options and commands, so that each invocation of your program would execute one command (or a combination of several), controlled by command line arguments:

    bst add entry my_database.file
    bst add another-entry my_database.file
    bst lookup entry my_database.file > output.file.
    

    This is the conventional workflow of command line applications, and it’s in most regards superior, since it’s trivially scriptable and can be combined with other command line tools.

  2. It is worth noting that, for the case of static menus (i.e. where the number of submenu items doesn’t change at runtime) the Boost.Variant library offers a superior alternative to the above class hierarchy. Each menu would be a boost::variant of the relevant commands. However, the general idea remains the same.

  • and while C++ supports OOP, it supports other paradigms much better. Out of curiosity, what other paradigms other than procedural do you mean? – Doval Nov 12 '14 at 13:41
  • @Doval Algorithm-based programming and the related generic programming. Read the interview with Alexander Stepanov, the inventor of the STL. The interview is quite long; the relevant part discussing OOP and generic programming is mainly in the middle; search for “object oriented” to jump there. – Konrad Rudolph Nov 12 '14 at 14:39
  • I've read that interview before. I'm not sure C++ is suited for that either - templates are a bitch to work with and you can't formally specify the expected interface anywhere. Unless you need to do some serious bit-twiddling, Standard ML/OCaml seem better suited for that. Thanks for clarifying what you meant though. – Doval Nov 12 '14 at 14:49
  • @Doval OCaml notwithstanding, C++ is simply the only actually used too which offers overhead-free abstractions. Yes, it kind of sucks but it also kind of works. Generic programming is used extensively in C++, and you can actually specify the interface if you’re not afraid of a bit of hackery (C++17 will hopefully make this much, much easier). “Templates are a bitch to work with” – right, but they are actually much simpler than they’re often made out to be. Not great, but a-okay. – Konrad Rudolph Nov 12 '14 at 15:57
  • 1
    @Doval I’d argue that until C++11, C++ supported generic programming much, much better than OOP, simply because you cannot do OOP reasonably when you have to worry constantly about your pointers leaking. This has been somewhat alleviated but compared to other mainstream languages C++ simply sucks at OOP. Compared to almost all mainstream languages, C++ is the only one with reasonable generic programming support. – Konrad Rudolph Nov 12 '14 at 16:08
1

If you need some data created somewhere in another class, you have to pass it. That is not bad style, there is nothing "messy" in it, that is just the way how data is to be used in a program. Ideally you pass it only once in the constructor:

 MainMenu main_menu(tree);

If that tree is needed in lots of places inside the class MainMenu, you store just a reference to it in a member variable of MainMenu, for example

 class MainMenu
 {
     BinarySearchTree &m_tree;

     MainMenu(BinarySearchTree &tree)
     : m_tree(tree)
     { 
     }

     void run()
     {
         // do things with m_tree here, maybe pass it to a different sub menu
     }
  }

This avoids the need for "endless passing within your classes methods", as you wrote.

You may consider not to "interweave" the access to you binary tree too much with the menu code. But for telling you if and how it is possible one has to look at the part of the program which actually deals with the tree. So the only guideline I can give you so far is put the actual operations on the tree into functions which are separated from your menu classes (maybe as member functions of your BinarySearchTree, maybe member functions of something like a TreeManipulator class, depends on how those operations look like).

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.