Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
We will discuss the insert methods of a badass data structure, i.e. deque, which contains the goodness of both, the good old stack and queue. In it we can access both the front and back thus breaking the LIFO and FIFO barriers. There are also ways to add elements directly in one of the interior positions, though it takes away the saliva inducing constant time complexity, giving us the worse yet not really linear time one. The insert methods discussed here are:
- deque::push_back() and deque::push_front()
- deque::insert()
- adding a single element at a particular iterator position
- To insert a number of same valued values starting at a particular iterator position
- To insert a number of values from a different object over a particular range of iterator positions
- deque::assign()
- assigning a bunch of same valued elements to the deque
- assigning a range of elements to the deque from a different object(can be deque, vector, array, etc.)
- deque::emplace()
- deque::swap()
1. deque::push_back() and deque::push_front()
The most typical of the ways to insert elements into the deque data structure are the push_back() and push_front() functions which lend it the name dequeue or the double sided queue. The push_front() function adds elements to the front of the deque. The push_back() function adds elements to the end of the deque.
They work in constant time and take only one argument of the type of deque.
Using push_front(), the added elements become the first indexed in the deque.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1,2,3 intially
mydeck.push_front(4);//elements of deque are ordered 4,1,2,3 now
Using push_back(), the added elements become the last indexed in the deque.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1,2,3 intially
mydeck.push_back(4);//elements of deque are ordered 1,2,3,4 now
In the following code we can see elements of two different arrays being inserted into a deque using push_front and push_back functions:
// deque::push_front() and deque::push_back()
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
int addfront[5]={1,2,3,4,5};
int addback[5]={6,7,8,9,10};
int i=0;int j=0;
while(i<5){
mydeck.push_front(addfront[i]);
i++;
}
while(j<5){
mydeck.push_back(addback[j]);
j++;
}
cout<<"No. of the elements in deque is "<<mydeck.size()<<endl;
cout<<"The elements at front and back are: "<<mydeck.front()<<" & "<<mydeck.back()<<endl;
}
Output:
No. of the elements in deque is 10
The elements at front and back are: 5 & 10
We can observe that last element of the array addfront we used, i.e. 5, is at the front of the deque(because we inputed the array elements from index 0 to 4, 4th indexed element being added at the end using pushfront()) and last element of the array addback, i.e. 10, is at back of the deque.
2. deque::insert()
It is a more general way of inserting elements in a deque. Here the elements provided are put in place using copy construtor or move constructor. It works in at most linear time complexity. The three ways to insert elements into the deque are described below.
* adding a single element at a particular iterator position
Using deque::insert(iterator pos, const value_type& val), the added element, i.e. val, is inserted into the position given by iterator pos.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1, 2, 3 intially
deque<int>::iterator it=mydeck.begin();//iterator it is providing position to the beginning of the deque
it++;//now it points to the 2nd positioned element i.e. 2
mydeck.insert(it, 37);//inserting 37 at the 2nd position
//elements of deque are ordered 1, 37, 2, 3 now
In the following code we use insert() function to insert an element at a particular position.
// deque::insert(iterator pos, const value_type& val)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
int add[5]={1,2,3,4,5};
int i=0;
while(i<5){
mydeck.push_back(add[i]);
i++;
}
deque<int>::iterator it=mydeck.begin(); /*declaring an iterator of a class of type deque<int> and intitializing, with it helping us access beginning element of mydeck */
cout<< *it<<endl; //the beginning element, i.e., 1
/* now to add an element to a particular position e.g. to the third position in the deque we can first point the iterator to the third index and then use insert to add the element to this index. */
it=it+3;// now the iterator is helping us access the fourth element
mydeck.insert(it, 37); //inserting 37 at the position given by iterator it
cout<< *it<<endl;//37
it++;
cout<< *it<<endl;//4
//now the fourth element of deque is 37 and fifth element in the deque 4
}
* To insert a number of same valued values starting at a particular iterator position
Using deque::insert(iterator pos, number_of_entries n, const value_type& val), a number of elements valued val, are inserted into the position given by iterator pos, n number of times.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1, 2, 3 intially
deque<int>::iterator it=mydeck.begin();//iterator it is providing position to the beginning of the deque
it++;//now it points to the 2nd positioned element i.e. 2
mydeck.insert(it,2, 37);//inserting 37 starting at the 2nd position 2 times
//elements of deque are ordered 1, 37, 37, 2, 3 now
In the following code we use insert() function to insert elements starting at a particular position a given number of times.
// deque::insert(iterator position, number_of_entries n, const value_type& val)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
int add[5]={1,2,3,4,5};
int i=0;
while(i<5){
mydeck.push_back(add[i]);
i++;
}
deque<int>::iterator it=mydeck.begin();
it=it+3;
mydeck.insert(it, 3, 37); //inserting 37 starting from index pointed to by iterator it, a total of 3 times
cout<< *it<<endl;//37
it++;
cout<< *it<<endl;//37
it++;
cout<< *it<<endl;//37
it++;
cout<< *it<<endl;//4
}
* To insert a number of values from a different object over a particular range of iterator positions
Using deque::insert(iterator position, input_iterator start, input_iterator end), a number of elements are inserted from a different object into the position given by iterator pos, over the range specified by input iterators.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1, 2, 3 intially
vector<int> myvector={4,5,6};// we'll insert the elements of this vector into mydeque
deque<int>::iterator it=mydeck.begin();//iterator it is providing position to the beginning of the deque
it++;//now it points to the 2nd positioned element i.e. 2
mydeck.insert(it,myvector.begin(), myvector.end());//inserting elements of myvector at the position specified by it
//elements of deque are ordered 1, 4, 5, 6, 2, 3 now
In the following code we use insert() function to insert a particular range of elements of a different object(which is another deque in this example) starting at a particular position
// deque::insert(iterator position, input_iterator start, input_iterator end)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck1;
deque<int> mydeck2;
int i=0;
while(i<5){
mydeck1.push_back(i+1);
i++;
}
deque<int>::iterator it=mydeck1.begin();
it=it+2;
while(i<8){
mydeck2.push_back(i+1);
i++;
}
mydeck1.insert(it, mydeck2.begin(), mydeck2.end()); //inserting values from starting index of mydeck2 to its last index
cout<< *it<<endl;//6
it++;
cout<< *it<<endl;//7
it++;
cout<< *it<<endl;//8
it++;
cout<< *it<<endl;//3
}
It is not neccessary for the other object to be deque, it can be vector , or any other object which can provide us the respective iterator arguments
3. deque::assign()
It Replaces the current elements with new ones provided to it. It works in at most linear time complexity. Two of the ways to use it are:
* assigning a bunch of same valued elements to the deque
Using deque::assign(number_of_entries n, const value_type& val), a number of elements valued val, are inserted into the deque n number of times. These replace the elements previously present.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1, 2, 3 intially
mydeck.assign(2, 37);//assigning two 37s to the deque after deleting all the previous elements
//elements of deque are ordered 37, 37 now
In the following code we use assign() function to insert an element a given number of times after deleting all the previous ones.
//deque::assign(number_of_entries n, const value_type& val)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
mydeck.push_back(1);
mydeck.push_back(2);
cout<<mydeck.size()<<endl;//2 (there are 2 elements in the deque)
mydeck.assign(5, 6);
cout<<mydeck.size()<<endl;//5 (the two elements have been replaced by five sixes)
}
* assigning a range of elements to the deque from a different object(can be deque, vector, array, etc.)
Using deque::assign(input_iterator start, input_iterator end), a number of elements are inserted from a different object into the position given by iterator pos, over the range specified by input iterators. The original elements are all deleted first.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1, 2, 3 intially
vector<int> myvector={4,5,6};// we'll assign the elements of this vector to mydeque
mydeck.assign(it,myvector.begin(), myvector.end());//inserting elements of myvector at the position specified by it
//elements of deque are ordered 1, 4, 5, 6, 2, 3 now
In the following code we use insert() function to insert a particular range of elements of a different object(which is another deque in this example) starting at a particular position
//deque::assign(input_iterator first, input_iterator last)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
mydeck.push_back(1);
mydeck.push_back(2);
cout<<mydeck.size()<<endl;//2 (there are 2 elements in the deque)
int assign_array[]={3,4,5,6};
mydeck.assign(assign_array, assign_array+4);//last pointer address is not included
cout<<mydeck.size()<<endl;//4 (the two elements have been replaced by elements of array)
}
4. deque::emplace()
It is almost same as insert(), the only difference being this function constructs the arguments provided in the position provided by the iterator itself. It works in at most linear time complexity.
Using deque::emplace(iterator pos, const value_type& val), the added element, i.e. val, is directly constructed into the position given by iterator pos.
Example:
deque<int> mydeck={1,2,3};// elements of deque ordered 1,2,3 intially
deque<int>::iterator it=mydeck.begin();//iterator it is providing position to the beginning of the deque
it++;//now it points to the 2nd positioned element i.e. 2
mydeck.emplace(it, 37);//inserting 37 at the 2nd position
//elements of deque are ordered 1, 37 ,2 ,3 now
In the following code we use emplace() function to insert an element at a particular position.
//deque::emplace(iterator position, Args&&.. args)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck;
mydeck.push_back(1);
mydeck.push_back(2);
mydeck.push_back(4);
deque::iterator it=mydeck.begin();
it++;
mydeck.emplace(it, 3);
for(it=mydeck.begin();it<mydeck.end();it++)
cout<<*it<<endl;
}
Output:
1
3
2
4
5. deque::swap()
It exchanges the element of one deque to another and vice versa. The other deque should be of the same type. It works in constant time.
Using deque::swap(deque& d2), the elements of deque that calls this function and the the one that is called are swapped.
Example:
deque<int> mydeck1={1,2,3};
deque<int> mydeck2={4,5,6};
mydeck.swap(mydeck2);
//elements of deque mydeck1 are ordered 4, 5, 6 now
//elements of deque mydeck2 are ordered 1 2, 3 now
In the following code we use swap() function to exchange elements of called and callee objects.
//deque::swap(deque& D2)
#include<iostream>
#include<deque>
using namespace std;
int main(){
deque<int> mydeck1;
mydeck1.push_back(1);
mydeck1.push_back(5);
mydeck1.push_back(6);
deque<int> mydeck2={2,3,4};
deque<int>::iterator it;
mydeck1.swap(mydeck2);
for(it=mydeck1.begin();it<mydeck1.end();it++)
cout<<*it<<" ";
cout<<'\n';
for(it=mydeck2.begin();it<mydeck2.end();it++)
cout<<*it<<" ";
cout<<'\n';
}
Output:
2 3 4
1 5 6
