Używanie std :: vector jako widoku surowej pamięci

71

Korzystam z zewnętrznej biblioteki, która w pewnym momencie daje mi surowy wskaźnik do tablicy liczb całkowitych i rozmiaru.

Teraz chciałbym użyć, std::vectoraby uzyskać dostęp i zmodyfikować te wartości w miejscu, zamiast uzyskiwać do nich dostęp za pomocą surowych wskaźników.

Oto sztuczny przykład, który wyjaśnia tę kwestię:

size_t size = 0;
int * data = get_data_from_library(size);   // raw data from library {5,3,2,1,4}, size gets filled in

std::vector<int> v = ????;                  // pseudo vector to be used to access the raw data

std::sort(v.begin(), v.end());              // sort raw data in place

for (int i = 0; i < 5; i++)
{
  std::cout << data[i] << "\n";             // display sorted raw data 
}

Oczekiwany wynik:

1
2
3
4
5

Powodem jest to, że muszę zastosować algorytmy z <algorithm>(sortowania, zamiany elementów itp.) Na tych danych.

Z drugiej strony zmiany rozmiaru tego wektora nigdy nie zostanie zmieniona, tak push_back, erase, insertnie są wymagane do pracy na tym wektorze.

Mógłbym zbudować wektor na podstawie danych z biblioteki, użyć zmodyfikować ten wektor i skopiować dane z powrotem do biblioteki, ale byłyby to dwie kompletne kopie, których chciałbym uniknąć, ponieważ zestaw danych mógłby być naprawdę duży.

Jabberwocky
źródło
16
To, czego szukasz, jest hipotetyczne std::vector_view, prawda?
眠 り ネ ロ ク
3
@ 眠 り ネ ロ ク tak, prawdopodobnie
Jabberwocky
5
To nie tak std::vectordziała.
Jesper Juhl
34
Standardowe algorytmy działają na iteratorach, a wskaźniki iteratorami. Nic Cię nie powstrzyma sort(arrayPointer, arrayPointer + elementCount);.
cmaster

Odpowiedzi:

60

Problem polega na tym, że std::vectortrzeba wykonać kopię elementów z tablicy, którą inicjujesz, ponieważ ma ona własność zawartych w niej obiektów.

Aby tego uniknąć, możesz użyć obiektu wycinka dla tablicy (tj. Podobnie do tego, co std::string_viewjest std::string). Możesz napisać własną array_viewimplementację szablonu klasy, której instancje są konstruowane przez przeniesienie surowego wskaźnika do pierwszego elementu tablicy i jej długości:

#include <cstdint>

template<typename T>
class array_view {
   T* ptr_;
   std::size_t len_;
public:
   array_view(T* ptr, std::size_t len) noexcept: ptr_{ptr}, len_{len} {}

   T& operator[](int i) noexcept { return ptr_[i]; }
   T const& operator[](int i) const noexcept { return ptr_[i]; }
   auto size() const noexcept { return len_; }

   auto begin() noexcept { return ptr_; }
   auto end() noexcept { return ptr_ + len_; }
};

array_viewnie przechowuje tablicy; po prostu trzyma wskaźnik na początku tablicy i jej długość. Dlatego array_viewobiekty są tanie w budowie i kopiowaniu.

Ponieważ array_viewzapewnia begin()i end()członków funkcje, można użyć standardowych algorytmów Library (np std::sort, std::find, std::lower_bound, itd.) Na jej temat:

#define LEN 5

auto main() -> int {
   int arr[LEN] = {4, 5, 1, 2, 3};

   array_view<int> av(arr, LEN);

   std::sort(av.begin(), av.end());

   for (auto const& val: av)
      std::cout << val << ' ';
   std::cout << '\n';
}

Wynik:

1 2 3 4 5

Zamiast tego użyj std::span(lub gsl::span)

Powyższa implementacja ujawnia koncepcję obiektów wycinanych . Jednak od C ++ 20 można bezpośrednio użyć std::spanzamiast tego. W każdym razie możesz używać gsl::spanod C ++ 14.

眠 り ネ ロ ク
źródło
Dlaczego oznaczyłeś metody jako wyjątki? Nie możesz w ogóle zagwarantować, że nie zostanie zgłoszony żaden wyjątek, prawda?
SonneXo
@moooeeeep Lepiej zostawić jakieś wyjaśnienie niż tylko link. Link może wygasnąć w przyszłości, podczas gdy często się zdarza.
Jason Liu
63

C ++ 20 std::span

Jeśli potrafisz używać C ++ 20, możesz użyć std::spanpary wskaźników i długości, która daje użytkownikowi widok na ciągłą sekwencję elementów. Jest jakiś swego rodzaju std::string_view, a jednocześnie oba std::spani std::string_viewsą non-posiadania poglądów, std::string_viewto widok tylko do odczytu.

Z dokumentów:

Rozpiętość szablonu klasy opisuje obiekt, który może odnosić się do ciągłej sekwencji obiektów z pierwszym elementem sekwencji w pozycji zero. Rozpiętość może mieć zasięg statyczny, w którym to przypadku liczba elementów w sekwencji jest znana i zakodowana w typie, lub zakres dynamiczny.

Więc działałyby następujące rzeczy:

#include <span>
#include <iostream>
#include <algorithm>

int main() {
    int data[] = { 5, 3, 2, 1, 4 };
    std::span<int> s{data, 5};

    std::sort(s.begin(), s.end());

    for (auto const i : s) {
        std::cout << i << "\n";
    }

    return 0;
}

Sprawdź to na żywo

Ponieważ std::spanjest to zasadniczo para wskaźnik-długość, możesz również użyć w następujący sposób:

size_t size = 0;
int *data = get_data_from_library(size);
std::span<int> s{data, size};

Uwaga: Nie wszystkie kompilatory obsługują std::span. Sprawdź obsługę kompilatora tutaj .

AKTUALIZACJA

Jeśli nie możesz używać C ++ 20, możesz użyć, gsl::spanktóra jest w zasadzie podstawową wersją standardu C ++ std::span.

Rozwiązanie C ++ 11

Jeśli jesteś ograniczony standardem C ++ 11, możesz spróbować wdrożyć własną prostą spanklasę:

template<typename T>
class span {
   T* ptr_;
   std::size_t len_;

public:
    span(T* ptr, std::size_t len) noexcept
        : ptr_{ptr}, len_{len}
    {}

    T& operator[](int i) noexcept {
        return *ptr_[i];
    }

    T const& operator[](int i) const noexcept {
        return *ptr_[i];
    }

    std::size_t size() const noexcept {
        return len_;
    }

    T* begin() noexcept {
        return ptr_;
    }

    T* end() noexcept {
        return ptr_ + len_;
    }
};

Sprawdź wersję C ++ 11 na żywo

Orzechówka
źródło
4
Możesz użyć gsl::spandla C ++ 14 i wyższych, jeśli twój kompilator nie implementujestd::span
Artyer
2
@Artyer Zaktualizuję swoją odpowiedź o to. Dzięki
NutCracker
29

Ponieważ biblioteka algorytmów współpracuje z iteratorami, możesz zachować tablicę.

Dla wskaźników i znanej długości tablicy

Tutaj możesz używać surowych wskaźników jako iteratorów. Obsługują wszystkie operacje obsługiwane przez iterator (przyrost, porównanie dla równości, wartość itp.):

#include <iostream>
#include <algorithm>

int *get_data_from_library(int &size) {
    static int data[] = {5,3,2,1,4}; 

    size = 5;

    return data;
}


int main()
{
    int size;
    int *data = get_data_from_library(size);

    std::sort(data, data + size);

    for (int i = 0; i < size; i++)
    {
        std::cout << data[i] << "\n";
    }
}

datawskazuje na pierwszy element tablicy jak iterator zwracany przez begin()i data + sizewskazuje na element za ostatnim elementem tablicy jak iterator zwracany przez end().

Do tablic

Tutaj możesz użyć std::begin()istd::end()

#include <iostream>
#include <algorithm>

int main()
{
    int data[] = {5,3,2,1,4};         // raw data from library

    std::sort(std::begin(data), std::end(data));    // sort raw data in place

    for (int i = 0; i < 5; i++)
    {
        std::cout << data[i] << "\n";   // display sorted raw data 
    }
}

Należy jednak pamiętać, że działa to tylko wtedy, gdy datanie rozpada się na wskaźnik, ponieważ wtedy brakuje informacji o długości.

churill
źródło
7
To jest właściwa odpowiedź. Algorytmy dotyczą zakresów . Kontenery (np. Std :: vector) są jednym ze sposobów zarządzania zasięgami, ale nie są jedynym sposobem.
Pete Becker
13

Możesz pobrać iteratory na surowe tablice i używać ich w algorytmach:

    int data[] = {5,3,2,1,4};
    std::sort(std::begin(data), std::end(data));
    for (auto i : data) {
        std::cout << i << std::endl;
    }

Jeśli pracujesz z surowymi wskaźnikami (ptr + rozmiar), możesz użyć następującej techniki:

    size_t size = 0;
    int * data = get_data_from_library(size);
    auto b = data;
    auto e = b + size;
    std::sort(b, e);
    for (auto it = b; it != e; ++it) {
        cout << *it << endl;
    }

UPD: Jednak powyższy przykład ma zły projekt. Biblioteka zwraca nam surowy wskaźnik i nie wiemy, gdzie przydzielony jest bufor podstawowy i kto powinien go zwolnić.

Zwykle program wywołujący udostępnia bufor dla funkcji wypełniania danych. W takim przypadku możemy wstępnie przydzielić wektor i użyć jego bufora:

    std::vector<int> v;
    v.resize(256); // allocate a buffer for 256 integers
    size_t size = get_data_from_library(v.data(), v.size());
    // shrink down to actual data. Note that no memory realocations or copy is done here.
    v.resize(size);
    std::sort(v.begin(), v.end());
    for (auto i : v) {
        cout << i << endl;
    }

Używając C ++ 11 lub nowszego, możemy nawet zrobić get_data_from_library (), aby zwrócić wektor. Dzięki operacjom przenoszenia nie będzie kopii pamięci.

PooSH
źródło
2
Następnie możesz użyć zwykłych wskaźników jako iteratorów:auto begin = data; auto end = data + size;
PooSH
Pytanie brzmi jednak, gdzie get_data_from_library()przydzielane są dane zwracane przez ? Może wcale nie powinniśmy tego zmieniać. Jeśli musimy przekazać bufor do biblioteki, możemy przydzielić wektor i przekazaćv.data()
PooSH
1
@PooSH dane są własnością biblioteki, ale można je zmienić bez ograniczeń (to właściwie jest sedno całego pytania). Tylko rozmiar danych nie może zostać zmieniony.
Jabberwocky
1
@Jabberwocky dodał lepszy przykład wykorzystania bufora wektorowego do wypełnienia danych.
PooSH
9

Nie możesz tego zrobić std::vectorbez zrobienia kopii. std::vectorjest właścicielem wskaźnika, który ma pod maską i przydziela miejsce za pośrednictwem udostępnionego alokatora.

Jeśli masz dostęp do kompilatora obsługującego C ++ 20, możesz użyć std :: span, który został zbudowany właśnie w tym celu. Zawija wskaźnik i rozmiar w „kontener”, który ma interfejs kontenera C ++.

Jeśli nie, możesz użyć gsl :: span, na której oparta była standardowa wersja.

Jeśli nie chcesz importować innej biblioteki, możesz to trywialnie zaimplementować samodzielnie, w zależności od tego, jaką funkcjonalność chcesz mieć.

NathanOliver
źródło
9

Teraz chciałbym użyć std :: vector, aby uzyskać dostęp i zmodyfikować te wartości w miejscu

Nie możesz. Nie po to std::vectorjest. std::vectorzarządza własnym buforem, który jest zawsze pobierany od alokatora. Nigdy nie przejmuje własności innego bufora (z wyjątkiem innego wektora tego samego typu).

Z drugiej strony nie musisz tego robić, ponieważ ...

Powodem jest to, że muszę zastosować algorytmy z (sortowania, zamiany elementów itp.) Na tych danych.

Algorytmy te działają na iteratorach. Wskaźnik jest iteratorem tablicy. Nie potrzebujesz wektora:

std::sort(data, data + size);

W przeciwieństwie do szablonów funkcyjnych <algorithm>, niektóre narzędzia, takie jak zakres-zakres, std::begin/ std::endi C ++ 20, nie działają jednak tylko z parą iteratorów, podczas gdy działają z kontenerami takimi jak wektory. Możliwe jest utworzenie klasy opakowania dla iteratora + rozmiaru, który zachowuje się jak zakres i działa z tymi narzędziami. C ++ 20 wprowadzi takie opakowanie do standardowej biblioteki: std::span.

eerorika
źródło
7

Oprócz innych dobrych sugestii dotyczących std::spanwejścia w a gsl:spantakże włączenie własnej (lekkiej) spanklasy do tego czasu jest już dość łatwe (nie krępuj się skopiować):

template<class T>
struct span {
    T* first;
    size_t length;
    span(T* first_, size_t length_) : first(first_), length(length_) {};
    using value_type = std::remove_cv_t<T>;//primarily needed if used with templates
    bool empty() const { return length == 0; }
    auto begin() const { return first; }
    auto end() const { return first + length; }
};

static_assert(_MSVC_LANG <= 201703L, "remember to switch to std::span");

Na szczególną uwagę zasługuje także biblioteka jeśli interesuje Cię bardziej ogólna koncepcja zakresu: https://www.boost.org/doc/libs/1_60_0/libs/range/doc/html/range/reference /utilities/iterator_range.html .

Koncepcje zasięgu pojawią się również w

darune
źródło
1
Co to jest using value_type = std::remove_cv_t<T>;za?
Jabberwocky
1
... i zapomniał konstruktora: span(T* first_, size_t length) : first(first), length(length) {};. Zredagowałem twoją odpowiedź.
Jabberwocky
@Jabberwocky Właśnie użyłem inicjalizacji agregacji. Ale konstruktor ma się dobrze.
darune
1
@eerorika Chyba masz rację, usunąłem wersje inne niż const
darune
1
Jest using value_type = std::remove_cv_t<T>;to potrzebne przede wszystkim, jeśli jest używane z programowaniem szablonów (w celu uzyskania wartości_typu „zakresu”). Jeśli chcesz tylko użyć iteratorów, możesz to pominąć / usunąć.
darune
6

Rzeczywiście mógłby niemal używać std::vectordo tego, nadużywając funkcji zwyczaj przydzielania powrócić wskaźnik do pamięci, którą chcesz wyświetlić. Nie byłoby to zagwarantowane przez normę do działania (wypełnienie, wyrównanie, inicjalizacja zwracanych wartości; trzeba będzie zadać sobie trud przy przypisywaniu początkowego rozmiaru, a dla osób niebędących prymitywami trzeba również zhakować konstruktorów ), ale w praktyce spodziewałbym się, że dostarczy wystarczająco dużo poprawek.

Nigdy tego nie rób. Jest brzydki, zaskakujący, hacky i niepotrzebny. Algorytmy biblioteki standardowej są już zaprojektowane do pracy zarówno z surowymi tablicami, jak i wektorami. Szczegółowe informacje na ten temat można znaleźć w innych odpowiedziach.

Sneftel
źródło
1
Hmm, tak, to może działać z vectorkonstruktorami, które przyjmują niestandardowe odwołanie Allocator jako argument konstruktora (nie tylko parametr szablonu). Sądzę, że potrzebujesz obiektu alokującego, który zawiera wartość wskaźnika środowiska wykonawczego, a nie jako parametr szablonu, w przeciwnym razie mógłby działać tylko dla adresów constexpr. Trzeba będzie uważać, aby nie pozwolić vectordomyślnym konstruować obiektów .resize()i zastępować istniejących danych; rozbieżność między właścicielem kontenera, takim jak wektor kontra zakres własności, jest ogromna, jeśli zaczniesz używać .push_back itp.
Peter Cordes
1
@PeterCordes Mam na myśli, nie zakopujmy lede - musiałbyś też zwariować. Moim zdaniem, najdziwniejszą rzeczą w tym pomyśle jest to, że interfejs alokatora zawiera constructmetodę, która byłaby wymagana ... Nie mogę myśleć, jakie niehackerskie przypadki użycia wymagałyby tego od umieszczenia nowego.
Sneftel
1
Oczywistym przypadkiem użycia jest uniknięcie marnowania czasu na konstruowanie elementów, które zamierzasz napisać w inny sposób, np. resize()Przed przekazaniem odwołania do czegoś, co chce użyć go jako czystego wyniku (np. Odczytu wywołania systemowego). W praktyce kompilatory często nie optymalizują tego zestawu ani nic takiego. Lub jeśli miałeś alokator, który używa calloc do uzyskania wstępnie wyzerowanej pamięci, możesz również uniknąć jej zabrudzenia, tak jak to głupie std::vector<int>domyślnie robi przy domyślnym konstruowaniu obiektów, które mają wzorzec zerowy. Patrz uwagi w en.cppreference.com/w/cpp/container/vector/vector
Peter Cordes
4

Jak zauważyli inni, std::vectormusi posiadać podstawową pamięć (brak bałaganu z niestandardowym alokatorem), więc nie można jej użyć.

Inni zalecili także rozpiętość c ++ 20, ale oczywiście wymaga to c ++ 20.

Polecam Span-lite rozpiętości. Cytując jego podtytuł:

span lite - Rozpiętość podobna do C ++ 20 dla C ++ 98, C ++ 11 i późniejszych w bibliotece z pojedynczym plikiem tylko w nagłówku

Zapewnia nieposiadający i modyfikowalny widok (jak można mutować elementy i ich kolejność, ale nie wstawiać ich), a jak mówi cytat, nie ma zależności i działa na większości kompilatorów.

Twój przykład:

#include <algorithm>
#include <cstddef>
#include <iostream>

#include <nonstd/span.hpp>

static int data[] = {5, 1, 2, 4, 3};

// For example
int* get_data_from_library()
{
  return data;
}

int main ()
{
  const std::size_t size = 5;

  nonstd::span<int> v{get_data_from_library(), size};

  std::sort(v.begin(), v.end());

  for (auto i = 0UL; i < v.size(); ++i)
  {
    std::cout << v[i] << "\n";
  }
}

Wydruki

1
2
3
4
5

To także ma dodany do góry nogami, gdy pewnego dnia zrobić przełącznik do C ++ 20, należy po prostu być w stanie zastąpić ten nonstd::spanz std::span.

Arghnews
źródło
3

Możesz użyć std::reference_wrapperdostępnego od C ++ 11:

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

int main()
{
    int src_table[] = {5, 4, 3, 2, 1, 0};

    std::vector< std::reference_wrapper< int > > dest_vector;

    std::copy(std::begin(src_table), std::end(src_table), std::back_inserter(dest_vector));
    // if you don't have the array defined just a pointer and size then:
    // std::copy(src_table_ptr, src_table_ptr + size, std::back_inserter(dest_vector));

    std::sort(std::begin(dest_vector), std::end(dest_vector));

    std::for_each(std::begin(src_table), std::end(src_table), [](int x) { std::cout << x << '\n'; });
    std::for_each(std::begin(dest_vector), std::end(dest_vector), [](int x) { std::cout << x << '\n'; });
}
Robert Andrzejuk
źródło
2
Wykonuje to kopię danych i właśnie tego chcę uniknąć.
Jabberwocky
1
@Jabberwocky To nie kopiuje danych. Ale to nie to, o co prosiłeś w pytaniu.
eerorika
@eerorika std::copy(std::begin(src_table), std::end(src_table), std::back_inserter(dest_vector));zdecydowanie wypełnia dest_vectorwartościami pobranymi z src_table(IOW dane są kopiowane dest_vector), więc nie dostałem twojego komentarza. Czy możesz wytłumaczyć?
Jabberwocky
@Jabberwocky nie kopiuje wartości. Wypełnia wektor opakowaniami referencyjnymi.
eerorika
3
@Jabberwocky jest bardziej nieefektywny w przypadku wartości całkowitych.
eerorika