[c++] Ordinare vector con posizioni fissate.

[F4b10_01]

Ho un vettore in input contenente interi positivi e interi uguali a "-1".
Devo ordinare il vettore lasciando inalterate le posizioni in cui il vettore risuta "-1".

Esempio:
input: [-1, 150, 190, 170, -1, -1, 160, 180]
output: [-1, 150, 160, 170, -1, -1, 180, 190]

Ovviamente so come ordinare un vettore (sia mediante algoritmi vari, sia mediante funzioni da stl), ma non so/capisco come fare a lasciare inalterate le posizioni a "-1".
Suggerimenti?
Grazie.

[Keyser70]

Dipende dall'efficienza che vuoi ottenere e dalla memoria a disposizione.
Supponiamo che il tuo sia un array e non uno std::vector, ma la cosa diventa ancora più semplice in tal caso.

Se non hai problemi di memoria puoi usare un set e poi sostituire i valori nel vettore originale.
Il set, nelle applicazioni reali, è velocissimo.

static const size_t size=8;
int v[size] = {-1, 150, 190, 170, -1, -1, 160, 180};

std::set<int> ordered;

for( int i = 0; i < 8; i++)
if( v[i]!=-1)
ordered.insert(v[i]);
// adesso ordered contiene [150, 160, 170, 180]

std::set<int>::iterator it = ordered.begin();
for( int i = 0; i < 8; i++)
if( v[i]!=-1)
v[i] = (*it);
// adesso v contiene [-1, 150, 160, 170, -1, -1, 180, 190]

Se invece la memoria è un problema puoi guardare qui (in inglese).

[Marcus Aseth]

una cosa del genere?

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

template<typename T>
using Iter = typename vector<T>::iterator;

template<typename V>
using value_type = typename V::value_type;

template<typename T>
struct Skip {
	T condition;
	Skip(T t) :condition{ t } {};
	template<typename T> bool operator()(T t) { return condition != t; }
};

template<typename Iter>
void sort_if(Iter Begin, Iter End,
			 function<bool(value_type<Iter>)> Condition,
			 function<bool(value_type<Iter>, value_type<Iter>)> Pred);

template<typename T>
void Print(vector<T>);

int main()
{
	vector<int> VecI{ -1, 150, 190, 170, -1, -1, 160, 180 };
	vector<string> VecS{ "casa","libro","zzz","pianta","zzz","zzz","auto" };

	sort_if(VecI.begin(), VecI.end(), Skip<int>(-1), less<int>());
	sort_if(VecS.begin(), VecS.end(), Skip<string>("zzz"), less<string>());

	Print(VecI);
	Print(VecS);
}

template<typename Iter>
void sort_if(Iter Begin, Iter End,
			 function<bool(value_type<Iter>)> Condition,
			 function<bool(value_type<Iter>, value_type<Iter>)> Pred)
{
	for (auto First = Begin; First != End; First++)
	{
		for (auto Second = First + 1; Second != End; Second++)
		{
			if ((Condition(*First)) && (Condition(*Second)))
			{
				if (!Pred(*First, *Second)) {
					iter_swap(First, Second);
				}
			}
		}
	}
}

template<typename T>
void Print(vector<T> Vec)
{
	for (auto&n : Vec) {
		cout << n << "  ";
	}
	cout << endl;
}