maths and c++ 101 » programming

std::vector use_it; //NOW!

Filed under: programming — luan @ 10:20 pm

Traditional arrays have several limitations. Who would’ve thought that you can’t change the size of the array once it’s created?? Who would’ve thought

int size;
std::cout<<”Enter size of array: “;
std::cin>>size;
int my_array[size];

doesn’t work!

Well worry no more! Let’s embrace the cutting edge technology of c++ vectors! (Well it is really not new anymore, but if you’re reading this maybe it’s new to you.) This article should get you the very basic ideas of vectors and help you to start using it immediately.

1. Initializing

Vector is in C++ standard library. So to use it, just like string you have to include it:

#include <vector>

Now that you have included it you can start making vectors. From now on you should do this every time you are in need of an array. Vectors are stored in memory exactly how arrays are (- Zach). So you’re not losing anything but a lot to gain.

std::vector<T> my_vector;
//T is a pre-defined (or user defined) type, like int, long or My_big_int

This make my_vector an array of size 0 (zero). You can anternately declare your vector like this if you know how many elements you need before hand:

std::vector<T> my_vector(10);

2. Inserting and Accessing Elements

After you declare your array you can start putting elements into it. If you declared your array without a size it will start out empty.

my_vector.push_back(my_value);

This will put my_value object at the end of the array. Say your vector already has 3 elements, a push_back will put the new item at the 4th position (index = 3) in your vector.

Now you can access your vector just like you would normally an array.

std::vector<int> my_ints;

my_ints.push_back(2);
// putting integer 2 into first position or index 0 (zero) of empty array

my_ints.push_back(0);
my_ints.push_back(0);
my_ints.push_back(8);

for (int i = 0; i < my_ints.size(); i++)
std::cout<<my_ints[i];
//you access vector elements how you would arrays

As you could imagine the above will prints out 2008 on the screen.

Notice if you declare the previous array:

std::vector<int> my_ints(2); // added (2)

and do the 4 push_backs as before, your array will look like t his:

[ 0 ] [ 0 ] [ 2 ] [ 0 ] [ 0 ] [ 8 ]

This is because when you declare your array you set the size at 2 it is created with the first 2 positions initialized to 0 (zero).

From the above snippet you see that to access vector elementls you do my_vector[index] just like you wuold do accessing an array.

3. Removing an element

To remove an element you call vector erase function. To remove 2 (index = 3 or 2nd after the first) from the array above you would do:

my_ints.erase(my_ints.begin()+2,my_ints.begin()+3);

2 is the index of the element you want erased. 3 is there because you want to erase from index 2 and stop at index 3 (1 element). my_ints.begin() points to the first element of your array (zero) (it is NOT an index).

As you would imagine:

my_ints.erase(my_ints.begin(), my_ints.end());

will erase everything from your array (size of array becomes 0 after). Even though if you want to do this you can simply call

my_ints.clear(); // remove everything from the array.

similarly

my_ints.erase(my_ints.begin(), my_ints.end()-1);

would delete everything and leave the last element (size of array = 1) and so on..

4. .size()

Another convenient member of the vector class is size() function. It returns the size of your vectors. As in how many elements are there in your vector and not how much memory your array is taking up (which is not exactly helpful in most cases, or is it?)

5. Warning… what?

When you compile the code above you will probably get a Warning about signed/unsigned mismatch. In your for loop you declared i as an integer (signed value). Then you compare i with vector.size() an unsigned value. That is why you’re getting the Warning. To solve this problem (and be very picky about not wasting a whole integer to store values of more limited size or not having enough room to adress the whole vector…) you can declare the vector size type:

typedef std::vector<int>::size_type v_sz;

This defines v_sz as a new type that is the size of vectors of integers. It will guarantee v_sz will be large enough to represent the size of the largest vector of integer you (or your compiler/computer rather) can generate. Of course you don’t have to limit yourself to just vectors of integers.

So when you write a loop to manipulate your vector you can do:

for (v_sz i; i< my_vector.size(); i++)
{
…
}

without getting the warning.

6. Iterating with the iterator

Another way to iterate through vector is by using its built-in iterator. But first let’s define the iterator type first…

typedef std::vector<int>::iterator v_it;
//again don’t have to be just <int>, try <double> or <std::string> sometimes

Of course you can type std::vector<T>::iterator everytime but it gets old. And then

for (std::vector<std::vector<std::string>>::iterator my_iterator; my_iterator !=….
// iterator for vector of vector of type string (a 2-d matrix of strings)

would get old the very second time..

Now we got that out of the way, we can now do this:

for(v_it i = my_vector.begin(); i != my_vector.end(); i++)
{
std::cout<< *i; //notice the asterisk
}

Now i, an iterator object, it is NOT an index. It is (pointing to) one of the element in your array itself. Similarly my_vector.end() and my_vector.begin() are not indexes, they are objects!. You may wonder why my_vector.begin() + 2 still work (good question!). This is because the addition and subtration operations are overloaded for this type of operation.

GOOD LUCK!

Comments (0)

reinventing the wheel

Filed under: programming — luan @ 8:57 pm

As of now I’d like my project for comp 5983 is to demonstrate and contrast the power of RSA and DES encryption method. In theory RSA is about 1500 times slower than DES. Part of this is due to the large arithmetic operations that is involved with RSA and the low-level and speed of of bit-wise operations of DES. With a plaintext of a few hundred characters we won’t notice the difference. But my goal is to implement both of these algorithm to its full scale (1024-bit and beyond RSA to start with) and start encrypts decent sized chunks of data at once.

This means I will need a number class that is large enough for RSA operation.

RSA basics:

You are given a public key (e,n) with this you can encrypt plaintext. Plaintext is simply raised to the power of e then reduce modulo n.

To decrypt you need the private key (d, n). The ciphertext is raised to the power d and then reduce modulo n.

Of course if there is a simple relation between e and d then RSA would not be secure at all. Since anybody could find the private key. The security of RSA algorithm is based on the fact that n is very hard to factor as it is a product of two very large primes. These two primes are essentially the only way to find d given e.

How large you ask? currently RSA is implemented at than 1024 bit or more(this modulus has around 308 digits since 2^1024 ~= 10^308 or log_base 10_of 2^2048)

There are quite a few library under GNU that allows operations with very large numbers (to the millions of digits). You can search for these library by googling “arbiraty precision.” Rewriting a class for this purpose would be reinventing the wheel but that doesn’t necessarily a bad thing. I’m sure there are lots to learn in the process.

My current idea is to use arrays (vectors) of arbiraty large size with the ith element in the array to represent the coefficient of 10^i in the decimal expansion of the number I want to demonstrate. For example 392 will be stored in a array like this [2] [9] [3].

This will also involve overloading the common operations for this common class namely addition (and multiplication). If we have addition we can do multiplication with bruteforce but it would be painstakingly slow as I hope to see.

As of now the standard c++ compiler understands 2^64 values (64-bit, compare to the goal of 1024-bit). There is story about this number

In a Kingdom far far away. One of the King’s advisor invented the game of chess. The king was so impress that he declare that the he would grant the advisor one wish.
The advisor wish is as follow: He would like 2 grains of cereal in the first square of his chess board, 4 in the second, 8 in the 3rd and so on until the last square (chessboard has 64 squares where the pieces can go on). The king was enraged thinking how little his advisor is asking. It is in insult to his generosity the way he sees it.

He stripped his advisor of his position and sent him home.

After a month or so when all the king’s mathematician have only gotten through half the board they declared that even if every square inch of the earth is covered with crops they still won’t be able to grow enough to match what was asked of them.

For simplicity the value the advisor asked is:

2^64 = 18446744073709551615
(it’s just about 18 billion billion).

In C++ you can manipulates values from 0 up to this by declaring

unsigned long long int my_var;

If you just do

long long int my_var

you will only have access to half the size (but same magnitute) from
-9223372036854775807 to 9223372036854775807

Comments (0)

Network Infrastructure for Massively Distributed Games

March 5, 2008

std::vector use_it; //NOW!

March 4, 2008

reinventing the wheel