How to insert a single value into every array alement?

I am currently using this code...

for (int i = 0; i < m_size; i++)
m_array[i] = EMPTY_CELL;

EMPTY_CELL is -666.
m_array is a dynamic array pointing to an integer.

Instead of using an O(n) algorithm I'm just wondering if there's a faster way using mem* or other functions? The reason why I'm interested is because EMPTY_CELL is a constant, so it seems like there may be a faster way than having to go through every single element in the array. But even if there was a C/C++ function for this, I can only guess it's O(n) too. But I thought I'd ask anyway so I can lay this idea to rest. Thanks!

The built-in C++ vector constructor is also linear on n; and I don't see any way to get something much faster (I don't see much gain in trying to copy 1, then 2, then 4, then ... elements).

Alright, thanks!

There is no way to get better than O(n). The C++ function to do this is fill, which is found in <algorithm>.

Depending on what you're doing, it may make sense to use a vector and resize it to zero items.

How could you possibly store n values into n slots without performing at least n operations? That would be pure magic.

Well, the line

Code:

---

fread(array, sizeof(array), 1, inFile);

---

sure looks like one operation (with array defined properly, etc.) although who knows what it turns into on the machine level.

It can be done by copying one sequence of memory with the desired pattern into our array.

For example if we have an array of 100 pointers and we want to make them null, all we need is to copy 100*4 byte of null bytes to our array. Sure we should have this 400 bytes of sequential null bytes somewhere in memory.

Think we have an array of

Code:

---

struct student
{
      char name[80];
      int      mark;
};

---

Then we make an array.

Code:

---

student students[100];

---

Students is a sequence of bytes 80 for name 4 for mark, 80 for name 4 for mark.
If we place a sequence with the same pattern somewhere in memory, for example 80 null bytes plus four bytes for a specific integer (for example zero) and we repeat it 100 times. Then we can fill our students array.

If we have an array in our program that we want to fill it with predefined values so many times we instantiate an array with those values and copy it to the array we want to fill.

In short we have to have an image of the array with predefined values and copy it to the array which we want to refresh, initialize, etc

Quite simple really ;)

Any loop in your program runs in O(N)
Any loop hidden inside an API call runs in O(1)

Obvious really :D ;) :p




If you bought that, I've got a jar of scotch mist for sale.....

I'm wading into waters deeper than my ken, since my assembly knowledge is nil, but my rough point was this: say I'm copying 16 shorts in an array. Would that necessarily turn into 16 machine operations (which is what I'm reading brewbuck to claim)? I would think that maybe I would get 8 4-byte copies (or something similar, alignment, etc.). It's still O(n), n/2 is still O(n), but it's not really n operations.

*agrees with tabstop*
Big-O ignores all scale factors, so whether the actual operation is accomplished in N/2 machine operations, or 100*N machine operations, it's still O(N).

Also, Big-O only works for large (asympotic) values on N on abstract machines.
Small N on real machines can show very different results.

mem copy is O(N), but has potential of being much faster than a filler loop in the code.