Incidentally, a week or so ago, a couple colleagues and I started a conversation about what might be the best way to implement a piece of code in C++. A simple outline was jotted on a text document. Regrettably I have misplaced the piece of paper. The purpose of the conversation was not the optimization of the specific code (at the time none was discussed), but to the approach (thinking process) a senior software developer would take to come up with an efficient implementation.
Based on our conversation, I decided to generate five associated blog entries. This is the first one. In it, I will formulate the issue / requirements. Please note that given the casual setting of the conversation, the requirements are simple and do not contain complete details. In general, a senior software developer would have a good handle of the scenario, other features, libraries, use of the software, user expectations, etc, etc, etc. All that knowledge aids in the design and implementation of simple solutions for what could be complex problems. That said, by no means, the example at hand should be considered a complex problem.
The problem / issue as far as I am able to recollect follows. Using C++, what type of primitive / class would you use to implement the following behavior: Ability to insert integers in a sorted manner. That is, when a new random integer is inserted the set would be always kept in ascending order.
For example, if the current set would contain the following set of integers: 1, 5, and 9, and a new element would be inserted (e.g., 7), the resulting set would be: 1, 5, 7 and 9.
The second part of the conversation was to support the deletion of elements from the set. The idea was to randomly remove one element from the set at a time.
For example, if the current set would contain the following set of integers: 2, 8, 11, and 17, and the element at a random position (e.g., 2) would be selected; the resulting set would hold the sequence: 2, 8 and 17. The description assumes the first element is at position zero (0).
Different suggestions were considered e.g., array, linked lists, vector or any other best suited class). Of course the number of elements in the set would be of consideration. Sorting a few thousand or hundreds of thousands is different that processing hundreds of millions. For the purpose of the conversation we decided to put an upper limit of 10,000 to 100,000 entries.
I mentioned that a few months ago, I implemented a type of array list to handle a similar situation. Instead of integers, I had to deal with TCP/IP addresses (i.e., 192.168.1.126). That said; an integer with enough bits would fit such requirements. Of course, life is not that simple, additional information (e.g., date and time, socket number) had to be included as part of the solution.
In Java, which I am also quite fluent, there is a commonly used class named ArrayList. Apparently such class (construct) is not available in the C++ language or commonly used libraries. If you perform a Google search, you will find a few implementations of the Java ArrayList in C++. I am not going to cover how I implemented the ArrayList construct that I used for a project at work.
The following three blog entries cover simple and similar implementations of ways to implement the basic requirements discussed in this blog entry. The fifth and last entry in this sequence will show the results of the execution times of the different console applications implemented using some of the constructs here proposed. I am glad to have taken the time to implement and test them.
John Canessa