C++ Tablice Dynamiczne

Question

Witam wszystkich. Z uwagi na to że jestem początkującym programistą mam do was pytanie. Otóż jak można dynamicznie zwiększać rozmiar tablicy? Tzn deklaruję sobie tablicę o rozmiarze 5 i chciałbym zwiększać jej rozmiar o 1 przez funkcję by dodawać nowe elementy i jak można później sprawdzić rozmiar tej tablicy by upewnić się że wszystko działa poprawnie? Z góry dziękuję za odpowiedzi i pozdrawiam :)

Answer 1

Nie baw się w wymyślanie koła na nowo. Użyj po prostu klasy std::vector.
Tutaj masz dokumentację jak jej używać, ale z łatwością znajdziesz materiały po Polsku.

Answer 2

• tworzysz nową tablicę o jeden element większą.

  size_t n = 5;
  T *tab = new T[n];
  ...
  
  T *new_tab = new T[n + 1];
  
  

   

• kopiujesz zawartość starej tablicy do nowej.

  copy(tab, tab + n, new_tab);

   

• starą usuwasz.

  delete[] tab;
  tab = new_tab;
  ++n;

   

Ale jeśli nie musisz, użyj wspomnianego vectora.

Answer 3

Zaalokować większy blok pamięci, przekopiowiać stary blok do nowego i zwolnić stary. Sprawdzić rozmiaru nie masz jak. Musisz go sobie gdzieś na bieżąco zapisywać. Z resztą - dokładnie to realizuje std::vector, więc nie ma potrzeby pisać tego samemu.

Comments

Przy każdym push backu tablica jest kopiowana?

---

Jasne, że nie :D To by było zabójcze. Z reguły przy każdej alokacji tablicy rozmiar jest zdwukrotniany (czyli praktycznie zawsze jest jakiś overhead), ale nie wiem czy to jest standaryzowane.

---

Ze standardu C++14 nt. metod emplace_back i push_back [23.3.6.5]:

Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor, move constructor, assignment operator, or move assignment operator of T or by any InputIterator operation there are no effects. If an exception is thrown while inserting a single element at the end and T is CopyInsertable or is_nothrow_move_constructible::value is true, there are no effects. Otherwise, if an exception is thrown by the move constructor of a non-CopyInsertable T, the effects are unspecified.  

Więc najwyraźniej standard w ogóle nie definiuje jak dużo vector powinien zaalokować przy "powiększaniu" wewnętrznej tablicy. Pierwsze, pogrubione zdanie jest w zasadzie jedynym mówiącym cokolwiek o alokacji.

---

Na GCC jest razy o 100%, ale na MSVC rozmiar zwiększany jest średnio o 2/3 poprzedniej wartości.

---

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v(50);
    v.emplace_back();
    std::cout << v.capacity();
}

Output:
gcc 8: 100
clang 6: 100
msvc 19*: 75

* 19 to ten z VS2015

---

Ja sprawdzałem taki przykład:

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> ints;

	for (int i = 0; i < 10000; i++)
	{
		ints.push_back(3);

		if (ints.size() == ints.capacity())
		{
			std::cout << ints.capacity() << "\n";
		}
	}
}