C ++, skopiuj zestaw do wektora

146

Muszę skopiować std::setdo std::vector:

std::set <double> input;
input.insert(5);
input.insert(6);

std::vector <double> output;
std::copy(input.begin(), input.end(), output.begin()); //Error: Vector iterator not dereferencable

Gdzie jest problem?

Krokodyl Dundee
źródło
5
jest też assign()funkcja:output.assign(input.begin(), input.end());
Gene Bushuyev
twój wektor jest pusty. Istnieje wiele sposobów, aby temu zaradzić, chociaż ludzie wskazują poniżej.
AJG85
@Gene: assign () chce zarezerwować () niezbędną ilość pamięci z wyprzedzeniem. Użyje iteratorów wejściowych, aby określić, ile jest potrzebne, chyba że iteratory są ściśle InputIterator, w którym to przypadku pominie rezerwowanie i spowoduje ponowne przydzielenie dla każdej push_back (). Na drugim końcu spektrum BiderectionalIterators pozwoliłoby mu po prostu odjąć koniec - początek. Iteratory std :: set nie są jednak żadnymi z nich (są ForwardIterator) i jest to niefortunne: w tym przypadku assign () po prostu przejdzie cały zestaw, aby określić jego rozmiar - zła wydajność na dużych zestawach.
Siergiej Szewczenko

Odpowiedzi:

213

Musisz użyć back_inserter:

std::copy(input.begin(), input.end(), std::back_inserter(output));

std::copynie dodaje elementów do kontenera, do którego wstawiasz: nie może; ma tylko iterator do kontenera. Z tego powodu, jeśli przekazujesz iterator wyjściowy bezpośrednio do std::copy, musisz upewnić się, że wskazuje zakres, który jest co najmniej wystarczająco duży, aby pomieścić zakres wejściowy.

std::back_insertertworzy iterator danych wyjściowych, który wywołuje push_backkontener dla każdego elementu, więc każdy element jest wstawiany do kontenera. Alternatywnie możesz utworzyć wystarczającą liczbę elementów w elemencie, std::vectoraby pomieścić kopiowany zakres:

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

Lub możesz użyć std::vectorkonstruktora zakresu:

std::vector<double> output(input.begin(), input.end()); 
James McNellis
źródło
3
Cześć James, zamiast twojej linii std :: copy (pierwszy blok kodu w twojej odpowiedzi), czy nie mogłem po prostu zrobić output.insert(output.end(), input.begin(), input.end());zamiast tego?
user2015453
lub po prostu użyj wersji cbegin and cend: output.insert(output.cend(), input.cbegin(), input.cend());Co o tym sądzisz? Dzięki.
user2015453
2
Czy powinienem output.reserve (input.size ()); czy mogę mieć nadzieję, że jakiś kompilator zrobi to za mnie?
jimifiki
@jimifiki, brak nadziei, boję się.
Alexis Wilke,
Twoja pierwsza inicjalizacja wektora jest nieprawidłowa. Tworzysz tablicę input,size()pustych wpisów, a następnie dołączasz kolejne. Myślę, że masz zamiar użyć std::vector<double> output; output.reserve(input.size()); std::copy(...);.
Alexis Wilke,
121

Po prostu użyj konstruktora dla wektora, który przyjmuje iteratory:

std::set<T> s;

//...

std::vector v( s.begin(), s.end() );

Zakłada, że ​​chcesz tylko zawartość s in v, a przed skopiowaniem danych nie ma nic w v.

Jakub
źródło
42

oto inna alternatywa użycia vector::assign:

theVector.assign(theSet.begin(), theSet.end());
TeddyC
źródło
24

Nie zarezerwowałeś wystarczająco dużo miejsca w swoim obiekcie wektorowym, aby pomieścić zawartość zestawu.

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());
Marlon
źródło
1
To nie zasługuje na -1. W szczególności pozwala to wektorowi na wykonanie tylko jednej alokacji (ponieważ nie może określić odległości ustawionych iteratorów w O (1)), a jeśli nie został zdefiniowany dla wektora, aby wyzerował każdy element podczas konstruowania, mogłoby to warto pozwolić, aby kopia sprowadziła się do mempa. To ostatnie mogłoby być nadal opłacalne, gdyby implementacja wykryła, że ​​pętla w ktorach wektora może zostać usunięta. Oczywiście to pierwsze można też osiągnąć z rezerwą.
Fred Nurk,
Nie wiem Pozwól, że ci w tym pomogę.
wilhelmtell
Dałem ci -1, ale z mojej strony było to cienkie. Dokonaj niewielkiej zmiany, abym mógł cofnąć mój głos, a dam ci +1: jest to właściwie bardzo czyste rozwiązanie ze względu na właściwość polegającą na tym, że pierwsza nie działa.
Fred Foo
Dopiero co się zorientowałem, że jeśli samodzielnie edytuję odpowiedź, mogę zagłosować za. Zrobiłem to, dał ci +1 za alokację pamięci w pierwszej kolejności. Przepraszam!
Fred Foo
3

Myślę, że najbardziej efektywnym sposobem jest wstępne przydzielenie, a następnie umieszczenie elementów:

template <typename T>
std::vector<T> VectorFromSet(const std::set<T>& from)
{
    std::vector<T> to;
    to.reserve(from.size());

    for (auto const& value : from)
        to.emplace_back(value);

    return to;
}

W ten sposób będziemy wywoływać konstruktor kopiujący tylko dla każdego elementu, w przeciwieństwie do wywoływania najpierw konstruktora domyślnego, a następnie kopiowania operatora przypisania dla innych rozwiązań wymienionych powyżej. Więcej wyjaśnień poniżej.

  1. Można użyć back_inserter, ale wywoła on push_back () na wektorze ( https://en.cppreference.com/w/cpp/iterator/back_insert_iterator ). embrace_back () jest bardziej wydajna, ponieważ unika tworzenia tymczasowego przy użyciu push_back () . Nie jest to problem z trywialnie skonstruowanymi typami, ale będzie implikował wydajność dla nietrywialnie skonstruowanych typów (np. Std :: string).

  2. Musimy unikać konstruowania wektora z argumentem size, który powoduje, że wszystkie elementy są domyślnie konstruowane (za nic). Jak na przykład z rozwiązaniem używającym std :: copy () .

  3. I wreszcie, metoda vector :: assign () lub konstruktor pobierający zakres iteratora nie są dobrymi opcjami, ponieważ będą wywoływać std :: distance () (aby poznać liczbę elementów) na iteratorach set . Spowoduje to niepożądaną dodatkową iterację przez wszystkie elementy zestawu , ponieważ zestaw jest strukturą danych Binary Search Tree i nie implementuje iteratorów dostępu swobodnego.

Mam nadzieję, że to pomoże.

dshvets1
źródło
proszę dodać odniesienie do organu, dlaczego jest to szybkie i coś w rodzaju, dlaczego back_inserternie trzeba go używać
Tarick Welling
Dodano więcej wyjaśnień w odpowiedzi.
dshvets1
1

std::copynie można używać do wkładania do pustego pojemnika. Aby to zrobić, musisz użyć insert_iterator w następujący sposób:

std::set<double> input;
input.insert(5);
input.insert(6);

std::vector<double> output;
std::copy(input.begin(), input.end(), inserter(output, output.begin())); 
Bradley Swain
źródło
3
To kończy się niepowodzeniem przy pierwszej ponownej alokacji wektora: iterator z output.begin () zostaje unieważniony.
Fred Nurk