Title: Code Critique Competition 122

Author: Bob Schmidt

Date: 03 March 2020 22:52:23 +00:00 or Tue, 03 March 2020 22:52:23 +00:00

Summary: Set and collated by Roger Orr. A book prize is awarded for the best entry.

Body: 

Please note that participation in this competition is open to all members, whether novice or expert. Readers are also encouraged to comment on published entries, and to supply their own possible code samples for the competition (in any common programming language) to scc@accu.org.

Note: if you would rather not have your critique visible online please inform me. (Email addresses are not publicly visible.)

Last issue’s code

I wanted to offload logging to the console from my main processing threads, so I thought I’d try to write a simple asynchronous logger class to help me do that (and hopefully learn something about threading while I’m doing it). Unfortunately it only prints the first line (or sometimes the first couple) and I’m not really sure how best to debug this as the program doesn’t seem to behave quite the same way in the debugger.

     $ queue.exe
     main thread
     Argument 0 = queue.exe

or sometimes only:

     $ queue.exe
     main thread

The coding is in three listings:

• Listing 1 contains async_logger.h
• Listing 2 contains async_logger.cpp
• Listing 3 contains queue.cpp.

#pragma once

#include <iostream>
#include <queue>
#include <string>
#include <thread>

using std::thread;

class async_logger
{
  bool active_;
  std::queue<std::string> queue_;
  thread thread_ { [this]() { run(); } };
  
  void run();
  
public:
  async_logger();
  ~async_logger();
  void log(const std::string &str);
};
			

#include "async_logger.h"
#include <iostream>
using std::thread;

// This runs in a dedicated thread
void async_logger::run()
{
  while (active_)
  {
    if (!queue_.empty())
    {
      std::cout << queue_.front() << '\n';
      queue_.pop();
    }
  }
}
async_logger::async_logger()
{
  active_ = true;
  thread_.detach();
}
async_logger::~async_logger()
{
  active_ = false;
}

// queue for processing on the other thread
void async_logger::log(const std::string &str)
{
  queue_.emplace(str);
}
			

#include "async_logger.h"

int main(int argc, char **argv)
{
  async_logger logger;
  logger.log("main thread");
  thread test1([&logger]() {
    logger.log("testing thread 1");
  });
  for (int idx = 0; idx < argc; ++idx)
  {
    logger.log("Argument "
      + std::to_string(idx) + " = "
      + argv[idx]);
  }
  logger.log("main ending");
  test1.join();
}
			

Note: I inadvertently elided an underscore in transcribing the code for publication. I’m sorry for any confusion.

Critiques

Paul Floyd

Let’s start by running through ‘main’ to see what should be happening.

1. An instance of async_logger is created on the stack. The constructor creates a thread with a lambda that executes the run() member, sets the active flag and detaches the thread that was just created.
2. A log message is sent from main().
3. A thread is created with a lambda that captures the logger instance by reference, and sends a message.
4. A for loop sends messages to the logger, one per command line argument.
5. A final ending message is sent to the logger.
6. The lambda thread from step 3 is joined.
7. Logger goes out of scope at the end of main. Its destructor clears the active_ flag, causing async_logger::run() to terminate.

On a semi-positive note, I see that the two threads that get created are either detached or joined. Creating detached threads is not recommended, see http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rconc-detached_thread.

Now for the problems. Firstly, a nitpick. I don’t like the member variable of async_logger called thread. The other members use a trailing underscore, so I’d prefer that to be thread thread_.

Next, there is a problem with the initialisation of async_logger::active_. The async_logger constructor will initialise its members in order of declaration. active_ is first, but is not initialised. Next queue_ is initialised, via its constructor. Next thread is initialised, as per the default member initialiser. In the body of the constructor, active_ is set to true and thread is detached.

There is a data race on the active_ member. If the uninitialised value is false and thread runs to the while (active_) test before the constructor body sets active_ to true then run() will terminate.

To fix this, move the initialisation of active_ either to the initializer list or use default member initialisation. For consistency, the latter is what I would recommend.

The next problem is also a data race. Read and write to async_logger::queue_ are not controlled, and std::queue is not thread safe.

To fix this, we can add a std::mutex to async_logger and then use a std::lock_guard (with an extra scope) in async_logger::run() and async_logger::log().

Are we done? No, there are still two more data races. They both involve the async_logger destructor. Firstly, there is a data race in the active_ member. The destructor sets active_ to false, but run could be reading it at the same time. To solve this we can make active_ an atomic (e.g., std::atomic<bool> active_;). In general this sort of error is ‘mostly harmless’ – if the race condition triggers it will probably just mean that run does one more iteration. However, I would still advise fixing the issue. The last data race concerns the destruction of queue_. The run thread could be accessing this member while the main thread destructor is destroying it. Unfortunately, there’s no easy way in the destructor to know when the run thread has terminated (and so it is safe to destroy queue_). So here I suggest not detaching the run thread. Remove the detach from the constructor and add a join to the constructor. After the join, we know that the run thread has terminated, so it is safe to proceed with the default destruction of queue_.

Are we there yet? No, still a long way to go. The data races are fixed, but there are still two problems. The first is that main() does nothing to make sure that async_logger::run() has emptied queue_ before it terminates (remember, the termination condition for run is that active_ is false, not that queue_ is empty. We can fix this by adding a loop to empty queue_ in the async_logger destructor.

The last remaining issue is performance. run() is busy-polling. It will be using ~100% of a CPU as long as the application runs. The fix for this is to use thread communication, for instance a std::condition_variable. Add one as a member of async_logger, add a call to notify_one in log and add a wait in run (and change the lock_guard to unique_guard).

OK, now we are done. No more thread hazards or CPU hogging and no missing output.

I spotted most of the issues other than the destructor and falling off main just by looking at the code. For further testing I used Thread Sanitizer, Valgrind DRD and Valgrind Helgrind.

A bit now about tools. As an example, I ran the unmodified code with clang++ -fsanitize=thread and I got

  WARNING: ThreadSanitizer: data race (pid=89319)
  Read of size 1 at 0x7ffee1517890 by thread T1:
  #0 async_logger::run() async_logger.cpp:8
  (cc121:x86_64+0x1000015a0)
  
  [snip]
  
  Previous write of size 1 at 0x7ffee1517890 by
  main thread:
  #0 async_logger::async_logger()
  async_logger.cpp:19 (cc121:x86_64+0x1000018b8)

Always test your thread code with a dynamic analysis tool!

I’ll finish with a few comments about the design. As always, you should consider reusing code or packages where possible. I’m sure that there are many existing packages for performing asynchronous logging. The code here only logs to standard output. A more complete system would have options to log to a file, syslog, Windows Events as a few examples. I would also expect some sort if severity level like critical, serious, warning and information, perhaps with an option to filter out levels. I have just one last point. Systems like this have a hard time with logging events that occur during program shutdown. How can I log an event from the destructor of an object that is a file static? logger, being local to main(), will have already been destroyed when static destructors start getting called.

Ovidiu Parvu

Let us assume throughout that two requirements need to be met by an async_logger object. Firstly an async_logger object can be used to log messages, which will be printed to the standard output in the order in which they were logged. Secondly the logged messages will be printed to the standard output on a separate thread. All messages should be printed to the standard output before the async_logger object is destructed.

There are four main issues with the implementation given in the listings provided.

First of all the code cannot be compiled successfully due to an undeclared identifier error. Specifically the std::thread async_logger data member is referred to as thread_ at async_logger.cpp:20:3 but it is defined as thread in async_logger.h. Renaming the data member from thread to thread_ as shown below, which would be consistent with the naming of other async_logger data members (e.g. active_), addresses this issue.

  // async_logger.h
  class async_logger
  {
    ...
    thread thread_ { [this]() { run(); } };
    ...
  };

Secondly, the active_ async_logger data member should be initialized with the value true when an async_logger object is constructed and before the thread_ data member is initialized. Otherwise it may be possible for the while (active_) { ... } loop in the run() method to be executed before the value of active_ is set to true, and therefore the run() method will finish executing before the async_logger object is constructed. In this case no logged messages would be printed to the standard output. To avoid this issue the active_ data member is initialized with the value true using a default member initializer as shown below.

  // async_logger.h
  class async_logger
  {
    ...
    bool active_ = true;
    ...
  };
  // async_logger.cpp
  async_logger::async_logger()
  {
    thread_.detach();
  }

Thirdly, read and write access from multiple threads to the active_ and queue_ async_logger data members should be synchronized. Otherwise data races could occur. Access to the active_ data member can be synchronized by changing the type of active_ from bool to std::atomic_bool and importing the <atomic> header as follows.

  // async_logger.h
  #include <atomic>
  ...
  class async_logger
  {
    ...
    std::atomic_bool active_{true};
    ...
  };

Conversely, access to the queue_ data member can be synchronized using a std::mutex. The mutex needs to be used in different async_logger member functions and therefore will be added as a data member to the async_logger class. The mutex will be (unique) locked in the run() and log(const std::string&) methods before accessing the queue_ data member as follows. In addition the <mutex> header must be included in async_logger.h.

  // async_logger.h
  ...
  #include <mutex>
  ...
  class async_logger
  {
    ...
    std::mutex mutex_;
    ...
  };
  // async_logger.cpp
  // This runs in a dedicated thread
  void async_logger::run()
  {
    while (active_)
    {
      std::unique_lock<std::mutex> lock(mutex_);
      if (!queue_.empty())
      {
        std::cout << queue_.front() << '\n';
        queue_.pop();
      }
    }
  }
  // queue for processing on the other thread
  void async_logger::log(const std::string& str)
  {
    std::unique_lock<std::mutex> lock(mutex_);
    queue_.emplace(str);
  }

Fourthly, the thread used to print messages to the standard output should not be detach()’ed in the async_logger constructor, and should be join()’ed in the async_logger destructor, because otherwise it will not be possible to wait for all messages to be printed on this thread before the async_logger object is destructed. After removing the thread_.detach() statement from the async_logger constructor, the constructor definition body is empty. Therefore both the async_logger constructor declaration and definition can be removed. The updated async_logger destructor definition is given below.

  // async_logger.cpp
  async_logger::~async_logger()
  {
    active_ = false;
    thread_.join();
  }

To ensure that all log messages are printed to the standard output before the async_logger is destructed, an additional loop is added to the run() method which prints all log messages remaining in queue_ after active_ is set to false and the while (active_) { ... } loop finishes executing. Both the newly added loop and the while (active_) { ... } loop pop the log messages from queue_ and print the messages to the standard output. Therefore the log messages printing code can be extracted into a separate member function called print_oldest_msg() as follows.

  // async_logger.h
  class async_logger
  {
    ...
    void print_oldest_msg();
    ...
  };
  // async_logger.cpp
  // This runs in a dedicated thread
  void async_logger::run()
  {
    while (active_)
    {
      std::unique_lock<std::mutex> lock(mutex_);
      if (!queue_.empty()) print_oldest_msg();
    }
    while (!queue_.empty()) print_oldest_msg();
  }
  void async_logger::print_oldest_msg() {
    std::cout << queue_.front() << '\n';
    queue_.pop();
  }

Additional minor improvements that could be made to the code given in provided listings are that the using std::thread; statements could be removed to avoid future potential name collisions should the project include user-defined thread type definitions in the future, and the unused <iostream> header include could be removed from async_logger.h.

[Ed: The code in Listings 2–4 updated according to all the changes described above was provided, but is omitted for brevity.]

James Holland

Some minor points. #pragma once is not standard C++. My version of async_logger.h uses the more universal method of writing Include Guards. The original code is missing a trailing underscore in the declaration of thread_ within the async_logger class.

When I ran the software on my Linux system, it produced the desired output. This was unfortunate because it gave no hint as to what could be wrong. When the student ran the program, some of the expected output was missing. This suggests there are some problems with the ordering of events within the executing program. Some systems may order events in a different order than others. It is very difficult just by looking at the source code to determine the relative timing of events when multiple threads are involved. In an attempt to make some headway with this problem I constructed a timing diagram that is loosely based on the Unified Modelling Language (UML) sequence diagram as shown in Figure 1.

Figure 1

At the top of the diagram are the objects involved in the exchange of messages. The time axis runs from top to bottom. One feature that is revealed is that the execution of async_logger’s run function’s while-loop is dependent on value of the active_ variable. Unfortunately, it is quite possible that the variable has not been assigned a value before it is read by the while-loop. The problem is that active_ is not initialised as soon as it could be. It is assigned a value within the body of async_logger(). This gives time for the while-loop to read the uninitialised variable. Probably the simplest way of correcting this problem is to initialise active_ to true within the class definition of async_logger (located in async_logger.h). Objects are initialised in the order they are declared within the class. Declaring (and initialising) active_ before thread_ ensures active_ is set to the required value before it is read by thread_. The assignment of active_ within the body of async_logger’s constructor can now be removed.

The sequence diagram also reveals a problem when logger is terminated. There is no guarantee that the calls to empty() and pop() will access a valid version of queue_ or that active_ exists when an attempted is made to access it by run(). Perhaps the simplest way to ensure these objects are still valid when accessed is for the destructor of async_logger to call thread_’s join() function instead of the constructor of async_logger calling thread_’s detach() function.

The compiler and the processor hardware are capable of optimising the program in ways that include altering the order in which instructions are executed as long as the result of a single thread of execution is the same as for the unaltered program. This can cause problems when two or more threads interact. In the program in question it is important that active_ is assigned a value at the appropriate time relative other instructions. To prevent such reordering, the type of active_ should be changed from bool to atomic_bool.

With any luck, the program is now producing the desired result. The program relies on luck because the C++ standard makes no guarantees about the correct operation of std::queue when working in a multi-threaded environment. What is needed is a thread-safe queue. Such queues are a little involved and I do not intend to explore their construction here. One of the best sources of information regarding threads and concurrency in general is the book by Anthony Williams, C++ Concurrency in Action, second edition, ISBN 978-1617294-69-3. Here, various thread-safe queues are discussed and are worthy of study. Implementing a thread-safe queue will remove the element of luck.

There is another interesting aspect to the student’s code. The function run() belonging to async_logger contains a loop that continually tests for items in the queue. This is wasteful of processor resources. It would be better for the async_logger thread to ‘sleep’ when there is nothing in the queue and to be ‘woken’ when something is added to the queue. Such a facility is provided by condition variables.

I have added a mutex, m, and a condition variable, data_available, to global scope. I have modified async_logger’s log function by changing the if statement for another while-loop and created a unique_lock object using the mutex m. A call is then made to data_available’s wait() function. In log(), I have added a call to data_available’s notify_one() function just after an item has been placed on the queue. In this way a thread can block on the wait() function until awoken by notify_one().

Arranging for run() to break out of the while-loop is a little tricky. I have chosen to wake-up the blocked thread with another call to notify_one() just after setting active_ to false. This requires a modification to waits()’s lambda so that execution can continue if active_ is false. An if statement is also added after the newly added while-loop of run() that has the effect of returning from run() when active_ is false. Another way to return from run() is to recognise a special message placed on the queue and to return when it is detected.

I provide my version of the code despite it not having a thread-safe queue. It may be instructive, however.

  --- async_logger.cpp ---
  #include "async_logger.h"
  #include <iostream>
  std::mutex m;
  std::condition_variable data_available;
  using std::thread;
  // This runs in a dedicated thread
  void async_logger::run()
  {
   while (true)
    {
      std::unique_lock<std::mutex> lock(m);
      data_available.wait(lock, [this]{
        return !queue_.empty() || !active_;});
      while (!queue_.empty())
      {
        std::cout << queue_.front() << '\n';
        queue_.pop();
      }
      if (!active_)
      {
        return;
      }
    }
  }
  async_logger::~async_logger()
  {
    active_ = false;
    data_available.notify_one();
    thread_.join();
  }
  // queue for processing on the other thread
  void async_logger::log(const std::string &str)
  {
    queue_.emplace(str);
    data_available.notify_one();
  }

  --- async_logger.h ---
  #ifndef ASYNC_LOGGER
  #define ASYNC_LOGGER
  #include <iostream>
  #include <queue>
  #include <string>
  #include <thread>
  #include <atomic>
  #include <mutex>
  #include <condition_variable>
  using std::thread;
  class async_logger
  {
  private:
    std::atomic_bool active_ = true;
    std::queue<std::string> queue_;
    thread thread_{[this](){run();}};
    void run();
  public:
    ~async_logger();
    void log(const std::string &str);
  };
  #endif
  
  --- queue.cpp ---
  #include "async_logger.h"
  int main(int argc, char **argv)
  {
    async_logger logger;
    logger.log("main thread");
    thread test1([&logger](){
      logger.log("testing thread 1");});
    for (int idx = 0; idx < argc; ++idx)
    {
      logger.log("Argument " +
        std::to_string(idx) + " = " +
        argv[idx]);
    }
    logger.log("main ending");
    test1.join();
  }

Hans Vredeveld

In making the author’s code available to us for review, the variable thread_ lost its underscore in the declaration on line 14 of async_logger.h. After correcting this, the code compiled and ran with the behaviour as described by the author.

One thing that testing this program makes clear, is that testing multi-threaded programs is hard. When I run the program with four arguments, I had to run it 27 times before I got something different than the expected output. When I run it with the complete alphabet as program arguments, it usually didn’t give the expected output, but stopped somewhere after outputting the letter m.

Before we delve into the real issues with the code, let’s get some annoyances out of the way.

Following the mantra ‘include what you use and nothing else’, #include <iostream> should be removed from async_logger.h, and queue.cpp should have #includes for <string> and <thread>.

Unscoped using declarations in headers should be avoided at all times and used with extreme care in implementation files. They can cause conflicts with identifiers that a user defines herself. At best this will result in a compiler error. At worst it will compile and link without any error or warning, but use the wrong declaration. We can remove the using declaration for std::thread in async_logger.h and qualify the types of thread_ in async_logger.h and test1 in queue.cpp with std::. The #using std::thread in async_logger.cpp serves no purpose at all and should be removed.

The last annoyance is the parameter of async_logger::log. Its type is std::string const&, and this forces the compiler to always copy the string into the queue. Especially for a log-function, that is called with a temporary object most of the time, it would be nice if we could use move semantics. Changing the function to

  void async_logger::log(std::string str)
  {
    queue_.emplace(std::move(str));
  }

makes this possible. Of course, async_logger.cpp now must #include <utility>.

Now that the annoyances are out of the way, let’s focus on the real problems. The first thing to notice is that in async_logger, thread_ has a default member initializer and that active_ is not initialized until inside the constructor body. Depending on thread scheduling, this could mean that thread_ starts executing async_logger::run while active_ is still not initialized and might have the value false. The while-loop in async_logger::run might thus never be executed. The solution to this problem is to remove the initialization of active_ from the constructor's body and move it to the member initializer list or to a default member initializer. Also, active_ is used from multiple threads and not only for reads. Therefore, it should be an std::atomic_bool instead of a bool.

More on thread_. In async_logger’s constructor the thread that it creates is detached. Consequently, the lifetime of the running thread is not connected to the lifetime of the async_logger instance that created it any more. The thread keeps on running when the async_logger instance that it is using, is destroyed, resulting in undefined behaviour. To solve this, remove thread_.detach() from the constructor and add thread_.join() to the destructor after setting active_ to false. Note that, if active_ was initialized by a member initializer, now there is no need to define the constructor explicitly any more, and we can leave it to the compiler to generate one.

Now, when active_ becomes false, the thread will drop out of the while-loop in async_logger::run and the thread will exit. Also, each time the body of the while-loop is executed and there are messages in the queue, only one message is printed. So when the thread drops out of the while-loop, any remaining messages in the queue are not printed, which is the behaviour that the student observed. By changing the if-statement to a while-statement, we make sure that all messages in the queue are printed before active_ is checked again.

While it now looks like we have the behaviour that the student wanted, there are still two issues with the code. First, std::queue is not thread safe. Second, async_logger::run uses a busy wait for queue_ to be filled again. We can solve these issues with a mutex and a condition variable. First, we add them as private members to the async_logger class in async_logger.h:

  std::mutex mutex_;
  std::condition_variable cv_;

Of course, we must also #include <mutex> and <condition_variable>. Now before we add a message to the queue in async_logger::log, we lock the mutex, and after we add the message, we notify a thread through the condition variable:

  void async_logger::log(std::string str)
  {
    std::lock_guard<std::mutex> lock(mutex_);
    queue_.emplace(std::move(str));
    cv_.notify_one();
  }

Now async_logger::run is a bit more complex:

  void async_logger::run()
  {
    while (true)
    {
      std::queue<std::string> q;
      {
        std::unique_lock<std::mutex>
          lck(mutex_);
        cv_.wait(lck,
          [this](){ return !(queue_.empty() &&
                             active_); });
        if (queue_.empty() && !active_)
            return;
        q = std::move(queue_);
        queue_ = std::queue<std::string>();
      }
      while (!q.empty())
      {
        std::cout << q.front() << '\n';
        q.pop();
      }
    }
  }

We need to hold a lock on mutex_ when we are accessing queue_, but we don’t want to hold the lock when printing the messages. Therefore, we move the messages to a local queue q, reinitialize queue_ as an empty queue and release the lock before we print the messages from the local queue.

Also, we let the thread sleep until there is something in queue_ or the async logger has become inactive. To make sure that we print the last messages, we change the outer while-loop into a perpetual loop and in its body explicitly return from the function when queue_ is empty and active_ is false.

Commentary

This simple looking example has multiple problems and goes to show, in Hans’s words “that testing multi-threaded programs is hard”.

The wording for this critique says the user is trying to write some logging to offload work from their main thread, and thought they’d use this as a chance to “learn something about threading”. I would avoid trying to learn threading indirectly like this as there are too many ‘sharp edges’ and the resultant code may well be buggy. Better to work through a tutorial or a book, such as Anthony’s C++ Concurrency in Action that James mentioned.

As far as the code itself goes, the entrants between them did a great job of finding the problems, explaining what was wrong, and providing solutions, so I don’t have a huge amount to add.

One concern I had over James’ solution is that he uses global variables m and data_available, which could cause link-time problems (and also have a potential static initialisation order problem).

All the critiques fixed the race condition in active_, then made it an atomic_bool for thread-safety reasons, and then added a mutex to make access to the queue thread-safe. Once the mutex was added I think the change to atomic_bool should be reverted (and the variable accessed while the mutex is locked) as there are two conditions for the thread to check and using a single synchronisation mechanism makes it easier to avoid threading errors, such as deadlock.

The original code had a potential inefficiency over copying temporary strings; Hans changed the function to take a string by value which is an optimisation for temporary strings and at least no worse for others. Should measurement indicate the performance of this method is a problem, there are other possibilities to investigate such as adding overloads for common use cases.

A note on #pragma once. While this is non-standard, it is very widely supported. There was at least one proposal to standardise this (wg21.link/p0538), but it was rejected in Kona 2017.

The winner of CC 121

All four critiques covered the major problems with the code and produced a solution that fixes the errors. Some additionally pointed out that the reading thread is using a busy loop and corrected this using a condition variable – this is probably the correct thing to do, unless latency is critical!

Diagrams like the one that James made use of can be really useful in a threading algorithm in identifying the dependencies and possible errors in logic, such as race conditions. This can be done in conjunction with dynamic analysis tools, such as those that Paul describes.

I liked Ovidiu’s introduction of a helper function print_oldest_msg as this made a separation between the logic of handling the queue and the work of processing the contents. While it doesn’t make too much difference in such short examples, this is the sort of separation of concerns that can make code significantly easier to understand.

Paul ends his critique by raising some of the design issues with logging and recommends looking for an existing package. I consider that may be the best advice in this case. Ovidiu’s opening paragraph lists two basic requirements of an asynchronous logger, which could be the basis of a check list for looking for a third-party logger.

There is a problem with ‘liveness’ in that the first three solutions process the message in the logging thread with the mutex locked. This blocks the main thread if it tries to log again during the I/O. Hans’s solution ensures that the processing of the queue of messages happens outside of the lock. (I think rather than moving from the queue and assigning a default constructed one it might be simpler to just swap the two queues over.)

Ending gracefully remains a potential problem: both Paul’s and Hans’s critiques as they stand contains a possible deadlock on exit as the destructor also needs modifying when the condition variable and mutex are added to ensure it notifies the condition variable. Without this change the code could hang on exit if the logging thread is inside the call to wait. when the value of active_ is changed.

Overall there were four good critiques here, but I thought that Paul’s discussion of dynamic analysis tools and his closing comments on the design made his critique broader in coverage and I have awarded him the prize for this issue’s critique.

Code Critique 121

(Submissions to scc@accu.org by April 1st)

I was set a challenge to read the ‘Top 100 books’ (from the BBC Big Read a few years ago) so thought I could start by seeing which ones I needed to get. Obviously this meant writing a program. Unfortunately, the output from the program isn’t sorted, although I was expecting it would be; and in addition, it crashed on Windows.

Can you help the author fix their program so they can begin to catch up with their reading? The program (the_big_read.cpp) is in Listing 4.

#include <algorithm>
#include <iostream>
template <int A, int B>
void to_buy(const char *(&to_read)[A],
  const char *(&own)[B])
{
  const char** ptr = new const char *[A];
  const char **first = ptr;
  for (int i = 0; i != A; ++i)
  {
    *ptr++ = to_read[i];
    for (int j = 0; j != B; ++j)
    {
      if (!strcmp(to_read[i], own[j]))
      {
        ptr--; // already own it!
      }
    }
  }
  std::sort(first, ptr);
  for (const char **q = first; q != ptr; ++q)
    std::cout << *q << std::endl;
  delete ptr;
}
int main()
{
  const char* top_100 [] = {
    "The Lord of the Rings",
    "Pride and Prejudice",
    "His Dark Materials",
    "The Hitchhiker's Guide to the Galaxy",
    // 93 missing ...
    "Girls In Love",
    "The Princess Diaries",
    "Midnight's Children",
    };
  const char* my_library[] = {
    "The Hitchhiker's Guide to the Galaxy",
    "Vintage Jeeves",
    // and many more ...
    "His Dark Materials",
    "Pride and Prejudice",
    "Emma",
    "Where Eagles Dare",
    };
  to_buy(top_100, my_library);
}
			

You can also get the current problem from the accu-general mail list (next entry is posted around the last issue’s deadline) or from the ACCU website (http://accu.org/index.php/journal</XRef> ). This particularly helps overseas members who typically get the magazine much later than members in the UK and Europe.

Roger Orr has been programming for over 20 years, most recently in C++ and Java for various investment banks in Canary Wharf and the City. He joined ACCU in 1999 and the BSI C++ panel in 2002.

Notes: 

More fields may be available via dynamicdata ..