I re-wrote command-not-found in C. It consists of two C programs: command-not-found, which gets triggered by bash, and update-command-not-found, which digests the data obtained with apt-file update.
AFAIK there is only one rough edge, in that the parsing of /etc/apt/sources.list is not the same as apt's parsing. I do not know enough C++ to use libapt to do this. https://github.com/shawnl/command-not-found/ -Shawn Landden
