Beispiellösung

Content

#ifndef ARRAY_HPP
#define ARRAY_HPP

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iterator>
#include <new>
#include <utility>

template<typename T>
class Array {
   private:
      using Tag = enum {AllocateStorage};
      Array(Tag tag, std::size_t size) :
	 size(size),
	 data(size > 0?
	       static_cast<T*>(operator new(sizeof(T) * size))
	    :
	       nullptr) {
      }
   public:
      Array() : size(0), data(nullptr) {
      }
      Array(std::size_t size) : Array(AllocateStorage, size) {
	 for (std::size_t index = 0; index < size; ++index) {
	    new (data + index) T();
	 }
      }
      Array(std::size_t size, const T& t) : Array(AllocateStorage, size) {
	 for (std::size_t index = 0; index < size; ++index) {
	    new (data + index) T(t);
	 }
      }
      template<typename Iterator>
      Array(Iterator it1, Iterator it2) :
	    Array(AllocateStorage, std::distance(it1, it2)) {
	 std::size_t index = 0;
	 while (it1 != it2 && index < size) {
	    new (data + index++) T(*it1++);
	 }
	 size = index; // just in case
      }
      Array(const Array& other) : Array(AllocateStorage, other.size) {
	 for (std::size_t index = 0; index < size; ++index) {
	    new (data + index) T(other.data[index]);
	 }
      }
      friend void swap(Array& a1, Array& a2) {
	 using std::swap;
	 swap(a1.size, a2.size);
	 swap(a1.data, a2.data);
      }
      Array(Array&& other) : Array() {
	 swap(*this, other);
      }
      ~Array() {
	 for (std::size_t index = 0; index < size; ++index) {
	    data[index].~T();
	 }
	 operator delete(data);
      }
      Array& operator=(Array other) {
	 swap(*this, other);
	 return *this;
      }
      std::size_t get_size() const {
	 return size;
      }
      T& operator()(std::size_t index) {
	 assert(index < size);
	 return data[index];
      }
      const T& operator()(std::size_t index) const {
	 assert(index < size);
	 return data[index];
      }
      T* begin() {
	 return data;
      }
      const T* begin() const {
	 return data;
      }
      T* end() {
	 return data + size;
      }
      const T* end() const {
	 return data + size;
      }
   private:
      std::size_t size;
      T* data;
};

#endif
#include <iostream>
#include "array.hpp"

int main() {
   int values[] = {2, 3, 5, 7, 11, 13};
   std::size_t dim = sizeof(values)/sizeof(values[0]);
   Array<int> a(values, values + dim);
   for (std::size_t index = 0; index < a.get_size(); ++index) {
      std::cout << " " << a(index);
   }
   std::cout << std::endl;
}
theon$ g++ -Wall -o test1 test1.cpp
theon$ valgrind ./test1
==2111== Memcheck, a memory error detector
==2111== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2111== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2111== Command: ./test1
==2111== 
 2 3 5 7 11 13
==2111== 
==2111== HEAP SUMMARY:
==2111==     in use at exit: 5,128 bytes in 1 blocks
==2111==   total heap usage: 3 allocs, 2 frees, 77,856 bytes allocated
==2111== 
==2111== LEAK SUMMARY:
==2111==    definitely lost: 0 bytes in 0 blocks
==2111==    indirectly lost: 0 bytes in 0 blocks
==2111==      possibly lost: 5,128 bytes in 1 blocks
==2111==    still reachable: 0 bytes in 0 blocks
==2111==         suppressed: 0 bytes in 0 blocks
==2111== Rerun with --leak-check=full to see details of leaked memory
==2111== 
==2111== For counts of detected and suppressed errors, rerun with: -v
==2111== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ 

Zur Frage zu test2.cpp:

#include <iostream>
#include <iterator>
#include "array.hpp"

int main() {
   std::istream_iterator<int> it(std::cin);
   std::istream_iterator<int> end;
   Array<int> a(it, end);
   for (std::size_t index = 0; index < a.get_size(); ++index) {
      std::cout << " " << a(index);
   }
   std::cout << std::endl;
}
theon$ g++ -Wall -o test2 test2.cpp
theon$ echo 1 2 3 | valgrind ./test2
==2145== Memcheck, a memory error detector
==2145== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2145== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2145== Command: ./test2
==2145== 
 1
==2145== 
==2145== HEAP SUMMARY:
==2145==     in use at exit: 10,256 bytes in 2 blocks
==2145==   total heap usage: 4 allocs, 2 frees, 82,972 bytes allocated
==2145== 
==2145== LEAK SUMMARY:
==2145==    definitely lost: 0 bytes in 0 blocks
==2145==    indirectly lost: 0 bytes in 0 blocks
==2145==      possibly lost: 10,256 bytes in 2 blocks
==2145==    still reachable: 0 bytes in 0 blocks
==2145==         suppressed: 0 bytes in 0 blocks
==2145== Rerun with --leak-check=full to see details of leaked memory
==2145== 
==2145== For counts of detected and suppressed errors, rerun with: -v
==2145== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ 

Das Problem ist hier, dass es sich bei std::istream_iterator um einen Input-Iterator handelt und nicht um einen Forward-Iteratoren, d.h. ein Inkrement verkonsumiert und ein Weg zurück ist nicht möglich. Werfen wir einen Blick auf den zum Einsatz kommenden Konstruktor:

template<typename Iterator>
Array(Iterator it1, Iterator it2) :
      Array(AllocateStorage, std::distance(it1, it2)) {
   std::size_t index = 0;
   while (it1 != it2 && index < size) {
      new (data + index++) T(*it1++);
   }
   size = index; // just in case
}

Bevor wir hier zum Kopierkonstruieren kommen, wird std::distance aufgerufen, das auf die triviale Methode mit linearem Aufwand zurückkommen muss, die etwa wie folgt aussieht:

template<typename Iterator>
std::ptrdiff_t distance(Iterator it1, Iterator it2) {
   std::ptrdiff_t count = 0;
   while (it1 != it2) {
      ++count; ++it1;
   }
   return count;
}

Nachdem std::distance aufgerufen worden ist, haben wir die zwei Iteratoren it1 und it2, die nicht gleich sind, wodurch wir beim ersten Mal in die Schleife eintreten. Bei std::istream_iterator wird nicht beim Dereferenzieren gelesen. Stattdessen wird das erste Element beim Konstruieren eingelesen, die späteren folgen beim Inkrementieren. Wenn beim Inkrementieren das Eingabe-Ende erkannt wird, entsteht daraus der Ende-Iterator. Somit wird der erste eingelesene Wert, der bei it1 gespeichert ist, noch übertragen. Das Inkrement stellt das Eingabe-Ende erneut fest und liefert den Ende-Iterator, so dass die Schleife nach der ersten Iteration endet. Somit haben wir den lästigen Fall, dass wir weniger Elemente bekommen haben als ursprünglich geplant. Was tun? Der einfachste Weg besteht darin, die Größe size anzupassen mit der unangenehmen Konsequenz, dass ein Teil des Speichers verschwendet wird. (Das ließe sich zwar mit Hilfe von std::realloc lösen, aber der Aufwand lohnt sich nicht, da es nicht sinnvoll ist, ein festzudimensionierendes Array mit Input-Iteratoren zu initialisieren, die nicht die Fähigkeiten eines Forward-Iterators haben.

Die nächsten vier Tests klappen auch wie erwartet:

#include <iostream>
#include <iterator>
#include "array.hpp"

struct Integer {
   Integer() : value(42) {
   }
   int value;
};
std::istream& operator>>(std::istream& in, Integer& i) {
   return in >> i.value;
}
std::ostream& operator<<(std::ostream& out, Integer i) {
   return out << i.value;
}

int main() {
   std::istream_iterator<Integer> it(std::cin);
   std::istream_iterator<Integer> end;
   Array<Integer> a(it, end);
   for (std::size_t index = 0; index < a.get_size(); ++index) {
      std::cout << " " << a(index);
   }
   std::cout << std::endl;
}
#include <iostream>
#include "array.hpp"

struct Integer {
   Integer(int value) : value(value) {
   }
   int value;
};

std::ostream& operator<<(std::ostream& out, Integer i) {
   return out << i.value;
}

int main() {
   Integer values[] = {2, 3, 5, 7, 11, 13};
   std::size_t dim = sizeof(values)/sizeof(values[0]);
   Array<Integer> a(values, values + dim);
   for (std::size_t index = 0; index < a.get_size(); ++index) {
      std::cout << " " << a(index);
   }
   std::cout << std::endl;
}
#include <iostream>
#include "array.hpp"

int main() {
   int values[] = {2, 3, 5, 7, 11, 13};
   std::size_t dim = sizeof(values)/sizeof(values[0]);
   Array<int> a(values, values + dim);
   for (auto value: a) {
      std::cout << " " << value;
   }
   std::cout << std::endl;
}
#include <iostream>
#include "array.hpp"

template<typename T>
void print_array(const Array<T>& a) {
   for (auto value: a) {
      std::cout << " " << value;
   }
   std::cout << std::endl;
}
int main() {
   int values[] = {2, 3, 5, 7, 11, 13};
   std::size_t dim = sizeof(values)/sizeof(values[0]);
   Array<int> a(values, values + dim);
   print_array(a);
}
theon$ g++ -Wall -o test3 test3.cpp
theon$ echo 1 2 3 | valgrind ./test3
==2171== Memcheck, a memory error detector
==2171== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2171== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2171== Command: ./test3
==2171== 
 1
==2171== 
==2171== HEAP SUMMARY:
==2171==     in use at exit: 10,256 bytes in 2 blocks
==2171==   total heap usage: 4 allocs, 2 frees, 82,972 bytes allocated
==2171== 
==2171== LEAK SUMMARY:
==2171==    definitely lost: 0 bytes in 0 blocks
==2171==    indirectly lost: 0 bytes in 0 blocks
==2171==      possibly lost: 10,256 bytes in 2 blocks
==2171==    still reachable: 0 bytes in 0 blocks
==2171==         suppressed: 0 bytes in 0 blocks
==2171== Rerun with --leak-check=full to see details of leaked memory
==2171== 
==2171== For counts of detected and suppressed errors, rerun with: -v
==2171== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ g++ -Wall -o test4 test4.cpp
theon$ valgrind ./test4
==2190== Memcheck, a memory error detector
==2190== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2190== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2190== Command: ./test4
==2190== 
 2 3 5 7 11 13
==2190== 
==2190== HEAP SUMMARY:
==2190==     in use at exit: 5,128 bytes in 1 blocks
==2190==   total heap usage: 3 allocs, 2 frees, 77,856 bytes allocated
==2190== 
==2190== LEAK SUMMARY:
==2190==    definitely lost: 0 bytes in 0 blocks
==2190==    indirectly lost: 0 bytes in 0 blocks
==2190==      possibly lost: 5,128 bytes in 1 blocks
==2190==    still reachable: 0 bytes in 0 blocks
==2190==         suppressed: 0 bytes in 0 blocks
==2190== Rerun with --leak-check=full to see details of leaked memory
==2190== 
==2190== For counts of detected and suppressed errors, rerun with: -v
==2190== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ g++ -Wall -o test5 test5.cpp
theon$ valgrind ./test5
==2214== Memcheck, a memory error detector
==2214== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2214== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2214== Command: ./test5
==2214== 
 2 3 5 7 11 13
==2214== 
==2214== HEAP SUMMARY:
==2214==     in use at exit: 5,128 bytes in 1 blocks
==2214==   total heap usage: 3 allocs, 2 frees, 77,856 bytes allocated
==2214== 
==2214== LEAK SUMMARY:
==2214==    definitely lost: 0 bytes in 0 blocks
==2214==    indirectly lost: 0 bytes in 0 blocks
==2214==      possibly lost: 5,128 bytes in 1 blocks
==2214==    still reachable: 0 bytes in 0 blocks
==2214==         suppressed: 0 bytes in 0 blocks
==2214== Rerun with --leak-check=full to see details of leaked memory
==2214== 
==2214== For counts of detected and suppressed errors, rerun with: -v
==2214== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ g++ -Wall -o test6 test6.cpp
theon$ valgrind ./test6
==2238== Memcheck, a memory error detector
==2238== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2238== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2238== Command: ./test6
==2238== 
 2 3 5 7 11 13
==2238== 
==2238== HEAP SUMMARY:
==2238==     in use at exit: 5,128 bytes in 1 blocks
==2238==   total heap usage: 3 allocs, 2 frees, 77,856 bytes allocated
==2238== 
==2238== LEAK SUMMARY:
==2238==    definitely lost: 0 bytes in 0 blocks
==2238==    indirectly lost: 0 bytes in 0 blocks
==2238==      possibly lost: 5,128 bytes in 1 blocks
==2238==    still reachable: 0 bytes in 0 blocks
==2238==         suppressed: 0 bytes in 0 blocks
==2238== Rerun with --leak-check=full to see details of leaked memory
==2238== 
==2238== For counts of detected and suppressed errors, rerun with: -v
==2238== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
theon$ 

Der letzte Test initialisiert nicht das Array, weil es sich bei value um eine lokale Kopie handelt, wenn wir diese verändern, hat dies keinen Effekt:

#include <iostream>
#include "array.hpp"

int main() {
   Array<int> a(3);
   for (auto value: a) {
      value = 42;
   }
   for (auto value: a) {
      std::cout << " " << value;
   }
   std::cout << std::endl;
}
theon$ g++ -Wall -o test7 test7.cpp
test7.cpp: In function 'int main()':
test7.cpp:6:14: warning: variable 'value' set but not used [-Wunused-but-set-variable]
    for (auto value: a) {
              ^~~~~
theon$ ./test7
 0 0 0
theon$ 

Das Problem lässt sich lösen, wenn wir mit einer Referenz arbeiten:

#include <iostream>
#include "array.hpp"

int main() {
   Array<int> a(3);
   for (auto& value: a) {
      value = 42;
   }
   for (auto value: a) {
      std::cout << " " << value;
   }
   std::cout << std::endl;
}
theon$ g++ -Wall -o test8 test8.cpp
theon$ ./test8
 42 42 42
theon$ 

Oder explizit mit Iteratoren:

#include <iostream>
#include "array.hpp"

int main() {
   Array<int> a(3);
   for (auto it = a.begin(); it != a.end(); ++it) {
      *it = 42;
   }
   for (auto value: a) {
      std::cout << " " << value;
   }
   std::cout << std::endl;
}
theon$ g++ -Wall -o test9 test9.cpp
theon$ ./test8
 42 42 42
theon$