C/C++ Flashcards
Initialize 2D ‘double’ array.
double A[3][3] = {-1.0, 0.0, 1.0; -2.0, 0.0, 2.0; -1.0, 0.0, 1.0};
How to define a function that receives a 2D array as an argument?
void my_function(double A[][5]) { …}
Basic file I/O in C
FILE *fp; fp=fopen(“test.txt”, “w”); fprintf(fp, “Testing…\n”); fclose(fp);
Explain C++ template
Template allows a function or class to work on many different data types without being rewritten for each one.
- Class templates are commonly used to implement containers.
- A function template represents a family of functions.
C++ iterator concept
In C++, an iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (at least, the increment (++) and dereference (*) operators). The concept of an iterator is fundamental to understanding the C++ Standard Template Library (STL) because iterators provide a means for accessing data stored in container classes such a vector, map, list, etc.
C++ iterator example
using namespace std;
vector myInt;
vector::iterator it; // Add to myInt
myInt.push_back(1);
myInt.push_back(4);
myInt.push_back(8);
for(it = myInt.begin(); it!= myInt.end(); it++) {
cout << “ “ << *it; //Should output 1 4 8
}
C++ reference (vs pointer)
void swap(int &v1, int &v2) { int temp = v1; v1 = v2; v2 = temp; } \* **Once reference to an object is created, then it cannot be reseated to refer a different object.** This is often done with pointers. Thus, pointer arithmetic is not possible with references. \* **Reference cannot be null.** Therefore, containers of references are NOT allowed. \* **Reference cannot be uninitialized.** int & k; // compile error!
Abstraction and Encapsulation
- Abstraction is the creation of a well-defined interface. This separates the implementation of an object from its interface.
- Encapsulation means keeps the implementation details of your abstractions PRIVATE.
C++ class definition
class Stack{ public: int pop(); void push(int i); Stack(); // constructor ~Stack(); // destructor private: int items[STACKSIZE]; int top; };
C++ Polymorphism
Dynamic typing Virtual function
C++ ‘function template’ example
// function template #include \<iostream\> using namespace std;
template <class Type>
Type GetMax (Type a, Type b) {
Type result;
result = (a>b)? a : b;
return (result);
}
int main () { int i=5, j=6, k; long l=10, m=5, n; k=GetMax\<int\>(i,j); n=GetMax\<long\>(l,m); cout \<\< k \<\< endl; cout \<\< n \<\< endl; return 0; }
C++ ‘Class template’ example
// class templates #include \<iostream\> using namespace std;
template <class Type>
class mypair {
Type a, b;
public:
mypair (Type first, Type second) {a=first; b=second;}
Type getmax ();
};
template <class Type>
Type mypair<Type>::getmax ()
{
Type retval;
retval = a>b? a : b;
return retval;
}
int main () { ** *mypair* \<int\> myobject (100, 75);** cout \<\< myobject.getmax(); return 0; }
C++ function template declaration: Two identical ways!
include <iostream>
- *template** <class identifier> function_declaration;
- *template** <typename identifier> function_declaration;
Example)
template <typename Type>
Type max(Type a, Type b) {
return a > b ? a : b;
}
int main() { // This will call max \<int\> (by argument deduction) std::cout \<\< max(3, 7) \<\< std::endl; // This will call max\<double\> (by argument deduction) std::cout \<\< max(3.0, 7.0) \<\< std::endl; // This type is ambiguous, so explicitly instantiate max\<double\> std::cout \<\< max\<double\>(3, 7.0) \<\< std::endl; return 0; }
C++ STL Vector Class
A vector is, essentially, a resizable array; the vector class allows random access via the [] operator, but adding an element anywhere but to the end of a vector causes some overhead as all of the elements are shuffled around to fit them correctly into memory.
#include \<iostream\> #include \<vector\>
using namespace std;
int main()
{
vector <int> example; //Vector to store integers
example.push_back(3); //Add 3 onto the vector
example.push_back(10); //Add 10 to the end
example.push_back(33); //Add 33 to the end
for(int x=0; x<example.size(); x++)
{
cout<<example[x]<<” “; //Should output: 3 10 33
}
if(!example.empty()) //Checks if empty
example.clear(); //Clears vector
vector <int> another_vector; //Creates another vector to store integers
another_vector.push_back(10); //Adds to end of vector
example.push_back(10); //Same
if(example==another_vector) //To show testing equality
{
example.push_back(20);
}
for(int y=0; y<example.size(); y++)
{
cout<<example[y]<<” “; //Should output 10 20
}
return 0;
}
What are the differences between Struct and Class in C++?
In C++, classes and struct are the same except for their default behaviour with regards to inheritance and access levels of members.
C++ class
Default Inheritance = private
Default Access Level for Member Variables and Functions = private
C++ struct
Default Inheritance = public
Default Access Level for Member Variables and Functions = public
In C++, why is the dynamic allocation using nested ‘new’ bad? (2D allocation)
Nested New MD arrays are inefficient. In addition to allocating all the space for the normal 2D array, you’re also allocating space for POINTERS. Not only that, but in order to access any element in the array, you have to dereference two pointers!
The one saving grace to the nested new approach is that it doesn’t require the entire MD array to be contiguous, which means you have a better chance of getting the memory you need if memory is badly fragmented.
Motivating example of C++ Template: Why do we need it?
// void qsort ( void \* base, size\_t num, size\_t size, int ( \* comparator ) ( **const void \***, **const void \*** ) ); inline int cmp (const **void \***a, const **void \***b) { int aa = \***(int \*)**a; // Pointer casting int bb = \***(int \*)**b; return (aa \< bb) ? -1 : (aa \> bb) ? 1 : 0; }
main (int argc, char \*argv[]) { const int size = 1000; // array of 1000 integers int array [size]; int n = 0; // read an integer into the n+1 th element of array while (cin \>\> array[n++]); n--; // it got incremented once too many times
qsort (array, n, sizeof(int), cmp);
for (int i = 0; i < n; i++)
cout << array[i] << “\n”;
}
C++ Iterator Example2
include <string.h><br></br> #include <algo.h><br></br> #include <vector.h><br></br> #include <stdlib.h><br></br> #include <iostream.h><br></br> <br></br> main ()<br></br> {<br></br> <strong>vector<int> v</int></strong>; // create an empty vector of integers<br></br> int input;<br></br> while (cin >> input) // while not end of file<br></br> <strong>v.push_back (input)</strong>; // append to vector<br></br> <br></br> // sort takes two random iterators, and sorts the elements between<br></br> // them. As is always the case in STL, this includes the value<br></br> // referred to by first but not the one referred to by last; indeed,<br></br> // this is often the past-the-end value, and is therefore not<br></br> // dereferenceable.<br></br> <strong>sort(v.begin(), v.end());</strong><br></br> <br></br> int n = v.size();<br></br> for (int i = 0; i < n; i++)<br></br> cout << v[i] << "\n";<br></br> }</iostream.h></stdlib.h></vector.h></algo.h></string.h>
* Iterators provide a way of specifying a position in a container. An iterator can be incremented or dereferenced, and two iterators can be compared. There is a special iterator value called “past-the-end”. Operations like sort take two iterators to specify the source range. To get the source elements, they increment and dereference the first iterator until it is equal to the second iterator. Note that this is a semi-open range: it includes the start but not the end.
Binary tree and its traversal algorithms: Inorder, Pre-order and Post-order
Recursive algorithms can be written for tree traversals. The data structure of the tree can be written as:[1]
typedef struct node
{
int val;
struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.
void inorder(tree t)
{
if(t == NULL)
return;
inorder(t->left);
printf(“%d “, t->val);
inorder(t->right);
}
void preorder(tree t)
{
if(t == NULL)
return;
printf(“%d “, t->val);
preorder(t->left);
preorder(t->right);
}
void postorder(tree t)
{
if(t == NULL)
return;
postorder(t->left);
postorder(t->right);
printf(“%d “, t->val);
}
C Doubly-Linked List
typedef struct iDLL_s {
struct iDLL_s * next; // IMPORTANT – recursive definition!!
struct iDLL_s * prev;
int key;
char * record;
} iDLL_t;
int init_DLL(iDLL_t ** DLL, int key, char * record);
int insert_DLL(iDLL_t ** DLL, int key, char * record);
char * search_DLL(iDLL_t * DLL, int key);
int length_DLL(iDLL_t * DLL);
int delete_DLL(iDLL_t ** DLL, int key);
int print_DL(iDLL_t * DLL);
C Singly Linked List
typedef struct iSLL_s {
int key;
struct iSLL_s * next;
} iSLL_t;
int length_SLL(iSLL_t * head);
iSLL_t * buildOneTwoThree_SLL(void);
void push_SLL(iSLL_t ** headRef, int newData);
void print_SLL(iSLL_t * head);
void delete_SLL(iSLL_t ** head);
int pop_SLL(iSLL_t ** head);
Graph data structure
- Adjacency list – Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices.
- Adjacency matrix – A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
Operations on graph data structure
- adjacent(G, x, y): tests whether there is an edge from node x to node y.
- neighbors(G, x): lists all nodes y such that there is an edge from x to y.
- add(G, x, y): adds to G the edge from x to y, if it is not there.
- delete(G, x, y): removes the edge from x to y, if it is there.
- get_node_value(G, x): returns the value associated with the node x.
- set_node_value(G, x, a): sets the value associated with the node x to a.
Structures that associate values to the edges usually also provide:
- get_edge_value(G, x, y): returns the value associated to the edge (x,y).
- set_edge_value(G, x, y, v): sets the value associated to the edge (x,y) to v.
C code for converting small/big endian numbers
// Unsigned 16 bit conversion: **swapped = (num\>\>8) | (num\<\<8)**
// Unsigned 32-bit conversion:
swapped = ((num>>24)& 0xff) |
((num<<8)& 0xff0000) |
((num>>8)& 0xff00) |
((num<<24)& 0xff000000)
Another C code for small/big endian conversion: int/unsigned int
include <stdint.h></stdint.h>
//! Byte swap unsigned short uint16\_t swap\_uint16( uint16\_t val ) { return (val \<\< 8) | (val \>\> 8 ); }
//! Byte swap short int16\_t swap\_int16( int16\_t val ) { return (val \<\< 8) | ((val \>\> 8) & 0xFF); }
//! Byte swap unsigned int uint32\_t swap\_uint32( uint32\_t val ) { val = ((val \<\< 8) & 0xFF00FF00 ) | ((val \>\> 8) & 0xFF00FF ); return (val \<\< 16) | (val \>\> 16); }
//! Byte swap int int32\_t swap\_int32( int32\_t val ) { val = ((val \<\< 8) & 0xFF00FF00) | ((val \>\> 8) & 0xFF00FF ); return (val \<\< 16) | ((val \>\> 16) & 0xFFFF); }
Example: Storing 0x90AB12CD in Big Endean machine
Big Endian
In big endian, you store the most significant byte in the smallest address. Here’s how it would look:
Address Value
1000 90
1001 AB
1002 12
1003 CD
int num = 1;
if(*(char *)&num == 1) {
printf(“\nLittle-Endian\n”);
} else {
printf(“Big-Endian\n”);
}
How to copy ‘size’ bytes from where ‘buffer’ points to where ‘app_key’ points?
Use the memcpy function (you need to #include <string.h>).</string.h>
memcpy(app_key, buffer, size);