in start I want to apologize for my english. My problem is weird because I'm trying write own ArrayList looks and works like List in Java and I know it's like reinvent a wheel, but I do this for fun and for better understanding how it works. So every answer like "use STL", "use vector", "use something else but don't create own list" are not helpful. So from start, I have own template to ArrayList with a few methods which are important for me. My ArrayList works as array where I use only a part of available space and if I need more space I create new bigger array and copy all old elements (I beleive that the way it works in Java ArrayList, tell me if I'm wrong). In array I store only pointers. And it is good template for save and remove known objects and if I only need read stored data, but real problem appear when I try write loop for read, check and remove specified element from list. I can not do this using standard for(int i=0;i
So can someone explain me what I should write in my template to support for-each functionality. In many examples appear begin() and end() functions but no one explain why this name, what is a return type and why, and what this method should return. Here is my template code, if something is wrong, please tell me. I will use this code in my other apps because for me this implementation is more intuition than vector (I was definitely too long works with Java :))
template <class T> class ArrayList {
public:
ArrayList() {
array = new T*[1000];
arraySize = 1000;
n = 0;
};
void add(T &arg) { //add new element at end
if (n == arraySize) {
increase();
}
array[n] = &arg;
n++;
};
void addAt(T &arg, unsigned int pos) { //add new element at specific position and override
if (pos >= 0 && pos <= n) {
if (pos == n) {
add(arg);
}
else {
array[pos] = &arg;
}
}
else {
throw "IndexOutOfBoundException";
}
};
void addAfter(T &arg, unsigned int pos) { //add new element between specific posittion and next element
pos++;
if (pos >= 0 && pos <= n) {
if (n == arraySize) {
increase();
}
for (unsigned int i = n; i > pos; i--) {
array[i] = array[i - 1];
}
array[pos] = &arg;
n++;
}
else {
throw "IndexOutOfBoundException";
}
};
void addList(ArrayList &list) { //add 'list' at the end
if (list.n > 0) {
while (list.n + n > arraySize) {
increase();
}
for (int i = 0; i < list.n; i++) {
array[n] = list.array[i];
n++;
}
}
};
void addListAfter(ArrayList &list, unsigned int pos) { //put 'list' inside list, start from 'pos'
pos++;
if (list.n > 0 && pos >= 0 && pos < n) {
while (list.n + n > arraySize) {
increase();
}
int m = n - 1;
while (m >= pos && m >= 0) {
array[m + list.n] = array[m];
m--;
}
for (int i = 0; i < list.n; i++) {
array[pos + i] = list.array[i];
}
n += list.n;
}
else {
throw "IndexOutOfBoundException";
}
};
void addListAfter(ArrayList &list, T &arg) { //put 'list' inside list, start after T, if T not exist 'list' will be added at the end
addListAfter(list, getIndex(arg));
};
void remove(T &arg, bool all) { //remove selected element if all=true remove all instance of object otherwise remove only first
if (all) {
int copies = 0;
for (int index = 0; index < n; index++) {
if (array[index] == &arg) {
copies++;
}
else if (copies != 0) {
array[index - copies] = array[index];
}
}
n -= copies;
if (copies == 0) {
throw "ArgumentNotFoundException";
}
while (arraySize - n >= 1000) {
decrease();
}
}
else {
remove(getIndex(arg));
}
};
void remove(unsigned int pos) { //remove element from specific position
if (pos >= 0 && pos < n) {
for (int i = pos; i < n - 1; i++) {
array[i] = array[i + 1];
}
n--;
if (arraySize - n >= 1000) {
decrease();
}
}
else {
throw "IndexOutOfBoundException";
}
};
void removeCopy(T &arg) { //leaves only one instance of an object and remove all other
int copies = -1;
for (int index = 0; index < n; index++) {
if (array[index] == &arg) {
copies++;
}
else if (copies > 0) {
array[index - copies] = array[index];
}
}
n -= copies;
if (copies == -1) {
n--;
throw "ArgumentNotFoundException";
}
while (arraySize - n >= 1000) {
decrease();
}
};
void repair() { //leaves only single instance of each object
for (int i = 0; i < n; i++) {
removeCopy(*array[i]);
}
};
void clear() { //remove all object from list
for (int i = 0; i < n; i++) {
array[i] = NULL;
}
n = 0;
};
T* get(unsigned int pos) { //return object on selected position
if (pos >= 0 && pos < n) {
return array[pos];
}
else {
throw "IndexOutOfBoundException";
}
};
unsigned int getIndex(T &arg) { //return position of selected object
unsigned int index = 0;
while (&arg != array[index] && index < n) {
index++;
}
if (index == n) {
throw "ArgumentNotFoundException";
}
return index;
};
ArrayList getSubList(unsigned int first, unsigned int last, bool deepCopy) { //return new list contains 'deep copy'/'copy reference' of all elements from (include) first to (include) last. If deepCopy=true function return deep copy, otherwise return copy of reference.
if (first < last&&first >= 0 && last < n) {
ArrayList<T> ret;
for (unsigned int i = first; i <= last; i++) {
if (deepCopy) {
ret.add(*new T(*array[i]));
}
else {
ret.add(*array[i]);
}
}
return ret;
}
throw "IndexOutOfBoundException";
};
unsigned int size() { //return size of list
return n;
};
bool isEmpty() {
return n == 0;
};
T *begin() {
return &*array[0];
}
T *end() {
return &*array[n];
}
private:
unsigned int arraySize; //actual size of array
unsigned int n; //number of elements in array
T** array;
void increase() { //increase size of array about 1000
if (arraySize + 1000 <= LONG_MAX) {
T** newArray = new T*[arraySize + 1000];
for (unsigned int i = 0; i < arraySize; i++) {
newArray[i] = array[i];
}
delete[] array;
array = newArray;
arraySize += 1000;
}
else {
throw "ArraySizeOutOfBoundException";
}
};
void decrease() { //decrease size of array about 1000
if (arraySize - 1000 > 0) {
arraySize -= 1000;
T** newArray = new T*[arraySize];
for (unsigned int i = 0; i < arraySize; i++) {
newArray[i] = array[i];
}
delete[] array;
array = newArray;
}
else {
throw "ArraySizeOutOfBoundException";
}
};
};
Some of the answers you've posted give good explanations. begin and end return iterators into a container, with begin referring to the first element and end to the position one item past the last element. As for the names, they seem intuitive. I believe this iterator design was chosen as an abstraction over pointers which would have minimal runtime cost.
I'm sure you've seen this link in the answers you linked to, but you should refer to this page on range-based for-loops.
In any case, you seem to be confused about the elements of the array vs. iterators pointing to the elements. With:
T **begin() {
return &array[0];
}
T **end() {
return &array[n];
}
Your program will work with ranged-for. Your element type is T*, not T.