C ++: объединение массива - возможно ли с указателями БЕЗ копирования? - PullRequest
0 голосов
/ 01 августа 2011

как в заголовке можно ли объединить несколько массивов без копирования и только с помощью указателей? Я трачу значительное количество времени на вычисления, копируя меньшие массивы в большие. примечание: я не могу использовать векторы, поскольку umfpack (некоторая библиотека для решения матриц) не позволяет мне или я не знаю как.

Как пример:

int n = 5;

// dynamically allocate array with use of pointer

int *a = new int[n];


// define array pointed by *a as [1 2 3 4 5]

for(int i=0;i<n;i++) {
    a[i]=i+1;
}


// pointer to array of pointers ???  --> this does not work

int *large_a = new int[4];
for(int i=0;i<4;i++) {
    large_a[i] = a;
}

Примечание. Я уже знаю простое решение, которое заключается в том, чтобы просто итеративно копировать их в новый большой массив, но было бы полезно знать, если нет необходимости копировать повторяющиеся блоки, которые хранятся в течение всего периода программа. Я в кривой обучения атм.

спасибо, что читаете всех

Ответы [ 6 ]

6 голосов
/ 01 августа 2011

как в заголовке можно ли объединить несколько массивов без копирования и только с помощью указателей?

Короче говоря, нет.

Указательпросто адрес в памяти - как уличный адрес.Вы не можете переместить два дома рядом друг с другом, просто копируя их адреса.Вы также не можете переместить два дома вместе, изменив их адреса.Изменение адреса не перемещает дом, оно указывает на новый дом.

примечание: я не могу использовать векторы, так как umfpack (некоторая библиотека решения матриц) не позволяетменя или я не знаю как.

В большинстве случаев вы можете передать адрес первого элемента std::vector, когда ожидается массив.

std::vector a = {0, 1, 2}; // C++0x initialization
void c_fn_call(int*);
c_fn_call(&a[0]);

Это работает, потому что vector гарантирует, что хранилище для его содержимого всегда непрерывно.

Однако , когда вы insert или erase элементиз vector он делает недействительными указатели и итераторы, которые из него получены. Любые указатели, которые вы могли получить, взяв адрес элемента, больше не указывают на vector, если выделенное хранилище должноизменить размер.

3 голосов
/ 01 августа 2011

Нет. Память двух массивов не обязательно является смежной, поэтому невозможно объединить их без копирования. И элементы массива должны находиться в смежной памяти ... или доступ по указателю был бы невозможен.

0 голосов
/ 01 августа 2011

Вот как это сделать правильно:

template<class T, class K1, class K2>
class JoinArray {
    JoinArray(K1 &k1, K2 &k2) : k1(k1), k2(k2) { }
    T operator[](int i) const { int s = k1.size(); if (i < s) return k1.operator[](i); else return k2.operator[](i-s); }
    int size() const { return k1.size() + k2.size(); }
 private:
    K1 &k1;
    K2 &k2;
 };
 template<class T, class K1, class K2>
 JoinArray<T,K1,K2> join(K1 &k1, K2 &k2) { return JoinArray<T,K1,K2>(k1,k2); }

 template<class T>
 class NativeArray
 {
     NativeArray(T *ptr, int size) : ptr(ptr), size(size) { }
     T operator[](int i) const { return ptr[i]; }
     int size() const { return size; }
  private:
     T *ptr;
     int size;
  };

 int main() {
    int array[2] = { 0,1 };
    int array2[2] = { 2,3 };
    NativeArray<int> na(array, 2);
    NativeArray<int> na2(array2, 2);
    auto joinarray = join(na,na2);
}
0 голосов
/ 01 августа 2011

Переменная, которая является указателем на указатель, должна быть объявлена ​​как таковая.Это делается путем размещения дополнительной звездочки перед ее именем.Следовательно, int **large_a = new int*[4]; Ваш large_a идет и находит указатель, в то время как вы определили его как указатель на int.Он должен быть определен (объявлен) как указатель на переменную-указатель.Так же, как int **large_a; может быть достаточно.

0 голосов
/ 01 августа 2011

Если вы хотите объединить массивы , не копируя элементы , и в то же время вы хотите получить доступ к элементам, используя оператор индекса, т.е. [], то это невозможно без написания класса, который инкапсулируетвсе такие функциональные возможности.

Я написал следующий класс с минимальным вниманием, но он демонстрирует основную идею, которую вы можете отредактировать, если хотите, чтобы у нее были функциональные возможности, которых в данный момент нет.Также должно быть несколько ошибок, которые я не написал, просто чтобы он выглядел короче, но я верю, что вы поймете код и соответственно обработаете ошибки.

template<typename T>
class joinable_array
{
     std::vector<T*>     m_data;
     std::vector<size_t> m_size;
     size_t              m_allsize;
   public: 
       joinable_array() : m_allsize() { }
       joinable_array(T *a, size_t len) : m_allsize() { join(a,len);}
       void join(T *a, size_t len)
       {
           m_data.push_back(a);
           m_size.push_back(len);
           m_allsize += len;
       }
       T & operator[](size_t i)  
       {
            index ix = get_index(i);
            return m_data[ix.v][ix.i];
       }
       const T & operator[](size_t i) const
       {
            index ix = get_index(i);
            return m_data[ix.v][ix.i];
       }
       size_t size() const { return m_allsize; }
  private:
       struct index
       {
           size_t v;
           size_t i;
       };
       index get_index(size_t i) const
       {
          index ix = { 0,  i};
          for(auto it = m_size.begin(); it != m_size.end(); it++)
          {
                if ( ix.i >= *it ) { ix.i -= *it; ix.v++; }
                else break;
          }
          return ix;
       }
};

И вот один тесткод:

#define alen(a) sizeof(a)/sizeof(*a)

int main() {

        int a[] = {1,2,3,4,5,6};
        int b[] = {11,12,13,14,15,16,17,18};

        joinable_array<int> arr(a,alen(a));
        arr.join(b, alen(b));
        arr.join(a, alen(a)); //join it again!

        for(size_t i = 0 ; i < arr.size() ; i++ )
            std::cout << arr[i] << " ";
}

Выход:

1 2 3 4 5 6 11 12 13 14 15 16 17 18 1 2 3 4 5 6 

Демонстрационная версия онлайн: http://ideone.com/VRSJI

0 голосов
/ 01 августа 2011

Я бы, вероятно, использовал memcpy / memmove, которая все еще будет копировать память, но, по крайней мере, она была оптимизирована и протестирована вашим поставщиком компиляторов.

Конечно, "настоящий" C ++способ сделать это будет использовать стандартные контейнеры и итераторы.Если ваша память разбросана повсюду, как это, для меня будет лучше использовать связанный список, если вы не собираетесь выполнять много операций произвольного доступа.

Кроме того, продолжайтеИмейте в виду, что если вы используете указатели и динамически размещаемые массивы вместо стандартных контейнеров, гораздо проще вызвать утечки памяти и другие проблемы.Я знаю, что иногда у тебя нет выбора, а просто сказать.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...