#include<iostream>
#include<cstdlib>
#include<cassert>
#include <algorithm>
#include <iterator>
#include <memory>
#define INT_MAX 5555
using namespace std;
template<class T> class SA {
private:
int low, high;
shared_ptr<T[]> p;
public:
// default constructor
SA()
{
low = 0;
high = -1;
p = NULL;
}
// 2 parameter constructor lets us write
SA(int l, int h)
{
if ((h - l + 1) <= 0)
{
cout << "constructor error in bounds definition" << endl;
exit(1);
}
low = l;
high = h;
p = shared_ptr<T[]>(new T[h - l + 1]);
}
// single parameter constructor lets us
// SA x(10); and getting an array x indexed from 0 to 9
SA(int i)
{
low = 0;
high = i - 1;
p = shared_ptr<T[]>(new T[i]);
}
// copy constructor for pass by value and
// initialization
SA(const SA& s)
{
int size = s.high - s.low + 1;
p = new T[size];
for (int i = 0; i < size; i++)
p[i] = s.p[i];
low = s.low;
high = s.high;
}
// destructor
~SA()
{
}
//overloaded [] lets us write
//SA x(10,20); x[15]= 100;
T& operator[](int i)
{
if (i < low || i > high)
{
cout << "index " << i << " out of range" << endl;
exit(1);
}
return p[i - low];
}
// overloaded assignment lets us assign one SA to another
SA& operator=(const SA& s)
{
if (this == &s)
return *this;
int size = s.high - s.low + 1;
p = shared_ptr<T[]>(new T[size]);
for (int i = 0; i < size; i++)
p[i] = s.p[i];
low = s.low;
high = s.high;
return *this;
}
// overloads << so we can directly print SAs
friend ostream& operator<<(ostream& os, SA s)
{
int size = s.high - s.low + 1;
for (int i = 0; i < size; i++)
cout << s.p[i] << endl;
return os;
};
//end of ostream
class iterator {
private:
shared_ptr<T[]> arr;
int in;
friend class SA;
public:
typedef T value_type;
typedef random_access_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
iterator(shared_ptr<T[]> p, int in = 0) : in(in), arr(p) {}
T& operator*() {
return arr[in];
}
iterator& operator++() {
in++;
return *this;
}
iterator operator++(int) {
iterator temp = *this;
++*this;
return temp;
}
iterator& operator--() {
in--;
return *this;
}
iterator operator--(int) {
iterator temp = *this;
--* this;
return temp;
}
bool operator==(const iterator& x)const {
return (arr == x.arr && in == x.in);
}
bool operator!=(const iterator& x)const {
return !(arr == x.arr && in == x.in);
}
bool operator<(const iterator& x)const {
return (arr == x.arr && in < x.in);
}
int operator-(const iterator& x)const {
return in - x.in;
}
iterator operator-(int x)const {
return iterator(arr, in - x);
}
iterator operator+(int x)const {
return iterator(arr, in + x);
}
};
iterator begin() const {
return iterator(p, 0);
}
iterator end() const {
return iterator(p, high - low + 1);
}
};
//end class of safeArray
template<class T> class SM {
private:
SA<SA<T> > mat;
int rlow, rhigh, clow, chigh;
public:
SM() {
rlow = clow = 0;
rhigh = chigh = -1;
mat = NULL;
}
SM(int r, int c)
{
if (r < 1 || c < 1)
{
cout << "constructor error in SM column bounds definition!" << endl;
exit(1);
}
rlow = clow = 0;
rhigh = r - 1;
chigh = c - 1;
mat = SA<SA<T>>(r);
for (int i = 0; i < r; i++)
mat[i] = SA<T>(c);
}
SM(int arlow, int arhigh, int aclow, int achigh)
{
rlow = arlow;
rhigh = arhigh;
clow = aclow;
chigh = achigh;
if ((rhigh < rlow) || (chigh < clow)) {
cout << "constructor error in SM column bounds definition!" << endl;
exit(1);
}
mat = SA<SA<T> >(rlow, rhigh);
for (int i = rlow; i <= rhigh; i++)
mat[i] = SA<T>(clow, chigh);
}
SA<T>& operator [](int i)
{
if (i < rlow || i > rhigh) {
cout << "Error: Index " << i << " is out of range" << endl;
exit(1);
}
return mat[i];
}
friend ostream& operator<<(ostream& out, SM arr) {
for (int i = arr.rlow; i <= arr.rhigh; i++)
{
for (int j = arr.clow; j <= arr.chigh; j++)
{
out << arr.mat[i][j] << " ";
}
out << endl;
}
return out;
}
};
template <typename T>
class VNT : public SM<T> {
private:
SM<T> table;
int r, c, min;
public:
VNT(int r, int c) : SM<T>(r, c) {
table = SM<T>(r, c);
this->r = r;
this->c = c;
initialize();
}
void initialize()
{
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
table[i][j] = INT_MAX;
}
}
}
void add(T x) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (table[i][j] == INT_MAX)
{
table[i][j] = x;
sort();
return;
}
}
}
}
string find(T x) {
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (table[i][j] == x)
return "true";
return "false";
}
T getMin() {
min = table[0][0];
table[0][0] = INT_MAX;
sort();
return min;
}
void sort() {
T* arr = new T[r * c];
int temp, index = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
arr[index++] = table[i][j];
for (int i = 0; i < (r * c) - 1; i++) {
for (int j = i + 1; j < (r * c); j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
index = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
table[i][j] = arr[index++];
delete[] arr;
}
void sort(T arr[], int size)
{
int x = 0;
while (x < size)
add(arr[x++]);
for (int i = 0; i < size; i++)
arr[i] = getMin();
}
void printOutVNT()
{
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (table[i][j] != INT_MAX)
cout << table[i][j] << "\t";
}
if(table[i][0]!=INT_MAX)
cout << endl;
}
cout << endl;
}
SA<T>& operator[](int i)
{
return table[i];
}
};
int main() {
/*
First Fill a VNT a approximately halfway
using the a.add() function and using a sequence
of neither ascending or descending numbers
(i.e. some numbers should be greater than the number added
to the VNT before them and some should be less than the number
added to the VNT before them)
Then print the VNT a
then remove a number using a.getmin();
then remove another number using a.getmin();
then print out the VNT a again
*/
VNT<int> a(5, 6);
int addedNumber = 0;
for (int i = 0; i <= 15; i++) {
addedNumber = (i * 31) % 50;
a.add(addedNumber);
cout << addedNumber << endl;
}
//use whatever method you want to print the VNT
//it can be a member function or you can just loop
//through or however else you want to print it
//this is just an example of what it could look like
//it doesn't have to look like this
a.printOutVNT();
//remove 2 numbers (if you removed a different number that's also okay)
a.getMin();
a.getMin();
//now print it again
a.printOutVNT();
/*
now use find on some numbers that are and are not in the VNT
print out which one's you're using find on and whether find returns
true or false
*/
int firstSearched = 100;
int secondSearched = 0;
int thirdSearched = 31;
//the following statements will print something like:
//"100 is in VNT is: false"
cout << firstSearched << " is in VNT is: " << a.find(firstSearched) << endl;
cout << secondSearched << " is in VNT is: " << a.find(secondSearched) << endl;
cout << thirdSearched << " is in VNT is: " << a.find(thirdSearched) << endl;
/*
Now create a 1d int array with 50 integers in neither ascending or
descending order as explained earlier and print out the unsorted version
*/
int arraySize = 50;
int* k = new int[arraySize];
cout << "The array initially is:" << endl;
for (int i = 0; i < arraySize; i++) {
addedNumber = (i * 31) % 50;
k[i] = addedNumber;
cout << addedNumber << " ";
}
cout << endl << endl;
/*
Now use the sort method from the VNT class to
sort the array k. It doesn't have to look like how I wrote it
you can create a VNT instance and use that or you can call the function
statically from the VNT class
*/
VNT<int> arr(1,arraySize);
arr.sort(k, arraySize);
//now reprint the now sorted array k
cout << "The array, now sorted by VNT, is:" << endl;
for (int i = 0; i < arraySize; i++) {
cout << k[i] << " ";
}
cout << endl;
//You're done
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}