Creating a Container Class

benjelly (80)
I think that most of the C++ STL (standard template library) is overdone. I guess they employed a good structure, yet I kind of don't like it. There's all those strange classes in the back-end. It's a lot of layers...

So now I want to make a smaller, more compact and modern container. All I could care for is a dynamic array:

1
2
3
4
5
6
7
8
9
 
template<typename ContentType>
class DynamicArray
{
public:
	DynamicArray(ContentType entityDefault);
	void Add(ContentType entity);
	void Delete(unsigned int index);
	ContentType Get(unsigned int index);
};


What do I need to do to make this functional?
Athar (4466)
I guess they employed a good structure, yet I kind of don't like it.

It's more likely that you just don't understand it. Pick up a good C++ book of your choice to rectify that (I recommend the C++ Primer).

There's all those strange classes in the back-end. It's a lot of layers...

What are you talking about?

All I could care for is a dynamic array:

That is called std::vector.

So now I want to make a smaller, more compact

Going to be hard. The container classes in C++ only provide the bare minimum functionality anyway.

What do I need to do to make this functional?

You need to write more code. Seriously, what do you actually want to know?
Last edited on
rapidcoder (1010)
The OP idea is not that bad. The STL's love for iterators is plain wrong for multicore. Iterator is a sequential concept, single-threaded by nature. So, what I would be very willing to see is some another standard collection library designed with massive parallelization in mind.

Something like:

1
2
3
4
5
6
 
void someFunction(int x) { ... }

parallel_vector<int> myVector;
myVector.push_back(...); 
...
myVector.foreach(&someFunction);

Last edited on
simeonz (490)
@rapidcoder
Interesting point. Still, C++ is currently single-threaded. :) And this only shows that you need to extend the interface. I think there is hardly anything to remove from it.

@OP
Iterators are useful, because the underlying structures for node-based containers have separate seeking and manipulation toll. For example, the complexity of deleting in a list is constant once you have located the node (without the deallocation toll), but seeking to the node is linear. Seeking to the next element in a set (in sorted order) takes constant time, but seeking to arbitrary element takes linear time. Iterators facilitate the seeking part, while the containers provide removal, insertion, etc., once the seeking is done.

Regards
closed account (zb0S216C)
How do you plan to optimize this more modern dynamic array class to make it faster at iteration? Are the elements created on the stack or the heap? Limitations? Safety measures( for example: Index range validation, element validation, etc... )?

If you're designing a new template container, you must have some sort of documentation to show?

Those strange classes have a purpose. It's best not to mess with them.

Define overdone.
benjelly (80)
Yeah I'm not very experienced with the STL's internals. But they're very old.. What about Thread Building Blocks' concurrent_vector class? Isn't that better?

Edit:
Hey wait, a new C++ ?
http://www2.research.att.com/~bs/C++0xFAQ.html
Last edited on
closed account (zb0S216C)
Yes, C++ 0x is the new C++. I'm not too sure if it's been released yet, but, I would love to get my hands on it.
firedraco (6246)
It's not yet...unfortunately. However, since vendors basically already know what's in it, most compilers have some of the features already there.
benjelly (80)
Relating to the original topic:
I can just use dynamic memory.. Aha, I think I got this figured out now!
benjelly (80)
Okay, I completed this. Please review the code and tell me how I can make it better... I actually ended up writing it in C, but my next one will be in 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
typedef struct dArray
{
	HandleMemory memoryPool;
	size_t elementSize;
	unsigned long size;
	unsigned long capacity;
	unsigned short flags;
} dArray, *pdArray;

short dArraySetup(pdArray *captureHandle, size_t givenElementSize, unsigned long givenCapacity, unsigned short givenFlags)
{
	#ifndef DARRAY_OPTIMIZE
	if (!captureHandle) return ERROR_DOES_NOT_EXIST;
	#endif

	if (!(*captureHandle))
	{
		*captureHandle = (pdArray) malloc(sizeof(dArray));
		if (!(*captureHandle)) return ERROR_FAILED;

		dArray newArray = {0,0,0,0,0};
		**captureHandle = newArray;
	}

	if ((*captureHandle)->flags&FLAG_ON || (*captureHandle)->memoryPool)
	{
		return ERROR_ALREADY_EXISTS;
	}
	else
	{
		if (givenElementSize && givenCapacity && !(givenFlags&DARRAY_FLAG_READ_ONLY))
		{
			(*captureHandle)->memoryPool = malloc(givenCapacity*givenElementSize);

			if ((*captureHandle)->memoryPool)
			{
				(*captureHandle)->elementSize = givenElementSize;
				(*captureHandle)->size = 0;
				(*captureHandle)->capacity = givenCapacity;
				(*captureHandle)->flags = FLAG_ON | givenFlags;

				return FLAG_ON;
			}

			return ERROR_FAILED;
		}
	}

	return ERROR_BAD_ARGUMENT;
}

short dArrayFree(pdArray *givenHandle)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_DOES_NOT_EXIST;
	if (!(*givenHandle)) return ERROR_DOES_NOT_EXIST;
	#endif

	free((*givenHandle)->memoryPool);

	(*givenHandle)->memoryPool = 0;
	(*givenHandle)->elementSize = 0;
	(*givenHandle)->size = 0;
	(*givenHandle)->capacity = 0;
	(*givenHandle)->flags = 0;

	free(*givenHandle);
	*givenHandle = 0;

	return 1;
}

short dArraySetCapacity(pdArray givenHandle, unsigned long givenCapacity)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_DOES_NOT_EXIST;
	#endif

	if (givenHandle->flags&DARRAY_FLAG_FIXED_CAPACITY) return ERROR_FAILED;
	if (givenCapacity <= givenHandle->size) return ERROR_BAD_ARGUMENT;

	/* We create a memoryBuffer to be the new memory pool */
	HandleMemory memoryBuffer = malloc(givenCapacity*givenHandle->elementSize);
	if (!memoryBuffer) return ERROR_FAILED;

	/* If data exists in the memoryPool, we transfer it to the memoryBuffer: */
	if (givenHandle->size)
	{
		memmove(memoryBuffer, givenHandle->memoryPool, givenHandle->size*givenHandle->elementSize);
	}

	free(givenHandle->memoryPool);

	givenHandle->memoryPool = memoryBuffer;
	givenHandle->capacity = givenCapacity;

	return 1;
}

/* dArrayAddElement returns a negative if it has problems,
 * Otherwise, it will give you a positive long-integer of the new element's
 * index */

long dArrayAddElement(pdArray givenHandle, void *givenElement)
{
	#ifndef QARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_BAD_ARGUMENT;
	#endif

	if (givenHandle->flags&DARRAY_FLAG_READ_ONLY) return ERROR_FAILED;
	if (givenHandle->size >= givenHandle->capacity)
	{
		if (givenHandle->flags&DARRAY_FLAG_FIXED_CAPACITY)
		{
			return ERROR_FAILED;
		}
		else
		{
			if (!dArraySetCapacity(givenHandle, (givenHandle->capacity+1)*1.5)) return ERROR_FAILED;
		}
	}

	memmove(
		givenHandle->memoryPool + givenHandle->size*givenHandle->elementSize,
		givenElement,
		givenHandle->elementSize);

	++givenHandle->size;
	return 1;
}

short dArrayGetElement(pdArray givenHandle, void *captureElement, unsigned long givenIndex)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_BAD_ARGUMENT;
	#endif

	if (givenIndex >= givenHandle->size) return ERROR_BAD_ARGUMENT;

	memmove(
		captureElement,
		givenHandle->memoryPool + givenIndex*givenHandle->elementSize,
		givenHandle->elementSize);

	return 1;
}

short dArraySetElement(pdArray givenHandle, void *givenElement, unsigned long givenIndex)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_BAD_ARGUMENT;
	#endif

	if (givenHandle->flags&DARRAY_FLAG_READ_ONLY) return ERROR_FAILED;
	if (givenIndex >= givenHandle->size) return ERROR_BAD_ARGUMENT;

	memmove(
		givenHandle->memoryPool + givenIndex*givenHandle->elementSize,
		givenElement,
		givenHandle->elementSize);

	return 1;
}

short dArrayRemoveElement(pdArray givenHandle, unsigned long givenIndex)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_BAD_ARGUMENT;
	#endif

	if (givenHandle->flags&DARRAY_FLAG_READ_ONLY) return ERROR_FAILED;
	if (givenIndex >= givenHandle->size) return ERROR_BAD_ARGUMENT;

	if (givenIndex+1 != givenHandle->size)
	memmove(
		givenHandle->memoryPool + givenIndex*givenHandle->elementSize,
		givenHandle->memoryPool + (givenIndex + 1)*givenHandle->elementSize,
		givenHandle->elementSize * (givenHandle->size-1-givenIndex));

	--givenHandle->size;

	return 1;
}

unsigned long dArrayGetSize(pdArray givenHandle)
{
	if (givenHandle)
	{
		return givenHandle->size;
	}

	return 0;
}

unsigned long dArrayGetCapacity(pdArray givenHandle)
{
	if (givenHandle)
	{
		return givenHandle->capacity;
	}

	return 0;
}

size_t dArrayGetByteSize(pdArray givenHandle)
{
	if (givenHandle)
	{
		return givenHandle->elementSize*givenHandle->size;
	}

	return 0;
}

short dArrayGetPool(pdArray givenHandle, HandleMemory *capturePool)
{
	#ifndef DARRAY_OPTIMIZE
	if (!givenHandle) return ERROR_BAD_ARGUMENT;
	#endif

	capturePool = givenHandle->memoryPool;

	return 1;
}


After I get rid of the imperfections, I want to take it a step further... does anyone want to explain how a "concurrent vector" actually works?
Last edited on
benjelly (80)
bumpedy bump... anyone to help?
Topic archived. No new replies allowed.