Utilisation de std :: vector comme vue sur la mémoire brute

71

J'utilise une bibliothèque externe qui à un moment donné me donne un pointeur brut vers un tableau d'entiers et une taille.

Maintenant, j'aimerais utiliser std::vectorpour accéder et modifier ces valeurs en place, plutôt que d'y accéder avec des pointeurs bruts.

Voici un exemple explicatif qui explique le point:

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 
}

Production attendue:

1
2
3
4
5

La raison en est que je dois appliquer des algorithmes à partir de <algorithm>(tri, échange d'éléments, etc.) sur ces données.

D'autre part changer la taille de ce vecteur ne serait jamais changé, donc push_back, erase, insertne sont pas tenus de travailler sur ce vecteur.

Je pourrais construire un vecteur basé sur les données de la bibliothèque, utiliser modifier ce vecteur et copier les données dans la bibliothèque, mais ce serait deux copies complètes que j'aimerais éviter car l'ensemble de données pourrait être très volumineux.

Jabberwocky
la source
16
Ce que vous recherchez est hypothétique std::vector_view, n'est-ce pas?
眠 り ネ ロ ク
3
@ 眠 り ネ ロ ク oui, probablement
Jabberwocky
5
Ce n'est pas comme ça que ça std::vectormarche.
Jesper Juhl
34
Les algorithmes standard fonctionnent sur les itérateurs et les pointeurs sont des itérateurs. Rien ne vous empêche de le faire sort(arrayPointer, arrayPointer + elementCount);.
cmaster - réintègre monica le

Réponses:

60

Le problème est qu'il std::vectorfaut faire une copie des éléments du tableau avec lequel vous l'initialisez car il a la propriété des objets qu'il contient.

Pour éviter cela, vous pouvez utiliser un objet tranche pour un tableau (c'est-à-dire similaire à ce qui std::string_viewest destiné std::string). Vous pouvez écrire votre propre array_viewimplémentation de modèle de classe dont les instances sont construites en prenant un pointeur brut vers le premier élément d'un tableau et la longueur du tableau:

#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_viewne stocke pas de tableau; il contient juste un pointeur sur le début du tableau et la longueur de ce tableau. Par conséquent, les array_viewobjets sont bon marché à construire et à copier.

Depuis array_viewfournit les begin()et end()fonctions membres, vous pouvez utiliser les algorithmes de la bibliothèque standard (par exemple, std::sort, std::find, std::lower_bound, etc.) sur elle:

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

Production:

1 2 3 4 5

Utilisez std::span(ou gsl::span) à la place

L'implémentation ci-dessus expose le concept derrière les objets tranche . Cependant, depuis C ++ 20, vous pouvez utiliser directement à la std::spanplace. Dans tous les cas, vous pouvez utiliser gsl::spandepuis C ++ 14.

眠 り ネ ロ ク
la source
Pourquoi avez-vous marqué les méthodes comme non sauf? Vous ne pouvez pas garantir du tout qu'aucune exception n'est levée, n'est-ce pas?
SonneXo
@moooeeeep Il vaut mieux laisser une explication qu'un simple lien. Le lien pourrait expirer à l'avenir alors que j'ai vu que cela arrivait souvent.
Jason Liu
63

C ++ 20's std::span

Si vous pouvez utiliser C ++ 20, vous pouvez utiliser std::spanune paire pointeur-longueur qui donne à l'utilisateur une vue dans une séquence d'éléments contigus. Il s'agit d'une sorte de std::string_view, et bien que les deux std::spanet ne std::string_viewsoient pas des vues propriétaires, std::string_viewc'est une vue en lecture seule.

De la documentation:

L'étendue du modèle de classe décrit un objet qui peut faire référence à une séquence contiguë d'objets avec le premier élément de la séquence à la position zéro. Une étendue peut avoir une étendue statique, auquel cas le nombre d'éléments de la séquence est connu et codé dans le type, ou une étendue dynamique.

Donc, ce qui suit fonctionnerait:

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

Découvrez-le en direct

Comme il std::spans'agit essentiellement d'une paire pointeur-longueur, vous pouvez également utiliser de la manière suivante:

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

Remarque: tous les compilateurs ne prennent pas en charge std::span. Vérifiez le support du compilateur ici .

MISE À JOUR

Si vous n'êtes pas en mesure d'utiliser C ++ 20, vous pouvez utiliser gsl::spanqui est essentiellement la version de base de la norme C ++ std::span.

Solution C ++ 11

Si vous êtes limité au standard C ++ 11, vous pouvez essayer d'implémenter votre propre spanclasse simple :

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

Découvrez la version C ++ 11 en direct

Casse Noisette
la source
4
Vous pouvez utiliser gsl::spanpour C ++ 14 et supérieur si votre compilateur ne met pas en œuvrestd::span
Artyer
2
@Artyer je mettrai à jour ma réponse avec ceci. Merci
NutCracker
29

Puisque la bibliothèque d'algorithmes fonctionne avec les itérateurs, vous pouvez conserver le tableau.

Pour les pointeurs et la longueur de tableau connue

Ici, vous pouvez utiliser des pointeurs bruts comme itérateurs. Ils supportent toutes les opérations supportées par un itérateur (incrément, comparaison pour égalité, valeur de, etc ...):

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

datapointe vers le premier membre du tableau comme un itérateur renvoyé par begin()et data + sizepointe vers l'élément après le dernier élément du tableau comme un itérateur renvoyé par end().

Pour les tableaux

Ici, vous pouvez utiliser std::begin()etstd::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 
    }
}

Mais gardez à l'esprit que cela ne fonctionne que s'il datane se désintègre pas en un pointeur, car les informations de longueur manquent.

churill
la source
7
C'est la bonne réponse. Les algorithmes s'appliquent aux plages . Les conteneurs (par exemple, std :: vector) sont une façon de gérer les plages, mais ce n'est pas la seule.
Pete Becker
13

Vous pouvez obtenir des itérateurs sur des tableaux bruts et les utiliser dans des algorithmes:

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

Si vous travaillez avec des pointeurs bruts (ptr + taille), vous pouvez utiliser la technique suivante:

    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: Cependant, l'exemple ci-dessus est de mauvaise conception. La bibliothèque nous renvoie un pointeur brut et nous ne savons pas où le tampon sous-jacent est alloué et qui est censé le libérer.

Habituellement, l'appelant fournit un tampon pour que la fonction remplisse les données. Dans ce cas, nous pouvons préallouer le vecteur et utiliser son tampon sous-jacent:

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

Lorsque vous utilisez C ++ 11 ou supérieur, nous pouvons même faire get_data_from_library () pour retourner un vecteur. Grâce aux opérations de déplacement, il n'y aura pas de copie mémoire.

PooSH
la source
2
Ensuite, vous pouvez utiliser des pointeurs réguliers comme itérateurs:auto begin = data; auto end = data + size;
PooSH
Cependant, la question est de savoir où les données renvoyées par get_data_from_library()sont allouées? Peut-être que nous ne sommes pas censés le changer du tout. Si nous devons passer un tampon à la bibliothèque, alors nous pouvons allouer le vecteur et passerv.data()
PooSH
1
@PooSH les données appartiennent à la bibliothèque, mais elles peuvent être modifiées sans restriction (c'est en fait le point de toute la question). Seule la taille des données ne peut pas être modifiée.
Jabberwocky
1
@Jabberwocky a ajouté un meilleur exemple de la façon d'utiliser le tampon sous-jacent du vecteur pour remplir les données.
PooSH
9

Vous ne pouvez pas le faire avec un std::vectorsans faire de copie. std::vectorpossède le pointeur qu'il a sous le capot et alloue de l'espace via l'allocateur fourni.

Si vous avez accès à un compilateur qui prend en charge C ++ 20, vous pouvez utiliser std :: span qui a été construit exactement à cette fin. Il encapsule un pointeur et une taille dans un "conteneur" qui a l'interface de conteneur C ++.

Sinon, vous pouvez utiliser gsl :: span qui est la base de la version standard.

Si vous ne souhaitez pas importer une autre bibliothèque, vous pouvez l'implémenter trivialement vous-même en fonction de toutes les fonctionnalités que vous souhaitez avoir.

NathanOliver
la source
9

Maintenant, je voudrais utiliser std :: vector pour accéder et modifier ces valeurs en place

Vous ne pouvez pas. Ce n'est pas pour ça std::vector. std::vectorgère son propre tampon, qui est toujours acquis à partir d'un allocateur. Il ne prend jamais possession d'un autre tampon (sauf d'un autre vecteur du même type).

D'un autre côté, vous n'avez pas non plus besoin de le faire parce que ...

La raison en est que je dois appliquer des algorithmes à partir de (tri, échange d'éléments, etc.) sur ces données.

Ces algorithmes fonctionnent sur des itérateurs. Un pointeur est un itérateur d'un tableau. Vous n'avez pas besoin d'un vecteur:

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

Contrairement aux modèles de fonctions dans <algorithm>, certains outils tels que range-for, std::begin/ std::endet C ++ 20 ne fonctionnent pas avec seulement une paire d'itérateurs, alors qu'ils fonctionnent avec des conteneurs tels que des vecteurs. Il est possible de créer une classe wrapper pour itérateur + taille qui se comporte comme une plage et fonctionne avec ces outils. C ++ 20 introduiront une enveloppe dans la bibliothèque standard: std::span.

eerorika
la source
7

En plus de l'autre bonne suggestion de std::spanvenir en et gsl:span, y compris votre propre spanclasse (légère) jusque-là est déjà assez facile (n'hésitez pas à copier):

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

Nous tenons à souligner également la bibliothèque de gamme boost si vous êtes intéressé par le concept de gamme plus générique: https://www.boost.org/doc/libs/1_60_0/libs/range/doc/html/range/reference /utilities/iterator_range.html .

Les concepts de plage arriveront également en

Darune
la source
1
À quoi ça using value_type = std::remove_cv_t<T>;sert?
Jabberwocky
1
... et vous avez oublié le constructeur: span(T* first_, size_t length) : first(first), length(length) {};. J'ai modifié votre réponse.
Jabberwocky
@Jabberwocky Je viens d'utiliser l'initialisation agrégée. Mais le constructeur va bien.
darune
1
@eerorika je suppose que vous avez raison, j'ai supprimé les versions non const
darune
1
Il using value_type = std::remove_cv_t<T>;est principalement nécessaire s'il est utilisé avec la programmation de modèles (pour obtenir le type_valeur d'une «plage»). Si vous souhaitez simplement utiliser les itérateurs, vous pouvez ignorer / supprimer cela.
darune
6

En fait, vous pourriez presque l'utiliser std::vectorpour cela, en abusant de la fonctionnalité d'allocateur personnalisé pour renvoyer un pointeur vers la mémoire que vous souhaitez afficher. Cela ne serait pas garanti par la norme de fonctionner (remplissage, alignement, initialisation des valeurs renvoyées; vous auriez à vous soucier de l'attribution de la taille initiale, et pour les non primitifs, vous auriez également besoin de pirater vos constructeurs ), mais en pratique, je m'attendrais à ce qu'il donne suffisamment de réglages.

Ne fais jamais ça. C'est moche, surprenant, hacky et inutile. Les algorithmes de la bibliothèque standard sont déjà conçus pour fonctionner aussi bien avec des tableaux bruts qu'avec des vecteurs. Voir les autres réponses pour plus de détails.

Sneftel
la source
1
Hmm, oui, cela pourrait fonctionner avec les vectorconstructeurs qui prennent une référence d'allocateur personnalisée comme argument de constructeur (pas seulement un paramètre de modèle). Je suppose que vous auriez besoin d'un objet allocateur contenant la valeur du pointeur d'exécution, pas en tant que paramètre de modèle, sinon il ne pourrait fonctionner que pour les adresses constexpr. Vous devez faire attention à ne pas laisser d' vectorobjets de construction par défaut sur .resize()et écraser les données existantes; l'inadéquation entre un conteneur propriétaire comme un vecteur par rapport à une plage non propriétaire est énorme si vous commencez à utiliser .push_back, etc.
Peter Cordes
1
@PeterCordes Je veux dire, n'enterrons pas la lede - il faudrait aussi être fou. À mon avis, la chose la plus étrange à propos de l'idée est que l'interface d'allocateur inclut la constructméthode qui serait requise ... Je ne peux pas penser quels cas d'utilisation non hacky exigeraient cela par rapport à placement-new.
Sneftel
1
Le cas d'utilisation évident est d'éviter de perdre du temps à construire des éléments que vous êtes sur le point d'écrire d'une autre manière, par exemple resize()avant de passer une référence à quelque chose qui veut l'utiliser comme une sortie pure (par exemple un appel système en lecture). Dans la pratique, les compilateurs n'optimisent souvent pas cet ensemble de mems ou autre. Ou si vous aviez un allocateur qui utilise calloc pour obtenir de la mémoire pré-mise à zéro, vous pourriez également éviter de le salir comme stupide le std::vector<int>fait par défaut lors de la construction d'objets par défaut qui ont un modèle de bits à zéro. Voir les notes dans en.cppreference.com/w/cpp/container/vector/vector
Peter Cordes
4

Comme d'autres l'ont souligné, std::vectordoit posséder la mémoire sous-jacente (à moins de jouer avec un allocateur personnalisé) donc ne peut pas être utilisé.

D'autres ont également recommandé l'étendue de c ++ 20, mais cela nécessite évidemment c ++ 20.

Je recommanderais le span-lite span. Pour citer son sous-titre:

span lite - Un span de type C ++ 20 pour C ++ 98, C ++ 11 et versions ultérieures dans une bibliothèque d'en-tête unique à fichier unique

Il fournit une vue non propriétaire et modifiable (comme dans vous pouvez muter les éléments et leur ordre mais pas les insérer) et comme le dit la citation n'a pas de dépendances et fonctionne sur la plupart des compilateurs.

Votre exemple:

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

Impressions

1
2
3
4
5

Cela a également l'avantage supplémentaire si un jour vous passez au c ++ 20, vous devriez simplement être en mesure de le remplacer nonstd::spanpar std::span.

Arghnews
la source
3

Vous pouvez utiliser un std::reference_wrapperdisponible depuis 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
la source
2
Cela effectue une copie des données, et c'est précisément ce que je veux éviter.
Jabberwocky
1
@Jabberwocky Cela ne copie pas les données. Mais ce n'est pas non plus ce que vous avez demandé dans la question.
eerorika
@eerorika std::copy(std::begin(src_table), std::end(src_table), std::back_inserter(dest_vector));remplit définitivement le dest_vectoravec les valeurs tirées de src_table(IOW les données sont copiées dest_vector), donc je n'ai pas reçu votre commentaire. Pourriez-vous expliquer?
Jabberwocky
@Jabberwocky, il ne copie pas les valeurs. Il remplit le vecteur avec des emballages de référence.
eerorika
3
@Jabberwocky c'est plus inefficace en cas de valeurs entières.
eerorika