Why vector.size()-1 gives garbage value?
myints.size() is an unsigned type: formally a std::vector<int>::size_type. Subtracting 1 from an unsigned type with a value of 0 will cause wrap-around effects, in your case, to
std::numeric_limits<std::vector<int>::size_type>::max()
It would not have printed "garbage value": but the number above, which will be one less than a large power of 2.
Weird behavior of vector.size() while printing to std output
The size of standard containers is represented as an unsigned integer (when using the default allocator such as in the example). Unsigned integer can represent only non-negative numbers.
When one operand of binary arithmetic operation (subtraction in this case) is unsigned (and at least as ranked as int) and the other is signed of same or lower rank, then the signed operand will be converted to the unsigned type. The result of the operation is that same type.
So, since the result of the operation is an unsigned integer, it cannot possibly be a negative number because those are not representable by unsigned integers. What happened is that the "correct" result of the operation was outside of representable numbers. This can happen both when the value is below representable range of values as well as above.
When "correct" result of unsigned arithmetic operation is outside representable range, the adjusted result that you get will be a representable value that is congruent with the "correct" result modulo M which is the number of representable values of the type (M == 2number of bits). In this case 18446744073709551614 is congruent with -2 modulo M.
Note that when result of signed arithmetic is outside the range of representable values, then the behaviour of the program is undefined. It is important to avoid that.
Creating array size of passed value gives garbage value
Since you are using C++, I suggest you to use vector.
Here's the std::vector solution for your problem.
std::vector<int> Hash(higher_element);
Vectors initialize to 0 automatically. But for your clarification,
std::vector<int> Hash(higher_element,0);
Vector.size() producing an unexpectedly large number
bins[currentbin] in the for loop access invalid bin as currentbin variable is already incremented. You need to currentbin++ after the for loop.
C++ array of fixed size getting garbage values
Variable Length Arrays (VLA) are not part of Standard C++. Read more in Why aren't variable-length arrays part of the C++ standard?
But let's say, that you use a compiler extension that allows them, then the problem is that you use a C function here:
std::cout << strlen(a) << '\n';
which expects a C string, which means a NULL-terminated string.
That means that you should make your array big enough to hold the NULL termination character, like this:
char a[s.length() + 1];
since string::length() will return 4 for the string "1010". That means that the C string should be this: "1010\0", i.e. the actual string, appended with the NULL terminating character. As a result, you would need an array of size 5 to store that string.
An easy fix would be:
char a[s.length() + 1] = {0};
which will NULL initialize every cell of the array. Then you will overwrite every cell of it with characters, except from the last cell, specially reserved for the NULL terminator.
Another approach would be to only assign the NULL terminator to the last cell of your string, like a[s.length()] = '\0';. Notice how s.length() now is the index to the last element of your array.
Standard C string functions (like strlen()) depend on the NULL termination character to mark the end of the string. In the absence of that important character, they do not know when to stop, thus accessing memory beyond from the point they are meant to visit.
That invokes Undefined Behavior (UB), which, in your computer, is accessing memory with garbage values.
c++ garbage values in vector of pointer
Read the documentation of std::vector::push_back
First the description:
Adds a new element at the end of the vector, after its current last element. The content of val is copied (or moved) to the new element.
This effectively increases the container size by one, which causes an automatic reallocation of the allocated storage space if -and only if- the new vector size surpasses the current vector capacity.
Then about validity of iterators:
If a reallocation happens, all iterators, pointers and references related to the container are invalidated.
So, when you add an object to the vector, all the pointers pointing to objects in that vector may become invalid - unless you've guaranteed that the vector has enough capacity with std::vector::reserve.
Invalid means that the pointer no longer points to a valid object and dereferencing it will have undefined behaviour.
In the latter code, you never add objects to the pointed-to vector after you've stored the pointers, so the pointers are valid.
how to handle garbage value while making my own vector in c++?
Many many misunderstanding.
Your range insert and erase is more than strange. There are some other bugs.
Please not, if you work with ranges in C++, then the end() of the range always has to point to one past the last element in the range.
Please the the comments that I put in your code.
I also replace all exceptions with std::exceptions so that I can compile.
Regarding the indeterminate values that you see.
If you create an Vector having the size 5, then these 5 values are initially indeterminate. Maybe you want to "reserve" 5 bytes?
But now you have the 5 bytes. And if you use push_back then the new values will be added after the 5 initial elements. As element index 5,6,7,8 and so on.
Please read about the API from std::vector in CPP Reference.
Please see your annotated code:
#include <iostream>
#include <algorithm>
#include <stdexcept>
template <typename Object>
class Vector
{
public:
explicit Vector(int initSize = 0)
: theSize(initSize), theCapacity(initSize + SPARE_CAPACITY)
{
objects = new Object[theCapacity];
}
Vector(const Vector& rhs)
: theSize(rhs.theSize), theCapacity(rhs.theCapacity), objects(nullptr)
{
objects = new Object[theCapacity];
for (int k = 0; k < theSize; ++k)
objects[k] = rhs.objects[k];
}
Vector& operator= (const Vector& rhs)
{
Vector copy = rhs; // Bug! Self Calling
std::swap(*this, copy); // Bug: Do not swap, you want to assign and both sould contain the same values
return *this;
}
~Vector()
{
delete[] objects;
}
Vector(Vector&& rhs)
: theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ rhs.objects }
{
rhs.objects = nullptr; // If this contains elements, then delete them
rhs.theSize = 0;
rhs.theCapacity = 0;
}
Vector& operator= (Vector&& rhs)
{
// Delete old contents of this
std::swap(theSize, rhs.theSize); // Do not swap!!! Move, like in the move assignment operator
std::swap(theCapacity, rhs.theCapacity);
std::swap(objects, rhs.objects);
return *this;
}
bool empty() const
{
return size() == 0;
}
int size() const
{
return theSize;
}
int capacity() const
{
return theCapacity;
}
Object& operator[](int index)
{
#ifndef NO_CHECK
if (index < 0 || index >= size())
throw std::out_of_range;
#endif
return objects[index];
}
const Object& operator[](int index) const
{
#ifndef NO_CHECK
if (index < 0 || index >= size())
throw std::out_of_range;
#endif
return objects[index];
}
void resize(int newSize)
{
if (newSize > theCapacity) // Bug: Should be >=
reserve(newSize * 2);
theSize = newSize;
}
void reserve(int newCapacity)
{
if (newCapacity < theSize)
return;
Object* newArray = new Object[newCapacity];
for (int k = 0; k < theSize; ++k)
newArray[k] = std::move(objects[k]);
theCapacity = newCapacity;
std::swap(objects, newArray); // Will work, but why always swapping? Assignment is sufficient
delete[] newArray;
}
// Stacky stuff
void push_back(const Object& x)
{
if (theSize == theCapacity) // Just for safety: Should be >=
reserve(2 * theCapacity + 1); // 2* the capacity should always be sufficient
objects[theSize++] = x;
}
// Stacky stuff
void push_back(Object&& x)
{
if (theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[theSize++] = std::move(x);
}
void pop_back()
{
if (empty())
throw std::underflow_error;
--theSize;
}
const Object& back() const
{
if (empty())
throw std::underflow_error;
return objects[theSize - 1];
}
// Iterator stuff: not bounds checked
typedef Object* iterator;
typedef const Object* const_iterator;
iterator begin()
{
return &objects[0];
}
const_iterator begin() const
{
return &objects[0];
}
iterator end()
{
return &objects[size()];
}
const_iterator end() const
{
return &objects[size()];
}
static const int SPARE_CAPACITY = 2;
/*************************************************************************/
/*************************************************************************/
iterator insert(const_iterator position, const Object& val)
{
if (theSize == theCapacity)
{
reserve(2 * theCapacity + 1);
}
int index = position - objects;
for (int i = theSize - 1; i >= index; --i)
objects[i + 1] = objects[i];
objects[index] = val;
theSize++;
return &objects;
}
iterator insert(const_iterator position, Object&& val)
{
if (theSize == theCapacity)
{
reserve(2 * theCapacity + 1);
}
int index = position - objects;
for (int i = theSize - 1; i >= index; --i)
objects[i + 1] = objects[i];
objects[index] = std::move(val);
theSize++;
return objects;
}
template <class InputIterator>
iterator insert(const_iterator position, InputIterator first, InputIterator last)
{
if (theSize == theCapacity) // Bug, completely wrong. Now insertion
{
reserve(2 * theCapacity + 1);
}
Object* newObjects = last - first;
return &objects;
}
iterator erase(const_iterator position)
{
theSize--;
int index = position - begin();
Object* newObj = new Object[theCapacity]; // Strange algorithm. Why copy all data instead of shifting
for (int i = 0, j = 0; j <= theSize; ++j)
{
if (j != index)
newObj[i++] = objects[j];
}
delete[] objects;
objects = newObj;
return &objects[index];
}
iterator erase(const_iterator first, const_iterator last)
{
int index = last - first;
theSize = index; // Wrong and too comlicated
Object* Array = new Object[theCapacity];
for (int i = 0; i <= index; i++) // Wrong
Array[i] = objects[i + index]; //
return Array;
}
void push_front(const Object& val)
{
if (theSize == theCapacity)
reserve(2 * theCapacity + 1);
objects[0] = val; // Bug. Just overwriting. No push front
theSize++; // No last value will be indeterminate
}
void push_front(Object&& val)
{
if (theSize == theCapacity) // Bug. See above
reserve(2 * theCapacity + 1);
objects[0] = std::move(val);
theSize++;
}
Object& front()
{
if (empty())
throw std::underflow_error;
return objects[0];
}
const Object& front() const
{
if (empty())
throw std::underflow_error;
return objects[0];
}
/*************************************************************************/
/*************************************************************************/
private:
int theSize;
int theCapacity;
Object* objects;
};
int main()
{
Vector<int> arr1(5); // Creating a vector arr1 with 5 indeterminate elements
Vector<int> arr2(5); // Creating a vector arr1 with 5 indeterminate elements
Vector<int> ::iterator it;
arr1.push_front(1); // Will set aissign one to the first element
arr1.push_back(2); // Will add a new element at the end. So, now first element has value, 2nd,3rd, 4th and 5th are indeterminate. Last will be 2
arr1.push_back(3); // See above
arr1.push_back(4); // See above
arr1.push_back(5); // See above
arr1.erase(arr1.begin(), arr1.begin() + 2); // Does not work correctly
for (it = arr1.begin(); it != arr1.end(); it++) // Will just show 2 values
std::cout << *it;
std::cout << '\n';
std::cout << arr1.size();
return 0;
}
Best way to extract a subvector from a vector?
vector<T>::const_iterator first = myVec.begin() + 100000;
vector<T>::const_iterator last = myVec.begin() + 101000;
vector<T> newVec(first, last);
It's an O(N) operation to construct the new vector, but there isn't really a better way.
Related Topics
How to Swap Array-Elements to Transfer the Array from a Column-Like into a Row-Like Representation
Using an Union (Encapsulated in a Struct) to Bypass Conversions for Neon Data Types
What Is the Status on Dynarrays
C++11 Std::Async Doesn't Work in Mingw
Outputting More Things Than a Polymorphic Text Archive
Is There a Safe Navigation Operator for C++
Trying to Use a While Statement to Validate User Input C++
How Is This a Most Vexing Parse
How to Check If Std::Map Contains a Key Without Doing Insert
Protected Data in Parent Class Not Available in Child Class
How to Read/Write Std::String Values From/To Binary Files
Com(C++) Programming Tutorials
How to Resume Input Stream After Stopped by Eof in C++