Usando std :: vector como visualização na memória não processada

71

Eu estou usando uma biblioteca externa que em algum momento me dá um ponteiro bruto para uma matriz de números inteiros e um tamanho.

Agora eu gostaria de usar std::vectorpara acessar e modificar esses valores no lugar, em vez de acessá-los com ponteiros brutos.

Aqui está um exemplo articifial que explica o ponto:

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 
}

Saída esperada:

1
2
3
4
5

O motivo é que preciso aplicar algoritmos <algorithm>(classificação, troca de elementos etc.) nesses dados.

Por outro lado alterando o tamanho desse vector nunca iria ser mudado, assim push_back, erase, insertnão são obrigados a trabalhar nisso vetor.

Eu poderia construir um vetor com base nos dados da biblioteca, usar modificar esse vetor e copiar os dados de volta para a biblioteca, mas seriam duas cópias completas que eu gostaria de evitar, pois o conjunto de dados pode ser muito grande.

Jabberwocky
fonte
16
O que você procura é hipotético std::vector_view, não é?
眠 り ネ ロ ク
3
@ 眠 り ネ ロ ク sim, provavelmente
Jabberwocky
5
Não é assim que std::vectorfunciona.
Jesper Juhl
34
Os algoritmos padrão funcionam em iteradores e os ponteiros são iteradores. Não há nada que o impeça de fazer sort(arrayPointer, arrayPointer + elementCount);.
cmaster - reinstate monica

Respostas:

60

O problema é que std::vectoré necessário fazer uma cópia dos elementos da matriz com a qual você a inicializa, pois possui a propriedade dos objetos que ela contém.

Para evitar isso, você pode usar um objeto de fatia para uma matriz (ou seja, semelhante ao que std::string_viewé std::string). Você pode escrever sua própria array_viewimplementação de modelo de classe cujas instâncias são construídas levando um ponteiro bruto para o primeiro elemento de uma matriz e o comprimento da matriz:

#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_viewnão armazena uma matriz; apenas mantém um ponteiro para o início da matriz e o comprimento dessa matriz. Portanto, os array_viewobjetos são baratos para construir e copiar.

Desde array_viewfornece os begin()e end()membro funções, você pode usar os algoritmos da biblioteca padrão (por exemplo, std::sort, std::find, std::lower_bound, etc.) sobre ele:

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

Resultado:

1 2 3 4 5

Use std::span(ou gsl::span)

A implementação acima expõe o conceito por trás dos objetos de fatia . No entanto, desde C ++ 20, você pode usar diretamente std::span. Em qualquer caso, você pode usar gsl::spandesde o C ++ 14.

眠 り ネ ロ
fonte
Por que você marcou os métodos como exceto? Você não pode garantir que nenhuma exceção esteja sendo lançada, pode?
SonneXo
@moooeeeep É melhor deixar alguma explicação do que apenas um link. O link pode expirar no futuro enquanto eu vi isso acontecer muito.
Jason Liu
63

C ++ 20's std::span

Se você puder usar o C ++ 20, poderá usar std::spanum par de comprimento de ponteiro que permita ao usuário visualizar uma sequência contígua de elementos. É uma espécie de a std::string_view, e embora ambas as visualizações sejam std::spane std::string_viewnão proprietárias, std::string_viewé uma visualização somente leitura.

Dos documentos:

A extensão do modelo de classe descreve um objeto que pode se referir a uma sequência contígua de objetos com o primeiro elemento da sequência na posição zero. Uma extensão pode ter uma extensão estática; nesse caso, o número de elementos na sequência é conhecido e codificado no tipo ou uma extensão dinâmica.

Portanto, o seguinte funcionaria:

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

Confira ao vivo

Como std::spané basicamente um par de comprimento de ponteiro, você também pode usar da seguinte maneira:

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

Nota: Nem todos os compiladores suportam std::span. Verifique o suporte do compilador aqui .

ATUALIZAR

Se você não conseguir usar o C ++ 20, poderá usar gsl::spana versão básica dos padrões do C ++ std::span.

Solução C ++ 11

Se você está limitado ao padrão C ++ 11, pode tentar implementar sua própria spanclasse simples :

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

Confira a versão C ++ 11 ao vivo

NutCracker
fonte
4
Você poderia usar o gsl::spanC ++ 14 e superior se o seu compilador não implementarstd::span
Artyer em 10/02
2
@Artyer Vou atualizar minha resposta com isso. Obrigado
NutCracker
29

Como a biblioteca de algoritmos trabalha com iteradores, você pode manter a matriz.

Para ponteiros e comprimento conhecido da matriz

Aqui você pode usar ponteiros brutos como iteradores. Eles suportam todas as operações que um iterador suporta (incremento, comparação para igualdade, valor 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";
    }
}

dataaponta para o membro da matriz dirst como um iterador retornado por begin()e data + sizeaponta para o elemento após o último elemento da matriz como um iterador retornado por end().

Para matrizes

Aqui você pode usar std::begin()estd::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 
    }
}

Mas lembre-se de que isso só funciona, se datanão se deteriorar para um ponteiro, porque as informações de comprimento desaparecem.

churill
fonte
7
Esta é a resposta certa. Os algoritmos se aplicam aos intervalos . Os contêineres (por exemplo, std :: vector) são uma maneira de gerenciar intervalos, mas não são a única.
Pete Becker
13

Você pode obter iteradores em matrizes brutas e usá-los em algoritmos:

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

Se você estiver trabalhando com ponteiros não processados ​​(ptr + tamanho), poderá usar a seguinte técnica:

    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: No entanto, o exemplo acima é de design incorreto. A biblioteca nos retorna um ponteiro bruto e não sabemos onde o buffer subjacente está alocado e quem deve liberá-lo.

Normalmente, o chamador fornece um buffer para a função preencher os dados. Nesse caso, podemos pré-alocar o vetor e usar seu buffer subjacente:

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

Ao usar o C ++ 11 ou superior, podemos fazer com que get_data_from_library () retorne um vetor. Graças às operações de movimentação, não haverá cópia de memória.

PooSH
fonte
2
Em seguida, você pode usar ponteiros regulares como iteradores:auto begin = data; auto end = data + size;
PooSH
No entanto, a questão é onde os dados retornados por get_data_from_library()são alocados? Talvez não devamos mudar isso. Se precisarmos passar um buffer para a biblioteca, podemos alocar vetor e passarv.data()
PooSH
11
@PooSH, os dados pertencem à biblioteca, mas podem ser alterados sem restrições (esse é realmente o objetivo de toda a questão). Somente o tamanho dos dados não pode ser alterado.
Jabberwocky
11
@Jabberwocky adicionou um exemplo melhor de como usar o buffer subjacente do vetor para preencher os dados.
PooSH
9

Você não pode fazer isso com um std::vectorsem fazer uma cópia. std::vectorpossui o ponteiro que possui sob o capô e aloca espaço através do alocador que é fornecido.

Se você tiver acesso a um compilador que suporte C ++ 20, poderá usar std :: span, que foi criado exatamente para esse fim. Ele agrupa um ponteiro e tamanho em um "contêiner" que possui a interface do contêiner C ++.

Caso contrário, você pode usar o gsl :: span, do qual a versão padrão foi baseada.

Se você não quiser importar outra biblioteca, poderá implementá-la trivialmente, dependendo de todas as funcionalidades que desejar.

NathanOliver
fonte
9

Agora eu gostaria de usar std :: vector para acessar e modificar esses valores no local

Você não pode. Não std::vectoré para isso que serve. std::vectorgerencia seu próprio buffer, que é sempre adquirido de um alocador. Ele nunca se apropria de outro buffer (exceto de outro vetor do mesmo tipo).

Por outro lado, você também não precisa, porque ...

O motivo é que preciso aplicar algoritmos (classificação, troca de elementos etc.) nesses dados.

Esses algoritmos funcionam em iteradores. Um ponteiro é um iterador para uma matriz. Você não precisa de um vetor:

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

Diferentemente dos modelos de função <algorithm>, algumas ferramentas, como intervalos para std::begin/ , std::ende C ++ 20, não funcionam apenas com um par de iteradores, enquanto trabalham com contêineres, como vetores. É possível criar uma classe de wrapper para o tamanho do iterador + que se comporta como um intervalo e funciona com essas ferramentas. C ++ 20 irá introduzir tais invólucro para a biblioteca padrão: std::span.

eerorika
fonte
7

Além da outra boa sugestão sobre a std::spanentrada em e gsl:span, incluindo sua própria spanclasse (leve) até então, já é fácil o suficiente (sinta-se à vontade para copiar):

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

De nota especial também é a biblioteca de faixa de se você estiver interessado no conceito de faixa mais genérico: https://www.boost.org/doc/libs/1_60_0/libs/range/doc/html/range/reference /utilities/iterator_range.html .

Os conceitos de intervalo também chegarão em

darune
fonte
11
Para que serve using value_type = std::remove_cv_t<T>;?
Jabberwocky
11
... e você esqueceu o construtor: span(T* first_, size_t length) : first(first), length(length) {};. Eu editei sua resposta.
Jabberwocky
@Jabberwocky Acabei de usar a inicialização agregada. Mas o construtor está bem.
darune
11
@eerorika eu acho que você está certo, eu removi as versões não-const
darune 11/02
11
Isso using value_type = std::remove_cv_t<T>;é necessário principalmente se usado com a programação de modelos (para obter o tipo de valor de um 'intervalo'). Se você quiser apenas usar os iteradores, pode pular / remover isso.
darune
6

Na verdade, você quase poderia usar std::vectorisso abusando da funcionalidade do alocador personalizado para retornar um ponteiro para a memória que deseja exibir. Isso não seria garantido pelo padrão para funcionar (preenchimento, alinhamento, inicialização dos valores retornados; você teria que se esforçar ao atribuir o tamanho inicial, e para os não-primitivos, você também precisaria hackear seus construtores ), mas na prática eu esperaria que ele desse ajustes suficientes.

Nunca, jamais, faça isso. É feio, surpreendente, hacky e desnecessário. Os algoritmos da biblioteca padrão já foram projetados para funcionar tanto com matrizes brutas quanto com vetores. Veja as outras respostas para detalhes disso.

Sneftel
fonte
11
Hmm, sim, isso poderia funcionar com os vectorconstrutores que usam uma referência personalizada do Alocador como um construtor arg (não apenas como um parâmetro de modelo). Eu acho que você precisaria de um objeto de alocador que tivesse o valor do ponteiro de tempo de execução, não como um parâmetro de modelo, caso contrário, ele só funcionaria para endereços constexpr. Você precisaria ter cuidado para não permitir que vectorobjetos de construção padrão .resize()substituíssem os dados existentes; a incompatibilidade entre um contêiner proprietário como vetor versus período não-proprietário é enorme se você começar a usar .push_back etc.
Peter Cordes
11
@ PeterCordes Quero dizer, não vamos enterrar o lede - você também teria que ser louco. Na minha opinião, o mais estranho da idéia é que a interface do alocador inclua o constructmétodo que seria necessário ... Não consigo pensar em quais casos de uso não hacky exigiriam isso sobre a colocação de novo.
Sneftel
11
O caso de uso óbvio é evitar perder tempo construindo elementos que você está prestes a escrever de outra maneira, por exemplo, resize()antes de passar uma referência a algo que deseja usá-lo como uma saída pura (por exemplo, uma chamada de sistema de leitura). Na prática, os compiladores geralmente não otimizam esse memset ou o que seja. Ou, se você tivesse um alocador que usa calloc para obter memória pré-zerada, também poderia evitar sujá-la da maneira estúpida std::vector<int>por padrão ao construir objetos padrão que possuem um padrão de bits zero. Veja as notas em en.cppreference.com/w/cpp/container/vector/vector
Peter Cordes
4

Como outros já apontaram, std::vectordeve possuir a memória subjacente (além de mexer com um alocador personalizado) para que não possa ser usado.

Outros também recomendaram a extensão do c ++ 20, no entanto, obviamente, isso requer c ++ 20.

Eu recomendaria o período span-lite . Para citar sua legenda:

span lite - um span do tipo C ++ 20 para C ++ 98, C ++ 11 e posterior em uma biblioteca somente de cabeçalho de arquivo único

Ele fornece uma visão não proprietária e mutável (como você pode alterar elementos e sua ordem, mas não inseri-los) e, como diz a citação, não possui dependências e funciona na maioria dos compiladores.

Seu exemplo:

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

Impressões

1
2
3
4
5

Isso também tem uma vantagem adicional: se um dia você mudar para c ++ 20, poderá substituir isso nonstd::spanpor std::span.

Arghnews
fonte
3

Você pode usar um std::reference_wrapperdisponível desde o 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
fonte
2
Isso executa uma cópia dos dados, e é exatamente isso que eu quero evitar.
Jabberwocky
11
@Jabberwocky Isso não copia os dados. Mas não é o que você pediu na pergunta também.
eerorika
A @eerorika std::copy(std::begin(src_table), std::end(src_table), std::back_inserter(dest_vector));definitivamente preenche os dest_vectorvalores obtidos src_table(IOW para os quais os dados são copiados dest_vector), então não recebi seu comentário. Você poderia explicar?
Jabberwocky
@Jabberwocky não copia valores. Ele preenche o vetor com invólucros de referência.
eerorika
3
@Jabberwocky é mais ineficiente no caso de valores inteiros.
eerorika