Undefined values in dynamic arrays

Question

I am going through a book to refresh my memory on data structures and c++ and I am reading through implementing a bitvector. In my Bitvector class, I have the following:

class BitVector
{
  public:
    Bitvector(int p_size)
    {
      m_array = 0;
      m_size = 0;
      Resize(p_size);
    }

    ~Bitvector()
    {
      if(m_array !=0)
        delete[] m_array;
      m_array = 0;
    }

    void Resize(int p_size)
    {
      unsigned long int* newvector = 0;
      if(p_size % 32 == 0)
        p_size = p_size / 32;
      else
        p_size = (p_size /32) + 1;

      newvector = new unsigned long int[p_size];

      if(newvector == 0)
        return;
      int min;
      if(p_size < m_size)
        min = p_size;
      else
        min = m_size;
      int index;
      for(index = 0;index < min; index++)
        newvector[index] = m_array[index];
      m_size = p_size;
      if(m_array != 0)
        delete[] m_array;
      m_array = newvector;
    }

    bool operator[](int p_index)
    {
      int cell = p_index / 32;
      int bit = p_index % 32;
      return (m_array[cell] & (1 << bit)) >> bit;
    }

    void Set(int p_index, bool p_value)
    {
      int cell = p_index / 32;
      int bit = p_index % 32;
      if(p_value == true)
        m_array[cell] = (m_array[cell] | (1 << bit));
      else
        m_array[cell] = (m_array[cell] & (~(1 << bit)));
    }
  protected:
    unsigned long int* m_array;
    int m_size;
};

When I initialize the newvector pointer in the constructor, nothing is initialized so the array is in an undefined state correct? So, I'm using VS2010 and getting the following # when I step-into the code: 3452816845 for newvector. I understand that this is signaling that nothing is defined as of yet but is this value always the case for unsigned long int? Does this range ever vary (could this ever be 0)? I am curious because in the [] override, you bit-and this undefined identifier with the number you shifted into.

Sorry for being pedantic, since you've explicitly stated you're doing this to refresh your memory, as a pure exercise. That's ok. For production, avoid reinventing the wheel by creating your own bitvector, and rather use std::bitset<> for the purpose. — FrankH.
– FrankH., Commented Dec 7, 2010 at 13:35

David Rodríguez - dribeas · Accepted Answer · 2010-12-07 09:26:20Z

1

You can change the acquisition of the data to:

newvector = new unsigned long int[p_size]();

to get a block of data initialized to 0s. Or you can initialize it manually either iterating over the array or with memset (which is fine for POD types, but not for non-POD types, so be careful where you use it).

On the question of whether the value is guaranteed to be that, or if it is random, the answer is that it is undefined. Some compilers, when compiling with debug options will initialize the data to known values on allocation and will rewrite during deallocation to ease debugging (if you see this value, chances are that you are using uninitialized memory/already released objects), but you cannot depend on that, as different compiler options will change the effect.

In many cases in release mode the memory will not be modified at all. It might even seem that it is 0 initialized as for security reasons some OSs will blank memory pages before giving them to the process, but again don't count on that as that will only hold on the first allocation of the memory, and a later Resize may not acquire a new memory page, but possibly yield a block that was previously allocated and released, with the values that were stored there prior to the previous deallocation.

If you want your memory to be initialized, you need to initialize it yourself.

edited Dec 7, 2010 at 9:26

answered Dec 7, 2010 at 9:20

David Rodríguez - dribeas

209k23 gold badges304 silver badges496 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ilya Over a year ago

Ah alright. So the author is kind of banking on the fact that the compiler wouldn't have messed up his point. Would I get, overall with the intention of his bitvector class, the same result if I just initialized all the values to the max value of an unsigned long int?

David Rodríguez - dribeas Over a year ago

I don't quite understand the comment. The code in question, as you have presented it, is undefined behavior. Will you get the same result if you properly initialized? Surely not, since that would be defined, and consistent across executions, while the current code need not be. Note that the value, in hex is 0xcdcdcdcd, with is a bitpattern injected by the compiler/libraries in debug mode. If code depends on that pattern and you change the compiler flags, the results will differ. Again, this is if the memory is not initialized somewhere else.

Loki Astari · Accepted Answer · 2010-12-07 09:36:25Z

0

A couple of comments:

  // No point in checking
  // Delete on a NULL pointer works fine.
  if(m_array !=0)
    delete[] m_array;

Calling new will never return NULL

  newvector = new unsigned long int[p_size];

  if(newvector == 0)
    return;  // This condition will NEVER happen
             // So don't even bother testing for it.

Rather than this:

  int min;
  if(p_size < m_size)
    min = p_size;
  else
    min = m_size;

I prefer the more succinct (though it is a personal preference)

  int min = (p_size < m_size) ? p_size : m_size;

You can delcare the index variable inside the loop.
It stops names leaking into the extended scope.
Also prefer to use the pre-fix increment. OK it does not matter for integers but it does matter for some iterators and sombody may change the type in a latter version and they should not have to scan the whole code base to make sure you are using the correct version of increment for the new type.

  for(int index = 0;index < min; ++index)
    newvector[index] = m_array[index];

Of course you can always replace this loop entirely with a copy()

std::copy(m_array, m_array+ min, newvector);

The most important bit. I left to last.
You class contains a RAW pointer. Thus you really need to define the copy constructor and assignment operator (loop up the rule of 3).

Think of this situation:

BitVector    x(5);
BitVector    y(x);  // What happens here?
                    // It calls the compiler created copy constructor.
                    // In itself this is not bad. But afterwords both
                    // x.m_array and y.m_array point at the same block of memory
                    // Thus when they go out of scope the destructor for
                    // each will try and delete the memory.

answered Dec 7, 2010 at 9:36

Loki Astari

267k87 gold badges344 silver badges575 bronze badges

2 Comments

Ilya Over a year ago

Heh thanks, looking to avoid bad practice. In terms of "Calling new will never return NULL", the book I'm using came out in 2003 and author explicitly stated the opposite. Is he wrong or was there a change somewhere after that point in time?

Loki Astari Over a year ago

@Ilya: The author is either wrong or he is talking about the no-throw versoin of new. But your code above does not use the no-throw version of new it explicitly uses the throwing version (this is most often used version (the other two version of new need to be explicitly used and should only be used if you understand you need something different to normal)). Thus allocation will either work or std::bad_alloc will be thrown as an exception.

Cheers and hth. - Alf · Accepted Answer · 2010-12-07 09:43:17Z

0

Re your question about particular values: an unitialized value can be anything. Including, for most types, that it can be trap value that will cause a crash or whatever if or when it's used. As a practical matter, I don't know of any 32-bit system that has trap representations (i.e. all bits are value representation bits), and so on a 32-bit system an uninitialized long int has the long int value represented by the bitpattern in memory.

Re your code, it violates the rule of three that if you need a destructor, a copy constructor or a copy assignment operator, then you most likely need all three.

Your code needs all three. Copying a BitVector will get you 2 BitVector instances that both think they're responsible for deallocating the array. Resulting in double deallocation. Which is Undefined Behavior.

A simple solution is to use a std::vector instead of a raw array.

Haven't you asked about that earlier? I seem to remember almost the exact same code.

Cheers & hth.,

answered Dec 7, 2010 at 9:43

Cheers and hth. - Alf

146k15 gold badges218 silver badges342 bronze badges

1 Comment

Ilya Over a year ago

Nope, first time I've asked about this. I'm using Data Structures for Game Programmers so that's possibly why. Remember heh, this is the author's code so I think he was going for brevity to show how bitvectors are implemented. Thanks though, will keep practice in mind.

Sylvain Defresne · Accepted Answer · 2010-12-07 11:00:59Z

When compiling your code with the memory heap debug (I think it is always enabled in Debug build), Visual Studio initialize memory to some magic numbers to detect some common usage of uninitialized memory.

The values are :

0xCDCDCDCD : Allocated in heap, but not initialized
0xDDDDDDDD : Released heap memory.
0xCCCCCCCC : Allocated on stack, but not initialized
0xFDFDFDFD : "NoMansLand" fences automatically placed at boundary of heap memory. Should never be overwritten. If you do overwrite one, you're probably walking off the end of an array.

As the memory for newvector is coming from the heap, it is initialized to 0xCDCDCDCD by Visual Studio, in debug build. You should not depend on thoses values, but when debugging it can be valuable, as it can help you spot some common error (pointer to released memory, ...).

In Release build, the memory will not be initialized to such a debugging value, and you'll get whatever was at the memory you've been allocated, so you must not depend on the value.

Collectives™ on Stack Overflow

Undefined values in dynamic arrays

4 Answers 4

2 Comments

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related