[C++] Resetting a pointers position

[Da)sniper]

I have an array with 16 data members and a pointer that can be at any position at any given time. If I want to reset the pointer so that it can go back through the array again what exactly should I do?

I tried:

myPointer -= 16;

But my biggest concern is that this will go into RAM with some awkward negative index for the array.

 

[edo494]

if you know at which position it is you can do something like this:

    int myKnownOffset = ...;
    type* ptr = ...;

    //do something
    
    ptr -= myKnownOffset * sizeof(ptr);

alternativelly you can at the beginning(before manipulation) take an address of the beginning of the sequence, and then set it to that so you effectivelly reset it:

type* mainPointer = ...;
type* startSequence = mainPointer;

//do stuff

mainPointer = startSequence;

 

[Da)sniper]

Thanks! Yeah I don't know exactly where it will land so that's out but the second suggestion should work quite nicely.

 

[edo494]

I forgot to mention, but the second pointer can even be const cause you most likely dont want it to change(type* const pointer = otherPointer

 

[Dr Super Good]

Alternatively you can perform an array lookup instead of incrementing the pointer. Depending on how the compiler and processor implement it, it may have equal or less overhead.

 

[Da)sniper]

That seems interesting, but how exactly would that work out?

 

[Dr Super Good]

Instead of a pointer that can be at any position of the array at any time, you have a pointer to the base of the array and an index integer representing the offset from the array base. Setting the index integer to 0 will always return it to the base.

You access elements the same way you would if the pointer was an array (hint, arrays are pointers). Speed wise it should make little difference and may even be faster since pointers always have to be pointer type bytes where as the index type can be smaller. Technically it will have to compute an effective address every instruction which might make you think it is slower but that depends on how the processor is pipelined (it may go through that step for every instruction anyway, or just use an idle arithmetic unit that would otherwise do nothing).

 

[Magtheridon96]

Why the hell are you doing this in C++? It's 2014, not 1994.

 

[edo494]

maybe low level stuff, or never heard of smart pointers. One cant know, but pointers are there to use, so I see no problem why you should jump on people using pointers

 

[Magtheridon96]

His goal is to use an array of data.

A pointer is definitely not a solution unless you're using it like an iterator for a bunch of algorithms.

 

[Dr Super Good]

Why the hell are you doing this in C++? It's 2014, not 1994.

Because he wants something that...
1. Works.
2. Does not consume many times the resources it should.
I mean that is why most people use C++ still.

A pointer is definitely not a solution unless you're using it like an iterator for a bunch of algorithms.

Yes he should be use references rather!

In C++ References are preferred to pass objects around since they have more strict constraints that are useful to prevent strange bugs. Pointers are mostly used in pure C code as C code is generally less type safe.

 

[Magtheridon96]

His solution is much more prone to error. A std::vector<T> or a std::array<T> is superior.
So what if std::vector<T> takes a bit more memory than a raw block of memory representing an equally sized array?
(I doubt he's writing software for a micro-controller. Hopefully.)

std::vector<T> on Microsoft's implementation has a size of 24 bytes and it will allocate a block that has a size greater than or equal to the size of the array it represents.
The memory overhead is negligible. When we're talking about operations like look-ups and the like, with optimizations enabled, a std::vector<T> will give you the same results as an array.

If passing around objects was the problem, yes, references would be the solution, but OP doesn't show any code, so I don't know what he's aiming for exactly.

 

[GhostWolf]

Or, you know, just use an array. Because, quite surprisingly, an array acts like an array, and you can even index it like an array.

 

[Magtheridon96]

That too. It depends on how you expect to size it and what you expect to do with it.
std::vector gives you a dynamic array and std::array<T, N> gives you the equivalent of T[N] with a bunch of member functions for convenience. In other cases, T[N] is good enough :v

 

[Da)sniper]

Why the hell are you doing this in C++? It's 2014, not 1994.

Simplistic answer; it's what I know and I really don't feel like fumbling around with my little knowledge of other languages.

but OP doesn't show any code, so I don't know what he's aiming for exactly.

Sorry about that, most of my work so far is highly conceptual based with some small attempts to get certain parts working, therefore not much code to really show you.

If passing around objects was the problem

It somewhat is and isn't. Currently this is the solution I've come up with, I'm trying not to pass arrays or vectors into functions simply due to the principle; it wastes a good bit of memory.


I'm not working with vectors because my knowledge on them is very primitive especially for what I'm trying to create, also not using matrices (not sure if that was what you were getting at) because I have no knowledge of them whatsoever.

Granted I'm still an undergrad so I'm sure I'm probably incorrect about most of my ideals, sorry in advanced.

 

[GhostWolf]

// No overhead, passing a pointer
void func(int *array) {
    array[15] = 9001;
}

// No overhead, passing a reference (aka a pointer)
void func(std::vector<int> &array) {
    array[15] = 9001;
}

int main() {
    int array[16];
    std::vector<int> array2(16);
    
    func(array);
    func(array2);
    
    return -PI/3; // 3 slices of PI
}

BA DAM TUSH.

 

[edo494]

vector is the standard type for dynamic arrays in C++, learn it

One reference of vector
Another one

 

[Magtheridon96]

There is no matrix in the C++ standard at the moment unfortunately. (No one can really agree on what you would want out of a matrix in terms of the API)

A vector is not hard to use:

// Default vector of size 0 initially
std::vector<int> v1;
// Append 3 to the end
v1.push_back(3);
// Append 42 to the end
v1.push_back(42);


// Vector of size 10 initialized all values being 4
std::vector<int> v2(10, 4);
// Change the 1st element to 7
v2[0] = 7;

// Display the sizes
std::cout << v1.size() << '\n';
std::cout << v2.size() << '\n';

Here's the proper reference

When you want to pass objects around to functions, you have several choices:

• Passing an instance void f(T t); or void f(const T t);
• Passing a reference void f(T& t); or void f(T const& t);
• Passing an r-value reference void f(T&& t);

Disregard the last one though. For the sake of simplicity.
The first method of passing an instance will make a copy of the object (or a move in some cases, but I won't get into that) and passes it into the function. This copy is destroyed after the function execution is over.
The second method is the one you'd want to use most of the time. Why make a copy when you can just pass a reference to the object you have? It's about the same as using a pointer, but the difference is that a reference guarantees an object (assuming well-formed C++ and no bugs involving references to objects that no longer exist). A pointer can be null and that's a valid value. However, there is no such thing as a null reference (When you hit bugs involving them, it's because you have code somewhere that is misusing objects and not paying attention to object lifetimes).

Even if you pass an instance, unless we're talking about arrays that use millions of a primitive type or thousands of a complex one, you're not wasting enough memory to call for messing with pointers and shit when you can use more reliable constructs like vectors.

 

[Dr Super Good]

It depends entirely on what he wants done. Vector is great for an unbounded list that mostly stays the same size. It is not a replacement for an array however (use an array rather when possible) since it adds extra overhead. It is also not too good for real time applications as the dynamic array resizing has difficult to predict execution time and also requires costly memory allocation.

 

[edo494]

vector adds extra overhead? lol you must be kidding me

Vector's operator[] is so light that it has the exact same speed as reading array.

Arrays are old, C style code. They are dumb, they dont know their size, they cant grow. + you have stuff like iterators and whole lot of standard algorithms supporting containers like vector, whereas most of those algorithms dont work on plain arrays

edit: to prove what I said, here is sample:

#include <vector>
#include <ctime>
#include <cmath>
#include <iostream>

int main(int argc, char** argv)
{
	std::vector<int> vec;
	int array[65536] = {0};
	
	srand(time(nullptr));

	int randomSet[65536] = {0};
	for(int i = 0; i < 65536; ++i)
	{
		randomSet[i] = rand();
	}

	long long a = __rdtsc();

	for(int i = 0; i < 65536; ++i)
	{
		array[i] = randomSet[i];
	}

	a = __rdtsc() - a;

	std::cout << "array: " << a << "\n";

	//resize before counting, because array is already preallocated
	vec.resize(65536, 0);

	a = __rdtsc();

	for(int i = 0; i < 65536; ++i)
	{
		vec[i] = randomSet[i];
	}

	a = __rdtsc() - a;

	std::cout << "vector: " << a << "\n";

	std::cin.get();
}

This prints roughly 39 - 43 for both, sometimes vector is even faster according to this test

edit: further prove:

This is how operator[] looks for vector in Visual studio 2012 standard library:

	reference operator[](size_type _Pos)
		{	// subscript mutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
		if (size() <= _Pos)
			{	// report error
			_DEBUG_ERROR("vector subscript out of range");
			_SCL_SECURE_OUT_OF_RANGE;
			}

 #elif _ITERATOR_DEBUG_LEVEL == 1
		_SCL_SECURE_VALIDATE_RANGE(_Pos < size());
 #endif /* _ITERATOR_DEBUG_LEVEL */

		return (*(this->_Myfirst + _Pos));
		}

_ITERATOR_DEBUG_LEVEL is only set in debug mode, as you may see, what this does is merely dereferences the pointer it has + offset, the very same thing that you will do with array

 

[Dr Super Good]

Vector's operator[] is so light that it has the exact same speed as reading array.

Care to explain to me the mechanics of how this is possible? I mean sure in a pipelined processor it may be masked by the parallelism but what about something with a smaller or less parallel pipeline? How can checking the bounds of something be faster than not checking the bounds?

They are dumb, they dont know their size, they cant grow.

Instructions are dumb...

edit: to prove what I said, here is sample:

Please learn computers before trying to be smart. This proves nothing because the timing involved is probably dominated by the OS scheduler and cache.

Especially since you pre-resize the vector, it probably writes to all elements assuring very good cache coherency resulting in it running faster than the array as the array has not been pre-traversed so is not very cache coherent.

The implementation of vector shown above does not feature automatic resizing, which is what I thought all vectors should do (Java does this). Obviously without automatic resizing it is an array and will perform like one since you ignore the bounds test. In fact why bother using a vector then since it is an array (just wrapped in nonsense so you do not need to manually manage allocation) and will still cause the same out of bounds failures.

 

[edo494]

Care to explain to me the mechanics of how this is possible? I mean sure in a pipelined processor it may be masked by the parallelism but what about something with a smaller or less parallel pipeline? How can checking the bounds of something be faster than not checking the bounds?

The thing is, it doesnt check the bounds if you are in release mode. Check the code I posted

Instructions are dumb...

How is this relevant?

Please learn computers before trying to be smart. This proves nothing because the timing involved is probably dominated by the OS scheduler and cache.

Especially since you pre-resize the vector, it probably writes to all elements assuring very good cache coherency resulting in it running faster than the array as the array has not been pre-traversed so is not very cache coherent.

sorry for not knowing everything -,- I will retest it in a moment

The implementation of vector shown above does not feature automatic resizing, which is what I thought all vectors should do (Java does this). Obviously without automatic resizing it is an array and will perform like one since you ignore the bounds test. In fact why bother using a vector then since it is an array (just wrapped in nonsense so you do not need to manually manage allocation) and will still cause the same out of bounds failures.

I shown you 1 function. Here is some resizing mumbo jumbo:

	void reserve(size_type _Count)
		{	// determine new minimum length of allocated storage
		if (capacity() < _Count)
			{	// something to do, check and reallocate
			if (max_size() < _Count)
				_Xlen();
			_Reallocate(_Count);
			}
		}

	void resize(size_type _Newsize)
		{	// determine new length, padding as needed
		if (_Newsize < size())
			erase(begin() + _Newsize, end());
		else if (size() < _Newsize)
			{	// pad as needed
			_Alty _Alval(this->_Getal());
			_Reserve(_Newsize - size());
			_TRY_BEGIN
			_Uninitialized_default_fill_n(this->_Mylast, _Newsize - size(),
				_Alval);
			_CATCH_ALL
			_Tidy();
			_RERAISE;
			_CATCH_END
			this->_Mylast += _Newsize - size();
			}
		}

	void resize(size_type _Newsize, const value_type& _Val)
		{	// determine new length, padding with _Val elements as needed
		if (_Newsize < size())
			erase(begin() + _Newsize, end());
		else if (size() < _Newsize)
			_Insert_n(end(), _Newsize - size(), _Val);
		}

vector is basically a wrapper around a POINTER, not ARRAY(there is std::array for that), which can grow and shrink as requested by user.

If you want bounds checking, you have to call .at(index offset), which will throw if you go out of the bounds

 

[Dr Super Good]

around a POINTER, not ARRAY

An array is a pointer...

You can de reference it or index it.
*somearray = 0;
somearray[0] = 0;

Both are the same.

When you allocate an array the only difference is you are guaranteeing that the result is a pointer to a location with N reserved elements of a certain type that were allocated for purpose.

Additionally constant arrays can be allocated in ROM via const type, which is very important for some architectures.

 

[edo494]

http://stackoverflow.com/questions/1641957/is-array-name-a-pointer-in-c
array is not pointer per se, but it decays to pointer

 

[edo494]

double post but eh:

#include <vector>
#include <ctime>
#include <cmath>
#include <iostream>

int main(int argc, char** argv)
{
    std::vector<int> vec;
    int array[65536] = {0};
   
    srand(time(nullptr));

    int randomSet[65536] = {0};
    for(int i = 0; i < 65536; ++i)
    {
        randomSet[i] = rand();
    }
	
	for(int i = 0; i < 65536; ++i)
	{
		array[i] = i;
	}

    long long a = __rdtsc();

    for(int i = 0; i < 65536; ++i)
    {
        array[i] = randomSet[i];
    }

    a = __rdtsc() - a;

    std::cout << "array: " << a << "\n";

    //resize before counting, because array is already preallocated
    vec.resize(65536, 0);

    a = __rdtsc();

    for(int i = 0; i < 65536; ++i)
    {
        vec[i] = randomSet[i];
    }

    a = __rdtsc() - a;

    std::cout << "vector: " << a << "\n";

    std::cin.get();
}

makes NO difference and the output is always almost the same for both arrays and vectors.

Vector IS as fast as array, there is no denying no matter how hard you try

 

[Magtheridon96]

Dr Super Good, all your issues with vector boil down to the fact that it is only heavier than a regular array in debug mode.

With optimizations, really, it is all the same. You aren't wrong about the extra checks without optimization. Who the hell releases a program to the public with optimizations off anyway?

There are rarely any genuine performance problems that call for using a pointer to a block of allocated memory instead of a vector.
You shouldn't worry about performance all the time for no really good reason, it's just too constraining and it's not that helpful in the end when instead, you can end up with maintainable and clean code that is less likely to fail due to human error (human error is a huge factor to take into consideration when dealing with code bases on the order of 1 million lines and you know that man ;/)

 

[GhostWolf]

No, you are wrong. That part that takes 0.1% of the program time could be faster by 2 nanoseconds, and that's a huge impact.
That being said, I hate the std syntax and constructs.

 

[edo494]

its not about the speed, but as I said, plain arrays are quite stupid, you can barely get their size and they have next to no support for algorithms in <algorithm>, whereas vector fits for all the algorithms pretty much, and is trivial to get his size

 

[Magtheridon96]

Well, sorta.

I mean, we have std::begin and std::end for arrays of type T[N].