Układanie elementów wektora w określonym porządku

Witam,
chciałbym uporządkować elementy vector <int> tak, by takie same elementy nie były obok siebie. Mam na myśli coś takiego:
{1, 2, 2, 2, 3, 3, 4, 4, 4}
chciałbym przekształcić w:
{1, 2, 4, 3, 4, 2, 3, 2, 4}
Czy jest na to jakiś algorytm, albo może już jest to w STLu? Szukam, szukam i znaleźć nie mogę.

Pozdrawiam.

http://www.cplusplus.com/reference/algorithm/random_shuffle/ ? ale nie masz wtedy wcale pewności że takie elementy nie będą obok siebie. Jeśli chcesz mieć taką pewność to musisz to posortować używając jakiegoś dziwnego komparatora.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
  {
   unsigned T[]={ 1, 2, 2, 2, 3, 3, 4, 4, 4, };
   vector<unsigned> Tb(T,T+sizeof(T)/sizeof(*T));
   map<unsigned,unsigned> Map;
   for(vector<unsigned>::iterator i=Tb.begin();i!=Tb.end();++i)
     {
      map<unsigned,unsigned>::iterator f=Map.find(*i);
      if(f==Map.end()) Map[*i]=1;
      else ++f->second;
     }
   cout<<"T[]={ ";
   for(bool more=true;more;)
     {
      more=false;
      for(map<unsigned,unsigned>::iterator i=Map.begin();i!=Map.end();++i)
        {
         if(i->second)
           {
            --i->second;
            cout<<i->first<<", ";
            more=true;
           }
        }            
     }
   cout<<"};";
   return 0;
  }

Dzięki za odpowiedź. Staram się zrozumieć Twoje rozwiązanie i zastanawiam się, jak je zmodyfikować, by powiedzmy dla { 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4 } odpowiedzą nie było { 1, 2, 3, 4, 2, 3, 4, 2, 4, 4, 4, 4 } tylko { 4, 1, 4, 2, 4, 3, 4, 2, 4, 3, 4, 2 }. Czy jest to możliwe?

Ja bym tu zrobił mapę, ile razy wystąpił dany item w wektorze wejściowym, a potem w pętli (while, a w niej for) bym wsadzał do wektora wynikowego klucze (liczby), faworyzując te z największą wartością (ilością wystąpień). Jeśli obecny klucz znajduje się na końcu wektora wynikowego, to robimy continue fora, a po dodaniu wartości do wektora wynikowego robimy break fora. I while robi tą rutynę, aż wszystkie wartości w mapie zejdą do zera (czy też jak kto woli, mapa zostanie pusta).