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++?

>>1
Either:
1) Use std::sort
2) Use an std::list and call the sort method after each insertion
3) Use an std::set to store the data (std::set uses some sort of self-balancing bst to store keys)
4) Read SICP