Sorting algorithms

I have a vector of a data structure i want to sort. My program works good, but when the amount of structures goes up, the program takes fucking ages to work. I don't want to piss around with bullshit sorting algorithms like bucket sort

I'm thinking about ordering it every time a new structure comes in. Whats the fastest way to order a vector of structures in c++?

There are data structures that do this for you, such as RBT