6
\$\begingroup\$

I'm writing a program to help with remembering complex bash commands. On invoking the program, it asks for a description of the desired operation, e.g., "increase volume" or "find orphaned packages", and displays the commands matching the input ordered by closest match.

Matching is determined by splitting the command text into a string vector, then the description, and combining these with a list of additional keywords to compare with the input via std::set_intersection. This is currently case sensitive, which I plan to change.

This is my first C++ program so I've probably made plenty of mistakes. A couple things I'm still unclear on: when to pass arguments by reference, when to use const and static, and when to use pointers.

#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

struct Command {
  std::string text;
  std::string description;
  std::vector<std::string> addl_keywords;
};

struct FoundCommand {
  std::vector<std::string>::size_type keywords_found;
  Command command;
  FoundCommand(std::vector<std::string>::size_type keywords_found, Command command)
      : keywords_found {keywords_found}, command {command} {}
  bool operator < (FoundCommand other) {
    return keywords_found > other.keywords_found;
  }
  bool operator > (FoundCommand other) {
    return keywords_found < other.keywords_found;
  }
};

// TODO: make case insensitive
static const Command commands[] {
  {"amixer -Mq set Master 1%-", "decrease volume", {"lower"}},
  {"amixer -Mq set Master 1%+", "increase volume", {"raise"}},
  {"makepkg -sri", "build and install a package using a PKGBUILD file", {"pkgbuild"}},
  {"makepkg -efi", "rebuild and reinstall a package using a PKGBUILD file",
    {"build", "install", "pkgbuild"}},
  {"pacman -Qdt", "list orphaned packages", {"find", "orphan"}},
  {"pacman -Qe", "list explicitly installed packages", {"find", "explicit"}},
  {"pacman -Ql [package]", "list files owned by package", {"find", "own"}},
  {"pacman -Qo [file]", "list packages that own file", {"find", "owned"}}
};

std::vector<std::string> Split(const std::string& s, char delim = ' ') {
  std::stringstream ss {s};
  std::string part;
  std::vector<std::string> parts;
  while (getline(ss, part, delim))
    parts.push_back(part);
  return parts;
}

std::vector<std::string> Union(std::vector<std::string> v1,
                               std::vector<std::string> v2) {
  std::vector<std::string> result;
  result.reserve(v1.size() + v2.size());
  result.insert(result.end(), v1.begin(), v1.end());
  result.insert(result.end(), v2.begin(), v2.end());
  return result;
}

std::vector<std::string> Union(std::vector<std::string> v1,
                               std::vector<std::string> v2,
                               std::vector<std::string> v3) {
  return Union(Union(v1, v2), v3);
}

std::vector<std::string> Intersect(std::vector<std::string>& v1,
                                   std::vector<std::string>& v2) {
  std::sort(v1.begin(), v1.end());
  std::sort(v2.begin(), v2.end());
  std::vector<std::string> result;
  std::set_intersection(v1.begin(), v1.end(),
                        v2.begin(), v2.end(),
                        std::back_inserter(result));
  return result;
}

std::vector<FoundCommand> FindCommands(std::vector<std::string>& input_keywords) {
  std::vector<FoundCommand> results;
  for (Command command : commands) {
    std::vector<std::string> cmd_keywords = Union(Split(command.text),
                                                  Split(command.description),
                                                  command.addl_keywords);
    std::vector<std::string> found_keywords = Intersect(input_keywords, cmd_keywords);
    if (!found_keywords.empty()) {
      results.emplace_back(found_keywords.size(), command);
    }
  }
  return results;
}

int main() {
  std::cout << "Using keywords, describe what you would like to do: ";
  std::string input;
  getline(std::cin, input);
  std::vector<std::string> input_keywords = Split(input);
  std::vector<FoundCommand> results = FindCommands(input_keywords);
  std::sort(results.begin(), results.end());
  for (FoundCommand result : results)
    std::cout << result.command.description << ": " << result.command.text << std::endl;
  return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Why not take advantage of set_union too (instead of your own Union) since you are already using set_intersection as well? \$\endgroup\$ – Juho Nov 15 '15 at 10:28
  • \$\begingroup\$ Good idea! Didn't realize. \$\endgroup\$ – David Kennedy Nov 15 '15 at 16:23
5
\$\begingroup\$

First, let me say that this is not a bad program from somebody who is new to C++. You seem to have successfully avoided many of the common pitfalls, so good job on that! To help you further develop, here are some things that may help you improve your code, starting with answers to your specific questions.

Understand when to use references

The primary difference between a reference and a pointer is that a reference cannot be nullptr. So if the function you're calling couldn't work with a nullptr (or doesn't check for one), as with your Intersect() routine, then it should be a reference as you've correctly done.

Use const where practical

One way to remember how to use const effectively is to think of it this way: try to use const everywhere, and then only omit it where you must. So, for example, your commands structure is never changed and is therefore const as you have correctly done it. However, with some additional changes, you can both make your program more efficient and use const more often. The following suggestions help with that.

Use existing library functions

As @mrm observed, you're using set_intersection already, so why not use set_union as well instead of defining your own Union? Also, in main, we currently have this:

std::string input;
getline(std::cin, input);
std::vector<std::string> input_keywords = Split(input);

However, we don't really need Split in this case. I would do it like this instead:

using namespace std;
vector<string> input_keywords;
copy(istream_iterator<string>(cin), istream_iterator<string>(), 
        back_inserter(input_keywords));

Note, too, that I'm using using namespace std within main() (and therefore limiting it to within that scope) rather than at the top of the file outside main which is a poor practice.

Use objects more effectively

The program requires the list of commands and keywords to operate, but they're constructed in a rather inefficient way. First, there is the Command structure, and then the commands[] simple array, but then to actually use this within FindCommands, each entry is individually converted into an array of words every time the function is called, which is not very efficient. Further, each string vector is then sorted within the call to Intersect and then discarded. That's a lot of redundant processing! Instead, I'd suggest creating a single class of Commands and creating member functions for that class. With a re-engineered class, the main function might look like this:

int main(int argc, char *argv[]) {
    for (const auto &item: commands.find(&argv[0], &argv[argc])) {
        std::cout <<  item << std::endl;
    }
}

This uses the command line input to create a vector of strings, rather than prompting for input, but that's a minor point. The significant change is that there is presumed to be a commands object that has a find member function that returns something that has an iterator. How we might go about writing this is described in the following items.

Eliminate global variables

There is really no compelling reason here to have global variables, even when they're as relatively benign as your static const commands array. I'd be inclined instead to either put it as an automatic variable within main or, if you really must have a global variable, at least wrap it inside a usable object or namespace.

Promote your structs to classes

Right now, there's only loose association between the functions and the data structures on which they operate. This could be made more clear by the use of objects, and more safe by making those objects class rather than struct types. Let's first look at your existing Command struct:

struct Command {
  std::string text;
  std::string description;
  std::vector<std::string> addl_keywords;
};

Right now, within the various functions, they reach in directly into the member data items and directly manipulate them. This is not good object design because it places no limits on how the objects are used. Really, we could make it into a class and write just three relatively simple member functions.

First, we can make all data items private:

class Command {
private:
    std::string text;
    std::string description;
    std::vector <std::string> addl_keywords;

Next, a simple constructor:

public:
    Command(const std::string &mytext,
        const std::string &mydesc,
        const std::vector<std::string> kwds)
    : text{mytext}, 
    description{mydesc},
    addl_keywords{kwds}
    {}

Next, a simple way to convert a particular command into a string for output:

    std::string toString() const {
        return description + ": " + text;
    }

Finally, a function that takes a single word as input, and return true if that word is somewhere within the data items for this command:

    bool find(const std::string &word) const {
        if (text.find(word) != std::string::npos  || 
            description.find(word) != std::string::npos) {
            return true;
        }
        for (const auto &w : addl_keywords) {
            if (w.find(word) != std::string::npos) {
                return true;
            }
        }
        return false;
    }
};

This uses std::string's find() which returns the value std::string::npos if the string is not found.

Next, rather than FoundCommand, why don't we refactor into a Commands class that contains a collection of objects of type Command? For this, we can start with the private data:

class Commands {
private:
    std::vector<Command> cmd;

Now let's create a constructor that allows us to as easily create this object as the original code created the simple array of Command structures:

public:
    Commands(std::initializer_list<Command> list)
    : cmd{list}
    {}

This uses the very handy std::initializer_list object. I'll show how to use it at the end of this review.

The last item is now a find routine. Unlike the find for a single Command, this find searches all of the Commands and also takes two iterators as arguments. Doing it that way allows us to use a very wide range of input structures to work with this function. Essentially, as long as we can pass two iterators (most likely a begin and end), that resolve to std::string types when dereferenced, we can use this function:

    template <class InputIt>
    std::vector<std::string> find(InputIt first, InputIt last) const {
        std::vector<std::string> result;
        for (const auto &c : cmd) {
            for (auto it=first; it!=last; ++it) {
                if (c.find(*it)) {
                    result.emplace_back(c.toString());
                    break;
                }
            }
        }
        return result;
    }
};

Now the entire main can be written like this:

int main(int argc, char *argv[])
{
    const Commands commands{
        {
            "amixer -Mq set Master 1%-", "decrease volume", {
        "lower"}}, {
            "amixer -Mq set Master 1%+", "increase volume", {
        "raise"}}, {
            "makepkg -sri", "build and install a package using a PKGBUILD file", {
        "pkgbuild"}}, {
            "makepkg -efi", "rebuild and reinstall a package using a PKGBUILD file", {
        "build", "install", "pkgbuild"}}, {
            "pacman -Qdt", "list orphaned packages", {
        "find", "orphan"}}, {
            "pacman -Qe", "list explicitly installed packages", {
        "find", "explicit"}}, {
            "pacman -Ql [package]", "list files owned by package", {
        "find", "own"}}, {
            "pacman -Qo [file]", "list packages that own file", {
        "find", "owned"}}
    };
    for (const auto &item: commands.find(&argv[0], &argv[argc])) {
        std::cout <<  item << std::endl;
    }
}

The advantage of doing it this way is that if you decided you wanted to, say, pull in the definitions from a file, all you would have to do would be to make a small change in how the commands variable is created. Also, if you wanted to have a more sophisticated search approach, that could easily be implemented without changing the interface. All of the details could be hidden within the implementation of the Command::find() function.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

\$\endgroup\$
  • \$\begingroup\$ copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(input_keywords)); seems to just hang, waiting for eof or something? \$\endgroup\$ – David Kennedy Nov 15 '15 at 18:04
  • \$\begingroup\$ Yes, it needs eof (usually Ctrl-D) to know when the stream is complete. \$\endgroup\$ – Edward Nov 15 '15 at 18:17
  • \$\begingroup\$ The results are no longer sorted by closest match, which is why I had the FoundCommand class. I think I need to put that class back and use it in Commands.Find(). \$\endgroup\$ – David Kennedy Nov 16 '15 at 4:05
  • \$\begingroup\$ Yes, your original code had features which I did not reproduce. My primary intent was more to show an alternative organization rather than suggesting an alternative algorithm. If you better isolate the algorithm, you can more easily experiment with alternatives. \$\endgroup\$ – Edward Nov 16 '15 at 13:31
  • \$\begingroup\$ I see. Thanks for giving such a thorough review :) \$\endgroup\$ – David Kennedy Nov 16 '15 at 18:09

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.