Integer Vectors in C++ (Data structure)

The below post is still not complete. So, don't freak out.

Header file 

#include <vector>




Vector Declaration/Creation

vector<int> arr;                                                                       

This creates an empty vector of integers with size 0.

vector<int> arr(5);                                                                       

This creates an empty vector of integers with size 5, and by default the vector elements will be initialised to 0.

#include <iostream>        

using namespace std;

int main() 
{
        vector<int> output(5);
        
        cout << "[ ";
        for (int i = 0; i < 5; i++) {
            cout << output[i] << " ";
        }
        cout << "]" << endl;
        return 0;
}

Output:
1

[ 0 0 0 0 0 ]

Vector Initialisation

vector<int> arr(5, 0);                                                 

Vector of size 5 can be initialised with default value 0 with the following syntax.

vector<int> arr = {1,2,3,4,5};                                                 

Vector elements can be directly initialised with values. 

It is good idea to store the size as an integer variable only if the vector has the values already initialised, otherwise we will get a compatibility issues in the for loop.

int size = v.size();                                                                   

Vector size() & capacity()

If the vector size is specified during declaration, the size and capacity would be the size specified. 

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr(5);
    int num;
    int size = arr.size();
    
    cout << "Size of arr " << arr.size() << " Capacity of arr " 
         << arr.capacity() << endl;

    return 0;
}

Output:

1

Size of arr 5 Capacity of arr 5

If you add elements to the vector at this stage, the size will keep incremented. But, I wanted to insert element from the position 0 of the vector. To insert elements from 0th position, check the arr1. 

Click here to debug.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr(5);
    int num;
    int size = arr.size();
    
    cout << "Size of arr " << arr.size() << 
         " Capacity of arr " << arr.capacity() << endl;
    
    // Vector arr size keeps incrementing.
    for (int i = 0; i < size; i++) {
       cout << " Insert element ";
       cin >> num;
       arr.push_back(num); 
       cout << " i is " << i << " Size " << arr.size() << 
               " Capacity " << arr.capacity() << endl;
    }
    
    cout << "arr's elements" << endl;
    for (int i = 0; i < size; i++) {
       cout << arr[i] << "  " << endl;
    } 
    
    vector<int> arr1;

    cout << "Size of arr1 " << arr1.size() << 
            " Capacity of arr1 " << arr1.capacity() << endl;
            
    // Vector elements inserted from 0th position 
    for (int i = 0; i < 5; i++) {
       cout << " Insert element ";
       cin >> num;
       arr1.push_back(num); 
       cout << " i is " << i << " Size " << arr1.size() << 
               " Capacity " << arr1.capacity() << endl;
    } 
    int size1 = arr1.size();
    cout << "arr1's elements" << endl;
    for (int i = 0; i != arr1.size(); i++) {
       cout << arr1[i] << "  " << endl;
    } 
    
    return 0;
}

Output:

1
2
3
4
5
6

Size of arr 5 Capacity of arr 5
 Insert element 2
 i is 0 Size 6 Capacity 10
 Insert element 6
 i is 1 Size 7 Capacity 10
 Insert element 8
 i is 2 Size 8 Capacity 10
 Insert element 4
 i is 3 Size 9 Capacity 10
 Insert element 3
 i is 4 Size 10 Capacity 10
arr's elements
0  
0  
0  
0  
0  
Size of arr1 0 Capacity of arr1 0
 Insert element 1
 i is 0 Size 1 Capacity 1
 Insert element 9
 i is 1 Size 2 Capacity 2
 Insert element 6
 i is 2 Size 3 Capacity 4
 Insert element 4
 i is 3 Size 4 Capacity 4
 Insert element 5
 i is 4 Size 5 Capacity 8
arr1's elements
1  
9  
6  
4  
5

Insert into a vector

  1. Getting the integers from the user
a) Insert using 'arr.push_back(value)'

Refer size() & capacity() above.

b) Insert using 'arr[index] = value'

If the user doesn't insert using push_back but with array index, then array's size should be set while declaring the array. 

#include <iostream>
#include <vector>

int returnSubArray(std::vector<int> arr)
{
    int subarray = 0;
    int sum = 0;
    int prod = 1;
        
    for (int j = 0; j < arr.size(); j++) {
        sum += arr[j];
        prod *= arr[j];

        if (sum == prod) {
            //std::cout <<" j " << j << " sum " << sum << std::endl;
            subarray++;
        }
    }
    return subarray;
}

int main() 
{
    int N;
    std::cout << "Enter the vector size" << std::endl;
    std::cin >> N;
    
    std::vector <int> arr;
    
    std::cout << "Enter the vector elements" << std::endl;
    for(int j = 0; j < N; j++) {
        std::cin >> arr[j];
    }

    int subArr = returnSubArray(arr);
    std::cout << "Sub Array count is " << subArr << std::endl;
    
    return 0;
}

Output:

1
2
3
4


Enter the vector size
3
Enter the vector elements
2

In the below program, array's size is set.

#include <iostream>
#include <vector>

int returnSubArray(std::vector<int> arr)
{
    int subarray = 0;
    int sum = 0;
    int prod = 1;
        
    for (int j = 0; j < arr.size(); j++) {
        sum += arr[j];
        prod *= arr[j];

        if (sum == prod) {
            //std::cout <<" j " << j << " sum " << sum << std::endl;
            subarray++;
        }
    }
    return subarray;
}

int main() 
{
    int N;
    std::cout << "Enter the vector size" << std::endl;
    std::cin >> N;
    
    std::vector <int> arr(N);
    
    std::cout << "Enter the vector elements" << std::endl;
    for(int j = 0; j < N; j++) {
        std::cin >> arr[j];
    }

    int subArr = returnSubArray(arr);
    std::cout << "Sub Array count is " << subArr << std::endl;
    
    return 0;
}

Output:

1
2
3
4
5
6

Enter the vector size
3
Enter the vector elements
2
2
1
Sub Array count is 2

  1. Inserting Elements at the back of vector (push_back)

int num;

for (int i = 0; i < size; i++) {
    cin >> num;
    arr.push_back(num); 
}

Size will be given by the user because initially vector will hold 0 elements so v.size() = 0. The vector size will be increased by 1 after each iteration. 

If vector elements are not inserted with push_back, but with array initialisation or incrementation, it will not have the vector size, so randomly inserting into any array position will not work. 

#include <iostream>

using namespace std;

#define RANGE_CHAR 26

int isValid(string s) {
    vector<int> count;
    int size = s.size();
    for (int i = 0; i < size; i++) {
        ++count[s[i] - 'a'];
    }
        
    for (int i = 0; i < RANGE_CHAR; i++) {
        cout << " Count of " << s[i] << " is " << count[s[i] - 'a'] << endl;
    }
    return 1;
}

int main() 
{
   isValid("shiirsh");
   return 1;
}

Output:

1
2
3
4
5
6
7
8
9
10

/usr/local/lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/debug/vector:192:
    error: attempt to subscript container with out-of-bounds index 18, but     
    container only holds 0 elements.

Objects involved in the operation:
sequence "this" @ 0x0xffeeef3c {
  type = N15__gnu_debug_def6vectorIiSaIiEEE;
}

Disallowed system call: SYS_kill

With vector size mentioned, it worked fine.

#include <iostream>

using namespace std;

#define RANGE_CHAR 26

int isValid(string s) {
    vector<int> count(RANGE_CHAR);
    int size = s.size();
    for (int i = 0; i < size; i++) {
        ++count[s[i] - 'a'];
    }
        
    for (int i = 0; i < RANGE_CHAR; i++) {
        cout << " Count of " << s[i] << " is " << count[s[i] - 'a'] << endl;
    }
    return 1;
}

int main() 
{
   isValid("shiirsh");
   return 1;
}


If I want to use push_back to insert the elements, then I don't want to specify the size explicitly until I don't use vec.at(i).

#include <iostream>
#include <vector>

using namespace std;

#define RANGE_CHAR 26

int isValid(string s) {
    vector<int> count;
    int size = s.size();
    for (int i = 0; i < size; i++) {
        //count.push_back(count.at(i) +1);
        count.push_back(1);
    }
        
    for (auto it = count.begin(); it != count.end(); ++it) {
         cout << *it;
                     
    }
    return 1;
}

int main() 
{
   isValid("shiirsh");
   return 1;
}

Output 

1111111

Access a vector element

Now, with at(i), it threw an error because it tried to access the element before inserting. 

#include <iostream>
#include <vector>

using namespace std;

#define RANGE_CHAR 26

int isValid(string s) {
    vector<int> count;
    int size = s.size();
    for (int i = 0; i < size; i++) {
        count.push_back(count.at(i) +1);
    }
        
    for (auto it = count.begin(); it != count.end(); ++it) {
         cout << *it;
                     
    }
    return 1;
}

int main() 
{
   isValid("shiirsh");
   return 1;
}

Output 

terminate called after throwing an instance of 'std::out_of_range'

  what():  vector::_M_range_check: __n (which is 0) >= this->size() (which is 0)

After specifying the size, it worked. Because, with size specified, the vector count is initialised to 0 as well.

#include <iostream>
#include <vector>

using namespace std;

#define RANGE_CHAR 26

int isValid(string s) {
    vector<int> count(RANGE_CHAR);
    int size = s.size();
    for (int i = 0; i < size; i++) {
        count.push_back(count.at(i) +1);
    }
        
    for (auto it = count.begin(); it != count.end(); ++it) {
         cout << *it;
                     
    }
    return 1;
}

int main() 
{
   isValid("shiirsh");
   return 1;
}

Output

000000000000000000000000001111111

Delete from a vector 

v.pop_back();

It removes the last element from the vector and effectively reduces the container size by one. 

v.erase(iterator); 

Inside for loop, erase will not work. So, get the iterator number and erase the item outside for loop. The front of the vector has the highest removal cost, because it has to move all elements forward after erasure.

Print the vector

Range based for loop ideas using auto, auto&, iterator are given here.

Range based for loop with 2D array or vector of vectors

vector<vector<int>> intervals;
vector<int> prev = intervals[0];

for (vector<int> i: intervals) {
   if (prev[1] > i[0]) {
       count++;
   }
}


Check if vector is empty or not

    vector<std::shared_ptr<ArmyHospital>> ptr;  // vector change

    if (ptr.empty()) {
        return;
    }

Sort the vector elements

sort(v.begin(),v.end()); 

Convert an array into a vector

    int arr[] = { 12, 6, 23, 7, 6, 90, 5, 6 };
 
    vector<int> v(arr, arr + 8);


Vector iterator initialisation

Method 1:

    vector<int>::iterator it;

    for (int i = 0; i < size; i++) {
        it = find(v.begin(), v.end(), query);
    }


Method 2: 
    for (int i = 0; i < size; i++) {
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), 6);
    }

'*it ' will print the value stored in the vector v. 'it' will print the value of the position. 

Remove duplicates 

Vector to set and Set to Vector 

template <typename T>
std::vector<T> removeDuplicates2(const std::vector<T>& arr)
{
    if(arr.size() == 0) 
    {
        return {};
    }

    // Use a set to remove the duplicates
    std::set<int> set(arr.begin(), arr.end());

    // Copy result back to different container
    std::vector<int> result(set.begin(), set.end());

    return result;
}

clear()

At any point, vector v will have no greater than 1 element because it clears before insertion.

        vector<int> v;
        for (int i = 0; i < heights.size(); i++) {
            for (int j = 0; j < heights[0].size(); j++) {
                if (pacific[i][j] == -1 && 
                    pacific[i][j] == atlantic[i][j]) {
                    v.clear();
                    v.push_back(i);
                    v.push_back(j);
                    ans.push_back(v);
                }
            }
        }

Returning a Vector from Function 

#include <iostream>
#include <vector>
#include <iterator>

using std::cout; using std::endl;
using std::vector;

using namespace std;

vector<int> multiplyByTwo(vector<int> &arr)
{
    vector<int> mult;
    mult.reserve(arr.size());

    for (const auto &i : arr) {
        mult.push_back(i * 2);
    }
    return mult;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    vector<int> arrby2;

    arrby2 = multiplyByTwo(arr);

    cout << "arr    - | ";
    copy(arr.begin(), arr.end(),
         std::ostream_iterator<int>(cout," | "));
    cout << endl;
    cout << "arrby2 - | ";
    copy(arrby2.begin(), arrby2.end(),
         std::ostream_iterator<int>(cout," | "));
    cout << endl;

    return 0;
}

Click here for the leetcode problem.

Returning an Empty Vector

#include <iostream>
#include <vector>

std::vector<int> returnEmptyVectors()
{
    return std::vector<int>();
}

int main()
{
    std::vector<int> vec2 = returnEmptyVectors();

    return 0;
}

Find the first element of a vector which is not in another vector

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> v1 = {1, 2, 3, 4};
    vector<int> v2 = {1, 2, 3, 4, 5, 6, 7};
    
    auto is_not = [&v1](int i) { 
        for (int j : v1) { 
            std::cout << "v1 : " << j <<" v2: " <<  i << std::endl;
            if (i == j) {
               return false;
            }
        }
        
        return true;
    };
    auto n2 = 4;
    
    auto result1 = std::find(begin(v1), end(v1), n2);
    auto result2 = std::find_if(begin(v2), end(v2), is_not);
 
    (result1 != std::end(v1))
        ? std::cout << "v1 contains " << n2 << '\n'
        : std::cout << "v1 does not contain " << n2 << '\n';
 
    (result2 != std::end(v2))
        ? std::cout << "The first unique number in v2: " << *result2 << '\n'
        : std::cout << "All elements are same in both v1 & v2\n";

    return 0;
}

Output

v1 : 1 v2: 1
v1 : 1 v2: 2
v1 : 2 v2: 2
v1 : 1 v2: 3
v1 : 2 v2: 3
v1 : 3 v2: 3
v1 : 1 v2: 4
v1 : 2 v2: 4
v1 : 3 v2: 4
v1 : 4 v2: 4
v1 : 1 v2: 5
v1 : 2 v2: 5
v1 : 3 v2: 5
v1 : 4 v2: 5
v1 contains 4
The first unique number in v2: 5

Click here to debug.

Two Dimensional Array 

Vector of Vector Initialisation

Initialising two dimensional array is little complicated. 

vector<Area> edgelist;

struct Area {
    int len;
    int breadth;
    int height;
}

void addEdge(int x, int y, int w)
{
   Area eList;
   eList.len = x;
   eList.breadth = y;
   eList.height = w;
   edgelist.push_back(eList);
}

Simplified way:

vector<Area> edgelist;

void addEdge(int x, int y, int w)
{
   edgelist.push_back({ x, y, w });
}

The above code adds just one vector elements. 

Initialising two dimensional array is little complicated. 

std::vector<std::vector<int> > fog(
    ROW_COUNT,
    std::vector<int>(COLUMN_COUNT)); // Defaults to zero initial value

Example:
    vector<vector<bool>> dp(len, vector<bool> (len, false));


For the below declaration, I'm not sure how to initialise the values.

vector<int> arr[size];

Insertion 


    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        vector<int> prev = intervals[0];
        vector<int> vec;
        
        for (int i = 1; i < intervals.size(); i++) {
            if (prev[1] > intervals[i][0]) {
                vec.push_back(prev[0]); 
                vec.push_back(intervals[i][1]);
            } else {
                prev = intervals[i];
                vec.push_back(intervals[i][0]); 
                vec.push_back(intervals[i][1]);
            }
            result.push_back(vec);
        }
        return result;
    }

Input is [[1,3],[2,6],[8,10],[15,18]]

The output is  [[1,6],[1,6,8,10],[1,6,8,10,15,18]]

Since the vec variable is declared outside the for loop, the values inserted on top of the previous values. 


    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        vector<int> prev = intervals[0];
        
        
        for (int i = 1; i < intervals.size(); i++) {
            vector<int> vec;
            if (prev[1] > intervals[i][0]) {
                vec.push_back(prev[0]); 
                vec.push_back(intervals[i][1]);
            } else {
                prev = intervals[i];
                vec.push_back(intervals[i][0]); 
                vec.push_back(intervals[i][1]);
            }
            result.push_back(vec);
        }
        return result;
    }

Input is [[1,3], [2,6], [8,10], [15,18]]

The output is  [[1,6], [8,10], [15,18]]

Accessing the last vector element using back()

    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        vector<vector<int>> result;        
        sort(intervals.begin(), intervals.end(), sortFinish);            
        result.push_back(intervals[0]);     
        
        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) {
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]); 
            }   
        }    
        return result;
    }

Size of the row & column of 2D vector

vector<vector<int>> intervals(5, vector<int>(4, 0));

int row = intervals.size();  // row would be 5
int col = intervals[0].size(); // column would be 5


References:

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/



Comments

Post a Comment