В новый динамический массив выписать все элементы массива, которые делятся на заданное число

@Ravik · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

Помоготи с простенькой задачей:

Дан массив произвольных чисел
необходимо в новый динамический массив выписать все элементы, которые делятся на число "k"
А именно перебрать все элементы массива и, если число делится на k, то расширить динамический массив на один элемент и сохранить значение.

Заранее спасибо)
Очень выручите))

@asics · 12.08.2011, 19:35

Сыроежка, Что значит "возможно" ? Он или есть или его нет, если первое - пруф линк в студию.

@Сыроежка · 12.08.2011, 19:41

Сообщение от asics

Сыроежка, Что значит "возможно" ? Он или есть или его нет, если первое - пруф линк в студию.

Это значит, что я не знаю. Но очевидно имеется противоречивая информация. Странно, если Страуструп ошибся.

@asics · 12.08.2011, 19:46

Мне кажется, что под этим

Сообщение от Сыроежка

В настоящее время эта ошибка исправлена

Страуструп как раз и подразумевает грядущий стандарт, так как финальный драфт уже принят.

@Ravik · 13.08.2011, 23:11 **[ТС]**

спасибо всем за комментарии)

Решил сильно не заморачиваться (ведь все равно пишу для себя):
просто когда появляется новый элемент, создаю массив дубикат, копирую в него, удаляю свой создаю снова его с кол-вом элементов +1 копирую все обратно и в конце добавляю последнее значение.

З.Ы. просьба не писать сообщения об неэффективности данного метода, спс сам знаю)

@ValeryLaptev · 13.08.2011, 23:27

Вот почитай про динамические растущие массивы.

Чтобы разобраться в этом вопросе, давайте снова реализуем динамический массив, но с переменным количеством элементов. Нумерация элементов, как обычно, должна начинаться с 0, а добавление элементов осуществляется только в конец массива. Нам нужно рассмотреть несколько вопросов:
1. Какой объем памяти выделять первоначально, если размер контейнера не указан.
2. Если при добавлении элемента выясняется, что места в контейнере нет, то какой объем выделять дополнительно.

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

Ответ на первый вопрос достаточно прост: сколько хотите, столько и выделяйте — никакого «специального» количества не существует. Можно выделить даже 0 элементов, так как это разрешено стандартом. Но обычно выделяют некоторое минимальное количество памяти, например, для 10 или 100 элементов.

Ответа на второй вопрос только три:
 выделять столько памяти, чтобы размер динамического массива всегда точно соответствовал количеству элементов в нем. При таком подходе память расходуется очень эффективно — никакого лишнего расхода. Однако это означает, что при каждом добавлении элемента требуется перезапись n элементов массива.
 увеличивать размер динамического массива с некоторым фиксированным шагом (количеством элементов) m, например 10 или 32. Очевидно, память расходуется достаточно эффективно — пустым остается небольшой объем. И перезаписи требуются реже — один раз на каждые m добавлений элементов.
 увеличивать размер динамического массива экспоненциально, выделяя каждый раз не меньше памяти, чем текущий размер массива. Например, в массиве 100 элементов, тогда новый динамический массив должен вмещать не менее 200 элементов. При следующем увеличении выделяется новая память для 400 элементов. Если принять текущий размер за 1, то коэффициент увеличения тоже равен 1, а размер нового массива равен sizeof(старый массив)*(1+1). При таком подходе память в значительной мере пустует. Однако, как пишет Герб Саттер [21, задача 7.2], такая стратегия существенно снижает необходимость перезаписи элементов — настолько существенно, что он рекомендует пренебречь дополнительным расходом памяти. Со ссылкой на Эндрю Кенига Саттер сообщает, что наилучший коэффициент увеличения массива должен быть близок к 1.5. Таким образом,

C++
1
размер нового массива = sizeof(старый массив)*(1+1.5)

Поверим Гербу Саттеру и перепишем класс SimpleArray (см. листинг 7.4) как шаблон TArray, реализовав последнюю стратегию выделения памяти. Добавим также последовательный доступ с помощью итераторов. Таким образом, класс-шаблон нашего массива может выглядеть так (листинг 9.1).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
Листинг 9.1. Интерфейс динамического массива с изменяемым размером
template<typename T> 
class TArray {
public:
  // типы
  typedef T                                     value_type;            
  typedef T*                                    iterator;              
  typedef const T*                              const_iterator;        
  typedef T&                                    reference;             
  typedef const T&                              const_reference;       
  typedef std::size_t                           size_type;             
  // конструкторы/копирование/деструктор
  TArray(const size_type& n = minsize);
  TArray(const TArray<T>& array);
  template <class Iterator> TArray(Iterator first, Iterator last);
  ~TArray() { delete [] elems; elems = 0; }
  Tarray<T>& operator=(const TArray<T>&);
  template<typename U> TArray& operator=(const TArray<U>&);
// итераторы
  iterator begin() { return elems; }
  const_iterator begin() const { return elems; }
  iterator end() { return elems+Count; }
  const_iterator end() const { return elems+Count; }
// размеры
  size_type size() const                // длина массива
  { return Count; }
  bool empty() const                    // есть ли элементы
  { return (Count == 0); }
  size_type capacity() const            // потенциальный размер
  { return Size; }
  void resize(size_type newsize);       // изменить размер
// доступ к элементам
  reference operator[](size_type)
  { rangecheck(i);                      // проверка индекса
    return elems[i]; 
  }
  const_reference operator[](size_type) const 
  { rangecheck(i);                      // проверка индекса
    return elems[i]; 
  }
  reference front() { return elems[0]; }
  const_reference front() const { return elems[0]; }
  reference back() { return elems[size()-1]; }
  const_reference back() const { return elems[size()-1]; }  
// методы-модификаторы
  void push_back(const T& v);
  void pop_back()                        // удалить последний элемент
  { if (!empty()) --Count; 
    else throw std::domain_error("array<>: empty array!");
  }
  void clear() { Count = 0; }           // очистить массив
  void swap(TArray<T>& other)           // обменять с другим массивом
  {  std::swap(elems, v.elems);         // стандартная функция обмена
     std::swap(Size, v.Size);
     std::swap(Count, v.Count);
  }
  void assign(const T& v)               // заполнить массив
  { if (!empty()) 
      for(size_type i = 0; i < Count; ++i) 
          elems[i] = v;
  } 
private:
  static const size_type minsize = 10;  // минимальный размер массива
  size_type Size;                       // выделено элементов в памяти
  size_type Count;                      // количество элементов
  value_type * elems;                   // указатель на данные
// проверка индекса
    void rangecheck (size_type i) 
    { if (i >= size()) 
        throw std::range_error("array<>: index out of range");
    }
};
// обмен – внешняя функция
template<typename T> void swap(TArray<T>&, TArray<T>&)
inline void swap(TArray<T>& x, TArray<T>& y)
{ x.swap(y); }
// сравнения
template<typename T> 
bool operator==(const TArray<T>& x, const TArray<T>& y)
{ if (x.size() == y.size())
  { for(size_type i = 0; i < x.size(); ++i) 
        if (x[i]!=y[i]) return false;
    return true;
  }
  else return false;
}
template<typename T> 
bool operator!=(const TArray<T>& x, const TArray<T>& y)
{ return !(x==y); }

Такой массив называется растущим, так как элементы добавляются только к его концу: массив «растет». В начале класса-шаблона, как обычно, заданы определения типов. Заменив double на любой другой встроенный числовой тип, получим реализацию динамического массива для другого типа. Реализацию методов при этом переписывать не требуется, поскольку они реализованы в терминах объявленных типов.

В классе три поля: указатель на выделенную память elems, поле Size определяет количество зарезервированных элементов, а поле Count содержит количество присутствующих в массиве элементов. Очевидно, что поле Count увеличивается по мере добавления элементов в массив. Как только значение поля Count сравняется со значением поля Size, необходимо выделять новую память.

Последовательный доступ к элементам динамического массива осуществляется итератором, который просто является указателем соответствующего типа. Поэтому в шаблоне не определен класс для итератора (см. листинг 3.20), как мы делали это в классе TDeque. Методы, принимающие параметры-итераторы или выдающие итератор-результат фактически работают с указателями на элементы массива — их реализация очень проста. Конечно, это снижает безопасность нашего кода, но в данном случае нам важнее разобраться с управлением памятью.

Класс массива обеспечивает получение начального (методы begin()) и конечного (методы end()) значения итератора, получение значения первого (методы front()) и последнего (методы back()) элемента. Конечное значение итератора, как обычно, — за последним элементом массива. Перемещение по элементам и получение значения элемента выполняется операциями с указателями (операции инкремента, декремента и разыменования).
Реализация остальных методов представлена в листинге 9.2.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Листинг 9.2. Реализация методов шаблона TArray
// конструкторы
template <class T>
TArray<T>::TArray(const TArray<T> &t)
:Size(t.Size), 
 Count(t.Count),
 elems(new T[Size])                         // новый массив
{   for(size_type i = 0; i<Count; ++i)      // копируем
       elems[i] = t.elems[i];
}
template <class T>
TArray<T>::TArray(const size_type& n)
:Size((n > minsize)?n:minsize), 
 Count(n),                                  // массив пустой
 elems(new T[Size])                         // новый массив
{ for(size_type i = 0; i<Size; ++i)         // обнуляем
     elems[i] = T();
}
template <class T>
template <class Iterator>
TArray<T>::TArray(Iterator begin, Iterator end)
{ if (!(begin > end))
  { Size  = (end - begin);                  // количество элементов
    Count = Size;                           // текущий размер
    elems = new T[Size];                    // создаем массив
    for(size_type i = 0; i<Count; ++i)      // заполняем массив
       elems[i] = *(begin+i);               // копируем из массива
  }
  else                                      // неправильные параметры
  throw std::invalid_argument("array<>: invalid_argument (begin > end)!");
}
// добавление элементов
template <class T>
void TArray<T>::push_back(const value_type& v)
{ if (Count == Size)                        // места нет
    resize(Size * 2);                       // увеличили «мощность»
  elems[Count++] = v;                       // присвоили
}
template <class T>
void TArray<T>::resize(size_type newsize)
{ if (newsize > capacity())
  { T *data = new T[newsize];               // новый массив
    for(size_type i = 0; i<Count; ++i)      // копируем
       data[i] = elems[i];
    delete[] elems;                         // возвращаем память
    elems = data;                           // вступили во владение
    Size = newsize;                         // «увеличили «мощность»
  }
}
template <class T>
template <class U>
TArray<T>& TArray<T>::operator=(const TArray<U>& other)
{ TArray<T>tmp(other.begin(), other.end());
  tmp.resize(other.capacity());
  swap(tmp);
  return *this;
}
template <class T>
TArray<T>& TArray<T>::operator=(const TArray<T>& other)
{ TArray<T>tmp(other.begin(), other.end());
  tmp.resize(other.capacity());  
  swap(tmp);
  return *this;
}

Набор конструкторов небольшой — всего три. Первый конструктор с параметром по умолчанию резервирует память. Количество резервируемой памяти по умолчанию определяется приватной статической константой minsize, поэтому больше выделить памяти можно, а меньше — нельзя. Если параметр не равен нулю, то создается массив из указанного количества индексируемых элементов, проинициализированных по умолчанию. В этом случае присвоить значение любому элементу можно обычным для массива способом, например

C++
1
2
TArray<int> m(5); 
m[0] = 12; m[3] = 2;

Этот конструктор позволяет создавать массивы, размеры которых зависят от значений переменных, например

C++
1
2
3
int k;
cin >> k;
TArray<int> w(k);

Если аргумент не задан, то по умолчанию массив — пустой, то есть количество присутствующих (индексируемых) элементов в массиве равно нулю. В этом случае в массив можно только добавлять элементы — методом push_back(), например

C++
1
2
3
4
5
6
7
8
9
10
TArray<int> m; 
cout << m.size() << ' ' << m.capacity() << endl;
m.push_back(1); 
m.push_back(1); 
m.push_back(2); 
m.push_back(2); 
m.push_back(3); 
cout << m.size() << ' ' << m.capacity() << endl;
for (int i = 0; i < m.size(); ++i) cout << m[i] << ' ';
cout << endl;

Этот фрагмент выведет на экран
0 10
5 10
1 1 2 2 3
Первая строка показывает, что первоначально массив пуст, хотя место зарезервировано для 10 элементов. Количество элементов, занесенных в массив, выдает метод size(), а количество зарезервированной памяти для элементов — метод capacity(). Во второй строке мы видим, что в массиве появилось 5 элементов. Цикл демонстрирует нам, что элементы, добавленные в массив, доступны по индексу.

После того, как элементы в массив добавлены, можно присвоить всем элементам одно и то же значение методом assign(), например

C++
1
m.assign(17);

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

C++
1
2
3
4
TArray<double> mm(m.begin(), m.end());
TArray<int>::const_iterator begin = m.begin();
TArray<int>::const_iterator end   = m.end();
TArray<long> tt(begin, end);.

В первой строке для создания массива mm типа TArray<double> используются итераторы массива m, который имеет тип TArray<int>. Далее объявляются и инициализируются константные итераторы типа TArray<int>, а используются они при создании массива TArray<long>. Если бы конструктор не был шаблонным методом, нельзя было бы использовать итераторы другого типа.

Операций присваивания — две. Одна – обычная, реализует присваивание массивов одинакового типа, при этом принимающий массив становится копией присваиваемого. Вторая операция присваивания сделана шаблонной по той же причине: чтобы можно было присваивать массив менее «мощного» типа массиву более «мощного» типа (как в шаблоне SimpleArray — листинг 7.24). Вообще-то говоря, необходимо проверять совместимость типов по присваиванию, но мы пока отложим эту проблему.

Реализация обеих операций совершенно одинакова. Обратите внимание, что используется все тот же прием с обменом текущего и временного массива, описанный Гербом Саттером в [21]. Для этого и реализован метод swap(), обменивающий поля текущего массива с полями массива-аргумента. И опять мы использовали стандартную функцию swap(), реализованную в библиотеке STL.

Почему реализовано две операции — нельзя ли обойтись одной? Нельзя. Вспомним, что шаблонный конструктор копирования и шаблонная операция присваивания (см. гл. 7) не замещают создаваемые по умолчанию. Таким образом, если мы не определим обычную операцию присваивания, то она будут создана по умолчанию. А как мы уже выяснили ранее (см. гл. 3), стандартная операция присваивания для динамических массивов работает неправильно — создает потерянные ссылки.

Метод resize() предназначен для увеличения размера зарезервированной памяти. Уменьшить размер выделенной памяти нельзя. Работает он просто: резервируется память для нового массива большего размера, туда копируются элементы текущего массива, после чего «старая» память возвращается.

Метод push_back(), который добавляет элемент в конец массива, совсем простой. Пока количество элементов (поле Count) меньше зарезервированного количества (поле Size), значение просто заносится в очередной зарезервированный элемент, увеличивая количество элементов массива на 1. Если при очередном добавлении окажется, что Count == Size, то вызывается метод resize() для удвоения выделенной памяти. После этого аргумент заносится в следующий элемент массива.

Метод pop_back() удаляет последний элемент массива, а метод clear() очищает весь массив. Методы работают очень быстро, так как реально никакого удаления не происходит, просто корректируется значение поля Count. Удаление, естественно, может быть выполнено только в том случае, если в массиве есть хоть один элемент, иначе генерируется исключение. Так как массив может быть пустой, для проверки этого факта реализован метод empty().

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

C++
1
m+=1; m+=1; m+=2; m+=2;m+=3;

Соответственно, для удаления элемента вполне подходит операция -=. Однако имена методов push_back() и pop_back() выбраны сознательно. Как мы увидим далее, реализованный нами шаблон растущего динамического массива очень похож на последовательный контейнер vector из стандартной библиотеки STL.

Можно дополнить на класс-шаблон методами вставки в произвольное место массива и удаления любого элемента. Массив с произвольными вставками и удалениями элементов называется «гибким» (flexible) массивом. Схема вставки в середину, например на место n, должна быть следующей:
1. Размер массива увеличивается на один элемент; если требуется, резервируется память под новый массив.
2. Элементы от n + 1 до count «сдвигаются» на один элемент «вправо».
3. На место n заносится вставляемый элемент.
При удалении выполняется «сдвиг» элементов от n + 1 до count «влево» на один элемент; память при этом не возвращается.

Вставку и удаление единственного элемента легко обобщить на группу элементов, задаваемую парой итераторов. Метод группового удаления, очевидно, выполняет в цикле одиночное удаление, перемещая итератор от элемента к элементу. Вставка группы элементов требует трех параметров: итератор, указывающий место вставки, и пара итераторов, указывающих вставляемые элементы из второго контейнера.
Для растущих и гибких массивов часто реализуется операция простого сцепления, например

C++
1
2
3
4
5
6
7
8
9
10
11
template <class T>
TArray<T>& TArray<T>::operator+=(const TArray<T>&r) throw(bad_alloc)
{ TArray<T> t(capacity()+r.capacity());   // новый большой массив
  for(int i = 0; i<size(); i++)       // переписываем текущий
      t.push_back(data[i]);
  for(int i = 0; i<r.size(); i++)     // переписываем новый
      t.push_back(data[i]);
  delete[] elems;                     // возвращаем память текущего
  *this = t;                          // заменяем текущий массив на новый
  return *this;
}

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

Новые блоги и статьи Все статьи Все блоги /
Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .	сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .	Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .

@Ravik 1 / 1 / 0 Регистрация: 24.06.2010 Сообщений: 55

	В новый динамический массив выписать все элементы массива, которые делятся на заданное число 12.08.2011, 17:38. Показов 7343. Ответов 24 Метки нет (Все метки) Помоготи с простенькой задачей: Дан массив произвольных чисел необходимо в новый динамический массив выписать все элементы, которые делятся на число "k" А именно перебрать все элементы массива и, если число делится на k, то расширить динамический массив на один элемент и сохранить значение. Заранее спасибо) Очень выручите)) 0

@asics Freelance 2891 / 1826 / 356 Регистрация: 09.09.2010 Сообщений: 3,841
	12.08.2011, 19:35
	Сыроежка, Что значит "возможно" ? Он или есть или его нет, если первое - пруф линк в студию. 0

@Ravik 1 / 1 / 0 Регистрация: 24.06.2010 Сообщений: 55
	13.08.2011, 23:11 [ТС]
	спасибо всем за комментарии) Решил сильно не заморачиваться (ведь все равно пишу для себя): просто когда появляется новый элемент, создаю массив дубикат, копирую в него, удаляю свой создаю снова его с кол-вом элементов +1 копирую все обратно и в конце добавляю последнее значение. З.Ы. просьба не писать сообщения об неэффективности данного метода, спс сам знаю) 0