Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > функции добавления/удаления эелементов из массива


Автор: massiv 27.9.2009, 15:31
Есть 2-е функции для работы с динамическими массивами (_push и _pop). Одна добавляет элемент в массив, другая удаляет элемент из массива. Вроде бы функции написаны правильно, и жаде делают то что нужно  smile  но, при использовании в многопоточной программе почему то дают сбой: функция добавления элемента Б во вторую ячейку почему то ИНОГДА (при определённых условиях, но не всегда) затирает первый элемент А массива, находящийся в первой ячейке, таким образом получается следующее:

1) есть массив с одним элементом : m = {A} (массив естественно динамический, это я для примера в фигурных пишу)
2) применяем функцию добавление элемента B в массив:  _push(m, massiv_size, B),
3) получаем массив m= {B,B}, а должен быть равен {A,B}

Собственно вопрос: почему так происходит? замечу что происходит так не всегда. Коды функций ниже:

_pop: 
Код

int _pop (int *mas, int msize, int pop_value) {     // на входе: ссылка на массив, его текущая размерность (число элементов), элемент который хотим вынуть из массива
  int i, j;
 
  for (i = 0, j = 0; i < msize; i++) { 
    if (mas[i] != pop_value) {
      mas[j] = mas[i];               //  перезаписываем все елементы кроме того который хотим убрать
      j++;
    }
  }

  if (!(mas = (int *) realloc(mas, (msize - 1) * sizeof(int)))) {            // и уменьшаем размерность массива на единицу
      perror("realloc");
      return -1;
    }

  return msize-1;           // на выходе новая размерность массива
}
 


_push
Код

int _push (int *mas, int msize, int push_value) {   // на входе: ссылка на массив, текущая размерность (число элементов), элемент который хотим добавить в массив
  if (!(mas = (int *) realloc(mas, (msize + 1) * sizeof(int)))) {   // увеличиваем массив на один элемент
    perror("perror");
    return -1;
  }

  mas[msize] = push_value;   // добавляем элемент

  return msize + 1;   // возвращаем новую размерность
}



Если что то не понятно объяснил, спрашивайте. В конце концов могу полный код привести если понадобится

Автор: Graf_h 27.9.2009, 16:50
massiv,  во первых, ставте критические секции на добавление и удаление, во вторых, не думаю что пробегатся фором  по всему масиву при перезаписи - это правильный выбор. 

Автор: massiv 27.9.2009, 17:26
Цитата

во первых, ставте критические секции на добавление и удаление


 не понимаю, поясните пож-ста

Цитата

во вторых, не думаю что пробегатся фором  по всему масиву при перезаписи - это правильный выбор. 



вы об этом участке в функции _push ?

  for (i = 0, j = 0; i < msize; i++) { 
    if (mas[i] != pop_value) {
      mas[j] = mas[i];              
      j++;
    }
  }

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


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

(A,B,C,D) -> (A, NULL, C, D) -> (A, C, D) 

но как это можно осуществить relloc-ом - непонятно....

Автор: Graf_h 27.9.2009, 19:32
massiv,  функция memcpy или memmove 
http://c2p.ru/c/func/strokovye-i-simvolnye
Можна заюзать СТЛ контейнеры

Цитата(massiv @  27.9.2009,  15:31 Найти цитируемый пост)
при использовании в многопоточной программе

А чему вы удивляетесь? Представте себе ситуация когда два потока одновременно обращаются к вашим функциям...))

Цитата(massiv @  27.9.2009,  17:26 Найти цитируемый пост)
не понимаю, поясните пож-ста


http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%B5%D0%BA%D1%86%D0%B8%D1%8F

http://www.cyberguru.ru/programming/cpp/multithreading-intro-page2.html


Автор: massiv 27.9.2009, 22:49
Цитата

А чему вы удивляетесь? Представте себе ситуация когда два потока одновременно обращаются к вашим функциям...))


Нет, в том то и суть,  я защищаю участки использования этих функций мьютексами, так что в этом плане всё в порядке, я уверен.

Остальное сейчас почитаю.



Ага!на счёт критических секций, я уже ответил - использую мьютексы, STL контейнеры тоже отпадают, код написан на С и компиляется это всё под линуксом (забыл упомянуть)  smile 

Автор: massiv 28.9.2009, 08:06
Пытаюсь сделать с помощью memmove, но сталкиваюсь с проблемой :

Код

int _pop (int *mas, int msize, int pop_value) {  
  int i, j, *p;
  j = 0;

  p = (int *) malloc((msize - 1) * sizeof(int));

  for (i = 0; i < msize; i++) {

       if (mas[i] == pop_value) { 
     j = i;                          // находим индекс исключаемого элемента
         break;
       }
  }

  printf("->> index = %d\n\n", j);

  memmove(p, mas, sizeof(int) * j);        // копируем все элементы стоящие до исключаемого элемента

  for (i = 0; i < msize -1; i++) printf("%d ", p[i]);

  // mas = (int *) realloc(mas, (msize - 1) * sizeof(int));

  return msize -1;
}



Вопрос: как же скопировать остальные элементы, стоящие после исключаемого с помощью memmove?

Автор: MAKCim 28.9.2009, 09:02
Цитата(Graf_h @  27.9.2009,  16:50 Найти цитируемый пост)
то пробегатся фором  по всему масиву при перезаписи - это правильный выбор.  

для этого есть RCU
главное обеспечить барьеры перед изменением поинтера
хотя для массивов int и этого не надо

Автор: Graf_h 28.9.2009, 09:29
massiv, 
Цитата(massiv @  28.9.2009,  08:06 Найти цитируемый пост)
Вопрос: как же скопировать остальные элементы, стоящие после исключаемого с помощью memmove? 

Елементы, которы стоят до исключаемого или добавляемого елемента трогать вообще не нужно. Нужно только сдвигать те, которые после.
realloc вам вообще не нужен. Сделайте как в СТЛ  векторе зарезервируйте количество памяти, и если елементов станет больше, выделите в 2 раз больше памяти (так называемое перераспредиление). На  мой взгляд - это логичней всего.
Код


memmove(p+index, mas, sizeof(int) * count); - примерно так

Автор: Andrey44 28.9.2009, 12:49
Цитата(massiv @  28.9.2009,  08:06 Найти цитируемый пост)
memmove(p, mas, sizeof(int) * j);        // копируем все элементы стоящие до исключаемого элемента

Цитата(Graf_h @  28.9.2009,  09:29 Найти цитируемый пост)
memmove(p+index, mas, sizeof(int) * count); - примерно так

Чем отличаются эти две строки?
Надо &mas[index] и sizeof(int) умножать на количество оставшихся элементов.
Как-то так

Автор: Graf_h 28.9.2009, 13:33
Andrey44, там вообще не нужно променжуточного масива. 
Код

memmove(mas+index, mas+index+1, sizeof(int) * count); 

Автор: Andrey44 28.9.2009, 14:09
Цитата(Andrey44 @  28.9.2009,  12:49 Найти цитируемый пост)
memmove(p+index, mas, sizeof(int) * count); - примерно так

Но это-же ты писал?

Автор: Graf_h 28.9.2009, 14:24
Andrey44, да)). поспешил. извиняюсь.

Автор: massiv 28.9.2009, 17:06
немного не так, вот как :

 memmove(mas+j, mas+j+1, (msize-j) *sizeof(int)); 

всем спасибо smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)