Making inserting to a Class** more efficient

[BAC Sun]

So I have a class called IPRecord. The program I'm supposed to write takes information from a file ("input.txt") and performs a binary search to find if the address has already been read in. If it has, it updates the frequency, if it hasn't it needs to insert in the correct position. Using std::vector<IPRecord> I could do it no problem, but we're supposed to use pointers and the class object.

I have the following code (which works), but I was curious if there is any way to make it more efficient?

I hard coded a binary search function to return not only if the address is found, but where it is or should be located also.

void addAddress(IPRecord** pRecordPointer, unsigned int position, int inbound, int fileSize) {
	if (pRecordPointer != NULL) {
//if the position doesn't have a record listed, add a new record
		if (pRecordPointer[position] == NULL) {							  
			pRecordPointer[position] = new IPRecord(inbound);
		}
//if the position already has a record listed, move the old records up, then add a new record
		else {															  
			for (int i = fileSize; i > position; --i) {
				if (pRecordPointer[i - 1] != NULL) {
					pRecordPointer[i] = NULL;
					pRecordPointer[i] = new IPRecord(pRecordPointer[i - 1]->getIP());
//increase frequency of pRecordPointer[i] to match correct frequency
					for (int j = 1; j < pRecordPointer[i - 1]->getFrequency(); ++j) {
						pRecordPointer[i]->incrementFrequency();		
					}
				}
			}
//delete IP and frequency at correct location
			delete pRecordPointer[position];							
//add inbound record
			pRecordPointer[position] = new IPRecord(inbound);			
		}
	}
}

[keskiverto]

I hard coded a binary search function to return not only if the address is found, but where it is or should be located also.

If you do look at the std::binary_search here: http://www.cplusplus.com/reference/algorithm/binary_search/
You will notice that it is equivalent to two steps:
1. std::lower_bound
2. test whether the position has the searched value

In other words, you have created a "binary_search" that does the same as std::lower_bound.
The lower_bound returns

An iterator to the lower bound of val in the range.
If all the element in the range compare less than val, the function returns last.

Iterator, for example a pointer.
The last is typically .end(), the iterator that you get when you advance one step from the last element.


Your pRecordPointer is an array of pointers, isn't it? You have somewhere a bunch of IPRecord objects and the array knows where.

You are using a lot of new and delete. Why all the deep copies? Why don't you simply update the pointers in the array?
Does something else point to the IPRecord objects too? (Obviously not, for you would not delete, if did.)

What if you get more unique addresses than there are places in your array?


Lets say that we have searched a Position. There are two possibilities:

1. Position has an element. Two subcases:
1a. Element has the address. Update the element
1b. Element does not have the address. Move* rest of array elements one step right. Now Position has no address. Create new element at the Position.

2. Position is "one past" the elements. Create* new element at the Position.

Both the move in 1b and the Create in 2 do require that the array does have capacity to assign an element to the "one past last" position. If it does not, then one has to increase the capacity of the array first.

[darkone41]

Could you post the whole source code? I might be able to help you out if I can see what you did.