Czy istnieje klasa sorted_vector, która obsługuje funkcję insert() itd.?

Question

Często skuteczniej jest używać posortowanego std::vector zamiast std::set. Czy ktoś zna bibliotekę klasy sorted_vector, która zasadniczo ma podobny interfejs do std::set, ale wstawia elementy do posortowanego wektora (tak, że nie ma żadnych duplikatów), używa wyszukiwania binarnego do elementów find itd.?

Wiem, że nie jest trudno napisać, ale prawdopodobnie lepiej nie marnować czasu i wykorzystać istniejącą implementację.

Aktualizacja: Powodem użyć sortowania wektor zamiast zestawu wynosi: Jeśli masz setki tysięcy małych zestawów, które zawierają tylko 10 lub tak członków każda, to jest więcej pamięci efektywne po prostu użyć posortowane wektory zamiast.

Answer 1

Myślę, że nie ma adaptera "sortowanego kontenera" w STL, ponieważ istnieją już odpowiednie pojemniki asocjacyjne do przechowywania posortowanych rzeczy, które byłyby odpowiednie w prawie wszystkich przypadkach. Szczerze mówiąc, jedynym powodem, dla którego mogę myśleć z góry mojej głowy, że mam posortowany kontener vector<> może być współdziałanie z funkcjami C, które oczekują posortowanej tablicy. Oczywiście, może czegoś brakuje.

Jeśli czujesz, że klasyfikowane vector<> byłoby bardziej odpowiednie dla swoich potrzeb (zdając sobie sprawę z niedostatków wstawiania elementów do wektora), oto implementacja na Code Project:

• An STL compliant sorted vector By Martin Holzherr

Nigdy go nie używałem, więc nie mogę ręczyć za to (lub jego licencję - jeśli jest określona). Ale szybkie przeczytanie artykułu i wygląda na to, że autor przynajmniej dołożył starań, aby adapter kontenera miał odpowiedni interfejs STL.

Wygląda na to, że warto się bliżej przyjrzeć.

Answer 2

Powodem, dla którego taki kontener nie jest częścią standardowej biblioteki jest to, że byłby on nieefektywny. Używanie wektora do przechowywania oznacza, że ​​obiekty muszą być przenoszone, jeśli coś jest wstawione w środek wektora. Robiąc to na wstawianie każdego staje się niepotrzebnie drogie. (Średnio połowa obiekty będą musiały być przeniesione do każdej wstawiania. To dość kosztowne)

Jeśli chcesz posortowaną wektor, to prawdopodobnie lepiej wstawić wszystkie elementy, a następnie zadzwonić std::sort()raz po wstawki.

Answer 3

Loki z firmy Alexandresu mają posortowaną implementację wektorową, jeśli nie chcesz przejść przez rzekomy wysiłek związany z toczeniem się.

http://loki-lib.sourceforge.net/html/a00025.html

Answer 4

Jeśli zdecydujesz się toczyć własną rękę, możesz również sprawdzić doładowania: ublas. W szczególności:

#include <boost/numeric/ublas/vector_sparse.hpp> 

i spójrz na element coordinate_vector, który implementuje wektor wartości i indeksów. Ta struktura danych obsługuje wstawianie O (1) (naruszenie sortowania), ale następnie sortuje na żądanie Omegę (n log n). Oczywiście, gdy zostanie posortowane, odnośniki to O (logn). Jeśli część tablicy jest posortowana, algorytm rozpoznaje to i sortuje tylko nowo dodane elementy, a następnie przeprowadza scalanie w miejscu.Jeśli zależy Ci na wydajności, to prawdopodobnie najlepsze, co możesz zrobić.

Answer 5

Boost.Container flat_set

Boost.Container flat_ [Multi] mapa/zestaw pojemniki są sortowane wektor oparty na bazie kontenerów asocjacyjnych Austern i wytycznych Alexandrescu użytkownika. Te uporządkowane kontenery wektorowe również zyskały ostatnio dzięki dodaniu semantyki ruchu do C++, znacznie przyspieszając czas wstawiania i kasowania. Płaskie asocjacyjne pojemniki mają następujące atrybuty:

• Szybsze wyszukiwanie niż standardowych kontenerów asocjacyjnych
• Znacznie szybciej niż iteracji standardowych kontenerów asocjacyjnych.
• Mniejsze zużycie pamięci dla małych obiektów (i dla dużych obiektów, jeżeli jest stosowany shrink_to_fit)
• Zwiększona wydajność pamięci podręcznej (dane są przechowywane w pamięci ciągłej)
• niestabilnego iteratory (iteratory są unieważniane przy wkładaniu i usuwanie elementów)
• dla copyable i nieruchomej typów wartości nie mogą być przechowywane
• słabszych bezpieczeństwa wyjątek niż standardowe pojemniki asocjacyjne (kopia/konstruktory ruch może wyrzucić podczas zmiany wartości w wymazywania i insercje)
• Wolniej włożenie i usunięcie ponad standardowy asocjacyjny pojemniki (specjalnie dla non-ruchomych typów)

Live demo:

#include <boost/container/flat_set.hpp> 
#include <iostream> 
#include <ostream> 

using namespace std; 

int main() 
{ 
    boost::container::flat_set<int> s; 
    s.insert(1); 
    s.insert(2); 
    s.insert(3); 
    cout << (s.find(1)!=s.end()) << endl; 
    cout << (s.find(4)!=s.end()) << endl; 
} 

---

jalf: Jeśli chcesz posortowaną wektor, to prawdopodobnie lepiej wstawić wszystkie elementy, a następnie wywołaj std :: sort() raz po wstawieniu.

boost::flat_set można zrobić automatycznie:

template<typename InputIterator> 
flat_set(InputIterator first, InputIterator last, 
     const Compare & comp = Compare(), 
     const allocator_type & a = allocator_type()); 

Wpływ: Konstrukty pustego zestawu przy użyciu określonego obiektu porównawczych i przydzielania i wstawienie elementów z przedziału [pierwsze, ostatni) .

Złożoność: liniowa w N, jeśli zakres [pierwsze, ostatnia) jest już posortowana użyciem Comp inaczej N * log (N), gdzie N jest ostatnim - pierwszy.

Answer 6

Here to moja klasa sorted_vector, której używam od lat w kodzie produkcyjnym. Ma przeciążenia, aby umożliwić korzystanie z niestandardowego predykatu. Używałem go do pojemników ze wskaźnikami, które mogą być naprawdę dobrym rozwiązaniem w wielu przypadkach użycia.