sorting - Instant sort when put new value in array C++ -

i have dynamically allocated array containing structs key pair value. need write update(key,value) function puts new struct array or if struct same key in array needs update value. insert , update combined in 1 function.

the problem is:

• before adding struct need check if struct key existing.

  i can go through elements of array , compare key (very slow)

  or can use binary search, (!) array must sorted.

  so tried sort array each update (sloooow) or sort when calling binary search funtion.....which each time updating

finally, thought there must way of inserting struct array it placed in right place , sorted.

however, couldn't think of algorithm came here ask because google refuses read mind.

i need make code faster because array accepts more 50 000 structs , i'm using bubble sort (because i'm dumb).

take @ red black trees: http://en.wikipedia.org/wiki/red%e2%80%93black_tree

they ensure data sorted, , has complexity of o ( log n ) inserts.

a binary heap not suffice, binary heap not have guaranteed sort order, guarantee top element either min or max.