Форум программистов, компьютерный форум CyberForum.ru

Стек! - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Написать программу, которая считывает английский текст из файла и выводит на экран слова текста, начинающиеся и оканчивающиеся на гласные буквы. http://www.cyberforum.ru/cpp-beginners/thread338295.html
напишите пожалуйста в С++
C++ putty преведы! аналогичная тема уже есть, но тем не менее :) где можно почитать маны//исходники проектов использующих ssh. исходники putty нагоняют тихий ужас и вызывают обмороки. даже не знаю как спросить еще. обмороки еще дают о себе знать. вОпщем, каким чудотворным образом написать прогу, которая будет конектится под виндой к SSH серверу. http://www.cyberforum.ru/cpp-beginners/thread338291.html
Проблемы с выводом C++
Подскжите пожалуйста почему не работает эта программа ? Почему точнее не работает вывод ? #include<iostream> #include<string> #include<fstream> //для ofstream #include<windows.h> using namespace std; int main () {setlocale(LC_ALL,"Rus"); cout<<"Введите строку для ввода --> "; string str;
C++ Доступ к переменным класса
Давным давно помню была такая фишка в сях, когда приходилось много раз писать конструкцию типа "VarName->member()" можно было заключить это в некоторый блок кода внутри которого можно было напрямую использовать member(). Может кто-нибудь напомнить? Заранее спасибо.
C++ Как определить какой массив ест память http://www.cyberforum.ru/cpp-beginners/thread338216.html
В проге куча всяких массивов в том числе глобальных Со временем объем занимаемой оперативной памяти начинает расти, прога пишет всякие данные в массивы в бесконечном цикле в коде не использую ни malloc/free ни new/delete 1) правильно понимаю что есть память увеличиваясь со временем может только глобальный массив ? или массив внутри функции тоже может после инициализации увеличить объем...
C++ ООП Подскажите статью или книгу где рассказывается про динамические списки (с указателями,ссылками,динамической памятью и классами знаком) подробнее

Показать сообщение отдельно
ValeryLaptev
Эксперт С++
1010 / 789 / 46
Регистрация: 30.04.2011
Сообщений: 1,598
02.08.2011, 12:35     Стек!
Цитата Сообщение от murod Посмотреть сообщение
так я получу ответ на свой главный вопрос ? т. е о задаче ?
Вот тебе про реализацию динамического массива. Тут много дополнительного, ченго тебе не нужно. Ну так ломать - не строить, выкинешь.


Динамический массив

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

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

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

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

Большинство методов очень просты, поэтому реализованы непосредственно в классе. Операции доступа по индексу используют для проверки индекса ту же приватную функцию rangecheck(), что и в классе SimpleArray (см. листинг 7.4).

В классе три поля: указатель на выделенную память elems, поле Size определяет количество зарезервированных элементов, а поле Count содержит количество присутствующих в массиве элементов. Очевидно, что поле Count увеличивается по мере добавления элементов в массив. Как только значение поля Count сравняется со значением поля Size, необходимо выделять новую память.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// добавление элементов
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;                         // «увеличили «мощность»
  }
}
Метод resize() предназначен для увеличения размера зарезервированной памяти. Уменьшить размер выделенной памяти нельзя. Работает он просто: резервируется память для нового массива большего размера, туда копируются элементы текущего массива, после чего «старая» память возвращается.

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

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

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

Соответственно, для удаления элемента вполне подходит операция -=. Однако имена методов push_back() и pop_back() выбраны сознательно. Как мы увидим далее, реализованный нами шаблон растущего динамического массива очень похож на последовательный контейнер vector из стандартной библиотеки STL.
 
Текущее время: 16:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru