Binary Search Algorithm

Description

The binary search algorithm is a divide and conquer algorithm, that takes a sorted array as an input. It works by comparing the searched value (key) to the middle element of the array. If they match, then its index is returned. If the key is less than the middle element, the algorithm is invoked on the left sub-array, otherwise it is invoked on right sub-array. This continues until the key is found or the input array is reduced to zero.

Recursion tree

Recursion tree

(more…)

C++ Observer Implementation

The Observer design pattern is used for state change notifications. An object called subject (or publisher) has a list of dependents, called observers (or subscribers). When the subject changes state, all its dependents are notified by calling a method. The Observer pattern is useful for the implementation of event handling.

UML diagram


The observer interface has an abstract method used for notifications and the subject has methods for attachment and detachment of observers.
(more…)

C++ Singleton Implementation

Singleton is the simplest and probably the most widely used of all design patterns. It’s so popular that some IDEs (like SlickEdit) have templates for its generation. The purpose of this design pattern is to ensure that only one instance of a class is created.
So, why discuss Singleton?
(more…)

Using CxxTest

Unit Testing 2 of 3

Having compared the two most popular C++ unit testing frameworks, let’s move on to the next step – the actual usage. Personally I prefer CxxTest, that’s why the samples bellow demonstrate its use. The test target will be the sample implementation of a read-only memory mapping.
(more…)

Tracing Memory Issues

I wasted two weeks of my life, hunting for a bug that is corrupting the heap of a server application. The application runs on Unix-like OSs and is fairly complex. It’s multithreaded and consists of a front-end and several back-ends. The server is written in C++ and it has in-house developed garbage collector. It exposes CORBA interface and several clients, developed in different languages (Java, C#, Perl), connect to it. (more…)

C++ Unit Testing Frameworks

Unit testing is focused on the smallest testable part of an application. A unit test exercises an individual portion of code, to determine if it functions properly.

Unit testing:

  • reduces the cost of software – defects are discovered during the development stage and can be fixed prior to the release to the test team;
  • promotes interface-based approach of implementing components. The interfaces are adding abstraction, that makes the code flexible;
  • ensures that the software functions as specified by the requirements.

(more…)

Memory Mapped Files

A memory mapped file is a disk file (or a part of it) that has been associated to a segment of the virtual memory space of a process. It’s useful when you need to manipulate files that are too large to fit in memory. Once mapped you can access the file as if it was entirely uploaded in memory. In reality the OS is paging the appropriate part of the file as you read from the mapped file pointer.

Benefits

  • It’s faster to access memory mapped files, than to use direct read and write operations;
  • You can use the data without copying it;
  • Ease of use.

Drawbacks

  • You are limited by the process space. On 32-bit versions of Windows typically the applications have 2 GB addressable memory, meaning that you can not map files bigger than 2 GB.

(more…)

Error Handling – The C++ Way

In my experience as software developer, I noticed that there are lots of people that write in C++, but do not use exceptions. They prefer to use return codes instead. I guess that this is caused by the late addition of exceptions in the C++ standard. Whatever the reason is, personally, I prefer to use exceptions as an error handling technique.

Almost 10 years ago I started programing in Object Pascal (Borland Delphi). It was really popular in Bulgaria at that time. I used to like it and I still think that Pascal is the best programming language for education purposes. In my opinion VCL is well designed framework, that is teaching developers good programming practices. Anyway, exceptions are widely used in VCL. So I got used to exceptions and when I moved to C++, I continued using this error handling mechanism.
(more…)