Verwenden von std :: vector als Ansicht des Rohspeichers

71

Ich verwende eine externe Bibliothek, die mir irgendwann einen unformatierten Zeiger auf ein Array von Ganzzahlen und eine Größe gibt.

Jetzt möchte ich auf std::vectordiese Werte zugreifen und sie ändern, anstatt mit rohen Zeigern darauf zuzugreifen.

Hier ist ein künstliches Beispiel, das den Punkt erklärt:

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 
}

Erwartete Ausgabe:

1
2
3
4
5

Der Grund ist, dass ich Algorithmen aus <algorithm>(Sortieren, Austauschen von Elementen usw.) auf diese Daten anwenden muss .

Auf der anderen Seite würde die Größe dieses Vektors ändert nie, so geändert werden push_back, erase, insertnicht auf diesem Vektor zur Arbeit benötigt.

Ich könnte einen Vektor basierend auf den Daten aus der Bibliothek erstellen, diesen Vektor ändern und die Daten zurück in die Bibliothek kopieren, aber das wären zwei vollständige Kopien, die ich vermeiden möchte, da der Datensatz sehr groß sein könnte.

Jabberwocky
quelle
16
Was Sie suchen, ist eine Hypothese std::vector_view, nicht wahr?
ク り ネ ロ
3
@ 眠 り ネ ロ ク ja, wahrscheinlich
Jabberwocky
5
So std::vectorfunktioniert das nicht .
Jesper Juhl
34
Standardalgorithmen arbeiten mit Iteratoren, und Zeiger sind Iteratoren. Nichts hindert dich daran sort(arrayPointer, arrayPointer + elementCount);.
cmaster

Antworten:

60

Das Problem besteht darin std::vector, dass eine Kopie der Elemente aus dem Array erstellt werden muss, mit dem Sie es initialisieren, da es den Besitz der darin enthaltenen Objekte besitzt.

Um dies zu vermeiden, können Sie ein Slice- Objekt für ein Array verwenden (dh ähnlich dem, was zu tun std::string_viewist std::string). Sie können Ihre eigene array_viewKlassenvorlagenimplementierung schreiben , deren Instanzen erstellt werden, indem Sie einen Rohzeiger auf das erste Element eines Arrays und die Arraylänge verwenden:

#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_viewspeichert kein Array; Es enthält nur einen Zeiger auf den Anfang des Arrays und die Länge dieses Arrays. Daher sind array_viewObjekte billig zu konstruieren und zu kopieren.

Da array_viewdie liefert begin()und end()Member - Funktionen können Sie die Standardbibliothek Algorithmen (zB verwenden std::sort, std::find, std::lower_bound, etc.) darauf:

#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';
}

Ausgabe:

1 2 3 4 5

Verwenden Sie stattdessen std::span(oder gsl::span)

Die obige Implementierung macht das Konzept hinter Slice-Objekten sichtbar . Seit C ++ 20 können Sie jedoch direkt verwenden std::span. In jedem Fall können Sie gsl::spanseit C ++ 14 verwenden.

眠 り ネ ロ ク
quelle
Warum haben Sie die Methoden als noexcept markiert? Sie können nicht garantieren, dass keine Ausnahme ausgelöst wird, oder?
SonneXo
@moooeeeep Es ist besser, eine Erklärung zu hinterlassen als nur einen Link. Der Link könnte in Zukunft abgelaufen sein, obwohl ich gesehen habe, dass dies viel passiert ist.
Jason Liu
63

C ++ 20er Jahre std::span

Wenn Sie C ++ 20 verwenden können, können Sie std::spanein Zeiger-Längen-Paar verwenden, das dem Benutzer einen Blick auf eine zusammenhängende Folge von Elementen bietet. Es ist eine Art a std::string_view, und während beide std::spanund std::string_viewnicht besitzende Ansichten sind,std::string_view ist es eine schreibgeschützte Ansicht.

Aus den Dokumenten:

Der Klassenvorlagenbereich beschreibt ein Objekt, das sich auf eine zusammenhängende Folge von Objekten beziehen kann, wobei sich das erste Element der Folge an Position Null befindet. Eine Spanne kann entweder eine statische Ausdehnung haben. In diesem Fall ist die Anzahl der Elemente in der Sequenz bekannt und im Typ codiert, oder eine dynamische Ausdehnung.

Also würde folgendes funktionieren:

#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;
}

Hör zu live aus

Da std::spanes sich im Grunde genommen um ein Zeiger-Längen-Paar handelt, können Sie es auch folgendermaßen verwenden:

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

Hinweis: Nicht alle Compiler unterstützen std::span. Überprüfen Sie Compiler - Unterstützung hier .

AKTUALISIEREN

Wenn Sie C ++ 20 nicht verwenden können, können Sie gsl::spandie Basisversion der C ++ - Standards verwenden std::span.

C ++ 11-Lösung

Wenn Sie auf den C ++ 11-Standard beschränkt sind, können Sie versuchen, Ihre eigene einfache spanKlasse zu implementieren :

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_;
    }
};

Testen Sie die C ++ 11-Version live

Nussknacker
quelle
4
Sie können gsl::spanfür C ++ 14 und höher verwenden, wenn Ihr Compiler nicht implementiertstd::span
Artyer
2
@Artyer Ich werde meine Antwort damit aktualisieren. Danke
NutCracker
29

Da die Algorithmusbibliothek mit Iteratoren arbeitet, können Sie das Array behalten.

Für Zeiger und bekannte Arraylänge

Hier können Sie Rohzeiger als Iteratoren verwenden. Sie unterstützen alle Operationen, die ein Iterator unterstützt (Inkrement, Vergleich auf Gleichheit, Wert von usw.):

#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";
    }
}

datazeigt auf das dirst-Array-Mitglied wie ein von zurückgegebener Iterator begin()und data + sizezeigt auf das Element nach dem letzten Element des Arrays wie ein von zurückgegebener Iterator end().

Für Arrays

Hier können Sie std::begin()und verwendenstd::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 
    }
}

Beachten Sie jedoch, dass dies nur funktioniert, wenn dataes nicht zu einem Zeiger zerfällt, da dann Längeninformationen fehlen.

churill
quelle
7
Das ist die richtige Antwort. Algorithmen gelten für Bereiche . Container (z. B. std :: vector) sind eine Möglichkeit, Bereiche zu verwalten, aber nicht die einzige.
Pete Becker
13

Sie können Iteratoren für Raw-Arrays abrufen und in Algorithmen verwenden:

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

Wenn Sie mit rohen Zeigern (ptr + Größe) arbeiten, können Sie die folgende Technik verwenden:

    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: Das obige Beispiel ist jedoch von schlechtem Design. Die Bibliothek gibt uns einen Rohzeiger zurück und wir wissen nicht, wo der zugrunde liegende Puffer zugeordnet ist und wer ihn freigeben soll.

Normalerweise stellt der Anrufer einen Puffer für die Funktion zum Füllen der Daten bereit. In diesem Fall können wir den Vektor vorab zuordnen und seinen zugrunde liegenden Puffer verwenden:

    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;
    }

Bei Verwendung von C ++ 11 oder höher können wir sogar get_data_from_library () erstellen, um einen Vektor zurückzugeben. Dank Verschiebungsvorgängen wird keine Speicherkopie erstellt.

PooSH
quelle
2
Dann können Sie reguläre Zeiger als Iteratoren verwenden:auto begin = data; auto end = data + size;
PooSH
Die Frage ist jedoch, wo die von zurückgegebenen Daten get_data_from_library()zugeordnet werden. Vielleicht sollen wir es gar nicht ändern. Wenn wir einen Puffer an die Bibliothek übergeben müssen, können wir Vektor zuweisen und übergebenv.data()
PooSH
1
@PooSH Die Daten gehören der Bibliothek, können jedoch ohne Einschränkung geändert werden (das ist eigentlich der Punkt der gesamten Frage). Nur die Größe der Daten kann nicht geändert werden.
Jabberwocky
1
@Jabberwocky hat ein besseres Beispiel hinzugefügt, wie der zugrunde liegende Puffer des Vektors zum Ausfüllen der Daten verwendet wird.
PooSH
9

Sie können dies nicht mit a tun, std::vectorohne eine Kopie zu erstellen. std::vectorbesitzt den Zeiger unter der Haube und weist Platz durch den bereitgestellten Allokator zu.

Wenn Sie Zugriff auf einen Compiler haben, der C ++ 20 unterstützt, können Sie std :: span verwenden, das genau für diesen Zweck erstellt wurde. Es verpackt einen Zeiger und eine Größe in einen "Container" mit der C ++ - Containerschnittstelle.

Wenn nicht, können Sie gsl :: span verwenden , auf dem die Standardversion basiert.

Wenn Sie keine andere Bibliothek importieren möchten, können Sie dies trivial selbst implementieren, je nachdem, welche Funktionen Sie benötigen.

NathanOliver
quelle
9

Jetzt möchte ich std :: vector verwenden, um auf diese Werte zuzugreifen und sie zu ändern

Du kannst nicht. Dafür ist nicht da std::vector. std::vectorverwaltet seinen eigenen Puffer, der immer von einem Allokator erfasst wird. Es übernimmt niemals den Besitz eines anderen Puffers (außer von einem anderen Vektor des gleichen Typs).

Auf der anderen Seite müssen Sie auch nicht, weil ...

Der Grund ist, dass ich Algorithmen aus (Sortieren, Austauschen von Elementen usw.) auf diese Daten anwenden muss.

Diese Algorithmen arbeiten mit Iteratoren. Ein Zeiger ist ein Iterator für ein Array. Sie brauchen keinen Vektor:

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

Im Gegensatz zu Funktionsvorlagen in funktionieren <algorithm>einige Tools wie range-for-, std::begin/ std::endund C ++ 20-Bereiche nicht nur mit zwei Iteratoren, sondern auch mit Containern wie Vektoren. Es ist möglich, eine Wrapper-Klasse für Iterator + Größe zu erstellen, die sich wie ein Bereich verhält und mit diesen Tools funktioniert. C ++ 20 führt einen solchen Wrapper in die Standardbibliothek ein : std::span.

eerorika
quelle
7

Neben dem anderen guten Vorschlag std::span, in und bis dahin gsl:spanauch eine eigene (leichte) spanKlasse einzuschließen, ist das schon einfach genug (zögern Sie nicht zu kopieren):

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");

Besonders hervorzuheben ist auch die Boost-Range-Bibliothek wenn Sie an dem allgemeineren Range-Konzept interessiert sind: https://www.boost.org/doc/libs/1_60_0/libs/range/doc/html/range/reference /utilities/iterator_range.html .

Bereichskonzepte werden auch in

Darune
quelle
1
Wofür ist das using value_type = std::remove_cv_t<T>;?
Jabberwocky
1
... und du hast den Konstruktor vergessen : span(T* first_, size_t length) : first(first), length(length) {};. Ich habe deine Antwort bearbeitet.
Jabberwocky
@Jabberwocky Ich habe gerade die Aggregatinitialisierung verwendet. Aber Konstruktor ist in Ordnung.
Darune
1
@eerorika Ich denke du hast recht, ich habe die nicht
konstanten
1
Das using value_type = std::remove_cv_t<T>;wird hauptsächlich benötigt, wenn es mit der Vorlagenprogrammierung verwendet wird (um den value_type eines 'Bereichs' zu erhalten). Wenn Sie nur die Iteratoren verwenden möchten, können Sie diese überspringen / entfernen.
Darune
6

Du könntest es tatsächlichstd::vector dies fast nutzen , indem Sie die benutzerdefinierte Zuordnungsfunktion missbrauchen, um einen Zeiger auf den Speicher zurückzugeben, den Sie anzeigen möchten. Der Standard garantiert nicht, dass dies funktioniert (Auffüllen, Ausrichten, Initialisieren der zurückgegebenen Werte; Sie müssten sich beim Zuweisen der Anfangsgröße Mühe geben, und bei Nicht-Grundelementen müssten Sie auch Ihre Konstruktoren hacken ), aber in der Praxis würde ich erwarten, dass es genug Optimierungen gibt.

Mach das niemals. Es ist hässlich, überraschend, hackig und unnötig. Die Algorithmen der Standardbibliothek sind bereits so konzipiert, dass sie sowohl mit Raw-Arrays als auch mit Vektoren funktionieren. Einzelheiten dazu finden Sie in den anderen Antworten.

Sneftel
quelle
1
Hmm, ja, das könnte mit den vectorKonstruktoren funktionieren , die eine benutzerdefinierte Allocator-Referenz als Konstruktorargument verwenden (nicht nur als Vorlagenparameter). Ich denke, Sie benötigen ein Allokatorobjekt, das den Laufzeitzeigerwert enthält, nicht als Vorlagenparameter, da es sonst nur für constexpr-Adressen funktionieren könnte. Sie müssen darauf achten, dass vectorObjekte nicht standardmäßig erstellt .resize()und vorhandene Daten überschrieben werden. Die Nichtübereinstimmung zwischen einem besitzenden Container wie Vektor und einer nicht besitzenden Spanne ist sehr groß, wenn Sie .push_back usw. verwenden
Peter Cordes
1
@PeterCordes Ich meine, lass uns die Lede nicht begraben - du müsstest auch verrückt sein. Meiner Meinung nach ist das Seltsamste an der Idee, dass die Allokator-Schnittstelle die constructMethode enthält, die erforderlich wäre ... Ich kann mir nicht vorstellen, welche nicht-hackigen Anwendungsfälle dies über eine neue Platzierung erfordern würden.
Sneftel
1
Der offensichtliche Anwendungsfall besteht darin, keine Zeit damit zu verschwenden, Elemente zu konstruieren, die Sie auf eine andere Weise schreiben möchten, z. B. resize()bevor Sie einen Verweis auf etwas übergeben, das ihn als reine Ausgabe verwenden möchte (z. B. einen Systemaufruf zum Lesen). In der Praxis optimieren Compiler dieses Memset oder was auch immer oft nicht. Oder wenn Sie einen Allokator hatten, der Calloc verwendet, um Speicher vor Null zu erhalten, können Sie auch vermeiden, ihn zu verschmutzen, wie es dumm std::vector<int>ist, wenn Sie standardmäßig Objekte mit einem Bitmuster von Null konstruieren. Siehe Anmerkungen in en.cppreference.com/w/cpp/container/vector/vector
Peter Cordes
4

Wie andere darauf hingewiesen haben, std::vector muss der zugrunde liegende Speicher vorhanden sein (ohne mit einem benutzerdefinierten Allokator herumzuspielen), sodass er nicht verwendet werden kann.

Andere haben auch die Spanne von c ++ 20 empfohlen, dies erfordert jedoch offensichtlich c ++ 20.

Ich würde die Span-Lite- Spanne empfehlen . Um es mit Untertiteln zu zitieren:

span lite - Ein C ++ 20-ähnlicher Bereich für C ++ 98, C ++ 11 und höher in einer Nur-Datei-Header-Bibliothek

Es bietet eine nicht besitzende und veränderbare Ansicht (wie in können Sie Elemente und ihre Reihenfolge mutieren, aber nicht einfügen) und hat, wie das Zitat sagt, keine Abhängigkeiten und funktioniert auf den meisten Compilern.

Ihr Beispiel:

#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";
  }
}

Druckt

1
2
3
4
5

Dies hat auch die zusätzlichen Kopf , wenn Sie einen Tag Schalter c tun ++ 20 sollten Sie nur in der Lage sein , dies zu ersetzen nonstd::spanmit std::span.

Arghnews
quelle
3

Sie können ein std::reference_wrapperseit C ++ 11 verfügbares verwenden:

#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
quelle
2
Dadurch wird eine Kopie der Daten erstellt, und genau das möchte ich vermeiden.
Jabberwocky
1
@Jabberwocky Dies kopiert die Daten nicht. Aber es ist auch nicht das, wonach Sie in der Frage gefragt haben.
Eerorika
@eerorika std::copy(std::begin(src_table), std::end(src_table), std::back_inserter(dest_vector));füllt das definitiv dest_vectormit den Werten aus src_table(IOW die Daten werden kopiert dest_vector), also habe ich Ihren Kommentar nicht erhalten. Könntest du erklären?
Jabberwocky
@Jabberwocky kopiert keine Werte. Es füllt den Vektor mit Referenz-Wrappern.
Eerorika
3
@Jabberwocky es ist mehr ineffizient bei ganzzahligen Werten.
Eerorika