Vektörde bir elemanı sıralamak için en etkili yol?

Question

Bazı dış değerlere göre sıralanmış öğelerden oluşan bir vektörüm var. Büyük bir konteynırdır ve sıralama değerine bakmak nispeten pahalıdır. Bir noktada bir elemanın (sadece) yeniden sıralanması gerekir. Bu elemanı yeniden sıralamak için en etkili yol nedir? std::sort() vektörü mü? Elementi silmek? Öğeyi yakın komşularıyla karşılaştırır mısınız?

DÜZENLEME:

// erase the key and then insert-sort it 
auto iter = std::find(keys.begin(), keys.end(), key); 

keys.erase(iter); 
SortedInsert(keys, index, <cmp>); 

EDIT2: tarafından netleştirmek için böyle bir şey demek eleman silme takın konteyner diğer performans nedenleriyle

için bir vektör olması gerekiyor

Answer 1

Sen gibi bir şey kullanabilirsiniz Bu:

std::sort(myvector.begin(), myvector.end) 

iyi uygulanan s part of STL and it s düşünün.

Answer 2

Değerleri MAP yerine depolamayı düşünün.

Answer 3

Sıralanmış bir vektör içinde doğru yerde doğrudan bir öğe eklemek istiyorsanız, doğru yerde elemanı yerleştirmek için bir yineleyici almak için upper_bound kullanıp insert bunu geçmelidir:

vec.insert(std::upper_bound(vec.begin(), vec.end(), item), item); 

upper_bound'un hızlı olacağını (O(log n)) unutmayın, ancak ekleme işlemi, ekleme noktasından sonraki tüm öğeleri kaydırması gerektiğinden yavaş olabilir (O(n)).

Bununla birlikte, vektörün sonuna ekleyerek ve std::sort numaralı telefonu arayarak O(n log n) numaralı telefon numarası en kötüsüdür;

vec.insert(item); 
std::sort(vec.begin(), vec.end()); 

Diğer bir seçenek vektörünün sonuna eklenir ve daha düşük veya buna eşit olana kadar bir önceki elemanı ile kaydırmaya olabilir. Bu durumda, ek O(1) amortize edilir ve O(n) takas yapmak zorundasınız.

Maalesef, list ile karşılaşabileceğiniz gibi bir O(log n) çözümü olmayacaktır.

Answer 4

101010 cevabını kontrol edebilirsiniz. Bence çok açıklayıcı. Bunu vakanızla analiz edebilirsiniz.