[C++] patching files

I am currently working on diff/patching utility. I finished diff generator and now it's time to apply that diff...

I was thinking about rewriting to another file with deleted elements to delete and adding elements to add... but that requires additional disk space and for applying small patches for big files it is not efficient (good word? :>) method. Second though is to do sth like this:

for every element to be deleted in diff in reversed order (from highest indexes)
{
go to index of element
for every few bytes after element
{
rewrite them at prievous index
set prievous index to end of rewrited element
}
}

and everything is deleted. Later similar loop to insert new data. But I have a question:

How to shorten file? I can rewrite everything back, and there won't be any problem when lenght of added strings is greater or equal to lenght of deleted, but if it's lesser, then there will be some "extra" bytes. Example:

base: This is file. Thing to be partially deleted.
delete: index of partially and 9 next bytes (entire word)
add: index of file, "some ".

So, after using that patching algorithm, it will be:

"This is some file. Thing to be deleted.ted."

How to cut of that "ted." and decrease size of file?