Page 1 of 1

C++ Vector Tutorial II Inserting and deleting, assigning multiple values, other Methods, perf Rate Topic: ***** 2 Votes

#1 jjhaag  Icon User is offline

  • me editor am smartastic
  • member icon

Reputation: 44
  • View blog
  • Posts: 1,789
  • Joined: 18-September 07

Posted 25 September 2007 - 09:26 PM

*
POPULAR

PART II
Inserting and Deleting Elements
Using resize() is a convenient way to increase the size of a vector by a large number of elements that all require the same value, but it would quickly become tedious if that was the only way to add or delete elements, especially single values. However, the vector container provides a number of methods for the addition and deletion of particular elements.

For adding a single element to the end of a vector, the method push_back() is used. It is used with the following calling syntax:
void push_back( const TYPE& val )


This code appends the element val to the end of the vector. Similarly, to remove a single element from the end of a vector, the function pop_back() is used:
void pop_back();



The following code demonstrates these functions:
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	
	//  initialize empty vector of integers
	vector<int> vectorOne;
	
	//  use push_back() to add 10 random integers to the vector
	for (long index=0; index<10; ++index) vectorOne.push_back(rand());
	
	//  display contents of vector
	cout << "vectorOne contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl << endl;
	
	//  add two more elements to the vector using push_back()
	for (long index=0; index<2; ++index) vectorOne.push_back(rand());
	
	//  display contents of vector
	cout << "vectorOne now contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl << endl;
	
	//  remove the last 9 elements of the vector using pop_back()
	for (long index=0; index<9; ++index) vectorOne.pop_back();
	
	//  display contents of vector
	cout << "vectorOne now contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl << endl;
	
}



Output:

vectorOne contains the following elements:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 

vectorOne now contains the following elements:
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 

vectorOne now contains the following elements:
41 18467 6334 



It's perfectly reasonable to assume that, at some point, someone is going to need to insert or remove an element at a specific location other than the very end. The vector container provides methods for doing so: insert() and erase(). These are both very handy functions, but they require the use of iterators, which some may be unfamiliar with. Iterators are used to access elements of the STL containers. I won't go into much detail on them (they definitely warrant a tutorial of their own), but for the moment, they can be though of like pointers - they represent an address within a container, and it is possible to dereference an iterator to access a particular element within the container. The calling syntax for insert() is as follows:

iterator insert( iterator location, const TYPE& value );
void insert( iterator locatio, size_type number, const TYPE& value );
void insert( iterator location, input_iterator start, input_iterator end );



The first inserts the element value before the location location, returning an iterator to the newly inserted element (note that you don't actually need to do anything with the return value, nor even specify storage for it in the code, unless there is something specific that you're going to do to the new element). The second line inserts number copies of the element value before the location location. The third inserts the values from start to end before the location location. The iterators start and end can refer to a different vector, making this syntax useful for copying some or all of the contents of one vector into another.

The function erase() is called with any of the following syntaxes:

iterator erase( iterator location );
iterator erase( iterator start, iterator end );



The first deletes the element at location location, while the second deletes the elements from start to end. Both return an iterator to the last element following the ones that were erased. The code that follows demonstrates the use of insert() and delete():

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	
	//  initialize empty vector of integers
	vector<int> vectorOne;
	vector<int> vectorTwo;
	
	//  use push_back() to add 10 random integers from 0-4 to vectorOne
	for (long index=0; index<10; ++index) vectorOne.push_back(rand()%5);
	
	//  use push_back() to add 10 random integers from 5-9 to vectorOne
	for (long index=0; index<10; ++index) vectorTwo.push_back(5+rand()%5);
	
	//  display contents of vectorOne
	cout << "vectorOne contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl;
	
	//  display contents of vectorTwo
	cout << "vectorTwo contains the following elements:" << endl;
	for (long index=0; index<(long)vectorTwo.size(); ++index) cout << vectorTwo.at(index) << " ";
	cout << endl;
	
	
	cout << endl << "inserting middle 6 elements from vectorOne into vectorTwo, then erasing them..." << endl << endl;
	
	
	//  insert middle 6 elements from vectorOne into vectorTwo...
	vectorTwo.insert(vectorTwo.begin()+5, vectorOne.begin()+2, vectorOne.end()-2);
	
	//  ...then erase those elements from vectorOne
	vectorOne.erase(vectorOne.begin()+2, vectorOne.end()-2);
	
	//  display contents of vectorOne
	cout << "vectorOne now contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl;
	
	//  display contents of vectorTwo
	cout << "vectorTwo now contains the following elements:" << endl;
	for (long index=0; index<(long)vectorTwo.size(); ++index) cout << vectorTwo.at(index) << " ";
	cout << endl;
	

	cout << endl << "erasing the third element from vectorTwo, and inserting a zero at the front." << endl << endl;
	
	
	//  erase third element (index=2) and insert a zero at start (index=0)
	vectorTwo.erase(vectorTwo.begin()+2);
	vectorTwo.insert(vectorTwo.begin(), 0);
	
	//  display contents of vectorTwo
	cout << "vectorTwo now contains the following elements:" << endl;
	for (long index=0; index<(long)vectorTwo.size(); ++index) cout << vectorTwo.at(index) << " ";
	cout << endl;
	
}



Output:

vectorOne contains the following elements:
1 2 4 0 4 4 3 3 2 4 
vectorTwo contains the following elements:
5 5 6 7 6 6 5 7 7 6 

inserting middle 6 elements from vectorOne into vectorTwo, then erasing them...

vectorOne now contains the following elements:
1 2 2 4 
vectorTwo now contains the following elements:
5 5 6 7 6 4 0 4 4 3 3 6 5 7 7 6 

erasing the third element from vectorTwo, and inserting a zero at the front.

vectorTwo now contains the following elements:
0 5 5 7 6 4 0 4 4 3 3 6 5 7 7 6 



The only tricky part of the above code (in the sense that it hasn't been covered here yet) are the functions begin() and end(). begin() returns an iterator to the first element of a vector, while end() returns an iterator to the element just past the last element in a vector. So to specify an iterator to the second element of a vector v, we can use v.begin() + 1 (remember that vector indices, like any normal C array, start at 0). Similarly, to get an iterator to the second to last element of v, we can use v.end() - 2. So, as an alternative to using an index in a for loop that must be less than v.size() for running through the elements of a vector, we could use the following syntax:

vector<int>iterator vitr;
for (vitr = v.begin(); vitr != v.end(); ++vitr) {
   //	do something here
}





Assigning Values to An Entire Vector
Most of the techniques for assigning values to a vector dealt with to this point consider only assigning a value to a single element, or assigning multiple elements the same value. There are a couple of functions that allow for the en masse assignment of elements to a vector. The first is assign(). This function has the syntax:

void assign( size_type number, const TYPE& value );
void assign( input_iterator start, input_iterator end );



The first version is used to fill a vector with number copies of the element value. This is especially useful when you've already declared a vector without assigning any values to it, and need to fill it up. The second version fills a vector with the elements between the iterators start and end. These can be iterators of belonging to another vector, which allows you to copy a portion of one vector into another (as we did with insert). In my experience, however, the most frequent use of the second form is to copy a raw array into a vector. This is especially useful when reading data from a stream into an array buffer (such as in the case of file I/O or user input), when you would really rather have it stored in a vector. The following code demonstrates both of the uses of assign, using it to fill an empty vector with multiple copies of a particular value, then reassign the vector with the elements stored in a static array:

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	
	//  initialize empty vector integers
	vector<int> vectorOne;
	
	//  display contents of vectorOne
	cout << "vectorOne contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl << endl;
	
	//  create a static array with 10 integer elements
	int arrayOne[]={ 4, 2, 6, 3, 6, 3, 4, 6, 4, 3};
	
	//  use assign() to give vectorOne 5 copies of the integer 1
	cout << "Using assign() to fill vector with 5 copies of integer 1." << endl << endl;
	vectorOne.assign(5,1);
	
	
	//  display contents of vectorOne
	cout << "vectorOne contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl << endl;

	//  display contents of arrayOne - note the dangerous, dangerous [] usage
	cout << "arrayOne contains the following elements:" << endl;
	for (long index=0; index<10; ++index) cout << arrayOne[index] << " ";
	cout << endl << endl;
	//  assign  contents of static array to the vector
	cout << "Assigning contents of arrayOne to vectorOne." << endl << endl;
	vectorOne.assign(arrayOne, arrayOne+10);
	
	//  display contents of vectorOne
	cout << "vectorOne contains the following elements:" << endl;
	for (long index=0; index<(long)vectorOne.size(); ++index) cout << vectorOne.at(index) << " ";
	cout << endl;
	
	return EXIT_SUCCESS;
}



Output:

vectorOne contains the following elements:
						//	<- this line is empty

Using assign() to fill vector with 5 copies of integer 1.

vectorOne contains the following elements:
1 1 1 1 1 

arrayOne contains the following elements:
4 2 6 3 6 3 4 6 4 3 

Assigning contents of arrayOne to vectorOne.

vectorOne contains the following elements:
4 2 6 3 6 3 4 6 4 3 



The second major method for multiple assignment is the function swap(). This function, as its name suggests, swaps the content of one vector with another. The calling syntax is:

void swap( container& source );



You should note well the fact that this function really does swap the vectors - the contents of source wind up in the calling vector, and the contents of the calling vector wind up in source. The following swaps the contents of one vector for another:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(int argc, char** argv) {
	
	vector<string> vectorOne, vectorTwo;
	vectorOne.push_back("I'm first");
	vectorTwo.push_back("I'm second");
	
	//  display contents of vectorOne
	cout << "vectorOne: ";
	for (vector<string>::iterator index=vectorOne.begin(); index!=vectorOne.end(); ++index) {
		cout << *index;
	}
	cout << endl;
	
	//  display contents of vectorTwo
	cout << "vectorTwo: ";
	for (vector<string>::iterator index=vectorTwo.begin(); index!=vectorTwo.end(); ++index) {
		cout << *index;
	}
	cout << endl << endl;
	
	//  swap vector contents
	cout << "Using swap() to exchange contents of vectorOne and vectorTwo." << endl << endl;
	vectorOne.swap(vectorTwo);
	
	//  display contents of vectorOne
		cout << "vectorOne: ";
		for (vector<string>::iterator index=vectorOne.begin(); index!=vectorOne.end(); ++index) {
			cout << *index;
		}
		cout << endl;
		
		//  display contents of vectorTwo
		cout << "vectorTwo: ";
		for (vector<string>::iterator index=vectorTwo.begin(); index!=vectorTwo.end(); ++index) {
			cout << *index;
		}
		cout << endl << endl;
	
	return EXIT_SUCCESS;
}



Output:

vectorOne: I'm first
vectorTwo: I'm second

Using swap() to exchange contents of vectorOne and vectorTwo.

vectorOne: I'm second
vectorTwo: I'm first



A rather trivial example, since each vector actually contains only one string. But it works. To be perfectly honest, though, Iíve never had to use swap() except when just playing around with the various vector methods for learning purposes. If anyone knows of a good reason to use swap() where another method wouldnít work as well, please post it here for our enlightment.


That covers many of the basic vector methods available, and concludes Part II. In the next part of this tutorial, Iíll be dealing with all of the vector methods that I can think of that havenít been presented thus far, as well as some considerations of the performance of vectors.



Other Vector Methods
There are a few more methods to round out the full complement of builtin functions available for vectors. I wonít present a lot of code for these, as most of them are relatively simple.

front()
back()


The front() and back() methods are used to return references to the start and end of a vector, respectively. The back() method is especially convenient when you need to play around with an element after youíve push_back()íed it into a vector.

begin()
end()


begin() and end() return random access iterators to the first element, and the location just after the last element, respectively. They were briefly discussed when dealing with erasing particular elements, and that is when I use them most often. As with any iterator, they can be dereferenced to obtain a reference to the element that they point to.

Since front() and back() both return references, and begin() and end() both return iterators that can be dereferenced, these two sets of methods are often interchangeable when the modification of a single element element is required. The following two lines produce the same result:
sampleVector.back() = val;
*(sampleVector.end()-1) = val;


The first (reference-return) form is obviously a much cleaner and simpler interface. However, the fact that the iterators returned by begin() and end(), like pointers, can be incremented, decremented, and dereferenced, makes the iterator approach much more versatile and powerful.


rbegin()
rend()


rbegin() and rend() return the same thing as begin() and end(), except the iterators that they return are reverse iterators. Reverse iterators are like dyslexic iterators Ė they exchange the meanings of +/-, +=/-=, and ++/--. Personally, I get more than a little confused by them, so I usually wind up just using random access iterators and take care of directionality and incrementing/decrementing myself. If anyone wants to explain them in more detail, feel free Ė I know it would be a learning experience for me.


clear()


clear() removes all of the elements from a vector. This means that size() will return zero after clear() is called. However, the capacity of the vector will remain the same (at least on all machines and using all compilers that Iíve found Ė I do not know whether this is specified in the ISO standard).


empty()


empty() returns true for the vector v if v.size()==0, and false otherwise. Simple, but useful in for loops and do-while statements to prevent overrunning the data if there are no elements to access (while avoiding extensive try-catch blocks).


Thatís about all for the vector methods. They also support the full range of assignment and comparative operators, but that will have to wait for another day, or maybe for a tutorial on operator overloading.



Performance Issues
Throughout this tutorial I have simply presented the methods for the vector container, without regards to its performance. In fact, vectors are pretty well optimized, and so will show good (fast) performance in a lot of situations. However, if youíre specifically looking for performance from a container class, there are some things that you should be aware of. The following sections list the complexity of each of the methods discussed here.

Constant time vector methods O(1)
at()
back()
begin()
capacity()
end()
front()
max_size()
pop_back()
push_back()*
rbegin()
rend()
swap()



Linear time vector methods O(N)
assign() 
clear()
empty()
erase()
insert()*
reserve()
resize()
size()



This should give you a pretty good idea about where you can expect your performance bottlenecks to be in programs using vectors extensively. However, note the asterisked entries. push_back() runs in constant time, but only if size() is less than capacity. It will run in constant time right up until it runs out of allocated memory, then waits around for what amounts to an internal call to reserve() to occur, which occurs in linear time. Therefore, avoiding tons of push_back()ís is a good way to prevent performance hits. Frequently, using reserve() at the outset of a program to allocate a huge block of memory, on the order of what you expect usage to be, can make a big difference (at least in my experience).

The insert() method is flagged for a different reason. For vectors, insert() runs in linear time, but it can be much faster in other containers such as list or deque. The deque can be particularly good, both for performance, and the fact that it also offers push_front() and pop_front() methods for inserting and deleting from the first element of the container, if thatís something you have frequent use for. Fortunately, most of the other STL containers have similar methods to vectors, so learning them after getting comfortable with vectors can be pretty easy.



Multidimensional Vectors
One of the more frustrating aspects of using raw arrays is when multidimensional arrays (2 or more dimensions) are required. Although fundamentally logical, I frequently find the code required to create such arrays convoluted and prone to errors. Vectors themselves cannot be multidimensional Ė they do not support multiple subscripts. However, there is nothing that says the datatype stored in a vector cannot be simply another vector. Initialization and assignment require slightly more complex code than in the standard 1D vector; however, the overall amount of code required can be greatly reduced, because the constructors and destructor take care of memory allocation/deallocation when the objects are intialized or go out of scope.

The following code demonstrates a few of the uses of multidimensional arrays constructed from STL vectors. The user is asked to input a series of 10 floating point numbers. For each number entered, the sine of the number is calculated, and both are stored in an array. The array is then sorted, according to the sine values, and all of the numbers except those with the two largest and two smallest sine values are deleted.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(int* argc, char* argv) {
		
	vector<vector<float> > mdVector;	//	declares empty 2D-array constructed from STL vectors
		
	float tempValue;			//  temporary value for storing input
	
	//  get a series of 10 floating point numbers
	do {
		//	get numbers from user
		cout << "Enter a floating-point number (no characters!): ";
		cin >> tempValue;
			
		//  input number & its sine value into array
		mdVector.push_back( vector<float>(2,0.0) );	//  add 2-element row to array
		mdVector.back().at(0)=tempValue;		//  store number
		mdVector.back().at(1)=sin(tempValue);	//  store sin(number)
				
	} while( mdVector.size()<10 );

	//  display inputted numbers and their respective sine-values
	cout << endl << "Unsorted numbers:" << endl << "#\tsin(#)" << endl;
	for (long row=0; row<(long)mdVector.size(); ++row) {
		cout << mdVector.at(row).at(0) << "\t" << mdVector.at(row).at(1) << endl;
	}
	
	//  sort numbers by their sine values, using a quick and dirty 
	//  direct sorting algorithm, and sqaw() to exchange rows
	for (long row1=0; row1<(long)mdVector.size(); ++row1) {
		for (long row2=row1; row2<(long)mdVector.size(); ++row2) {
			if ( mdVector.at(row1).at(1) > mdVector.at(row2).at(1) ) {
				mdVector.at(row1).swap(mdVector.at(row2));
			}
		}
	}

	//  display numbers sorted by their respective sine-values
	cout << endl << "Sorted numbers:" << endl << "#\tsin(#)" << endl;
	for (long row=0; row<(long)mdVector.size(); ++row) {
		cout << mdVector.at(row).at(0) << "\t" << mdVector.at(row).at(1) << endl;
	}
	
	//  remove all rows except those with the two largest and two smallest sine values
	mdVector.erase(mdVector.begin()+2, mdVector.end()-2);
	
	//  display the array with the numbers removed
	cout << endl << "Numbers with all but 2 largest and 2 smallest sine values removed :" << endl << "#\tsin(#)" << endl;
	for (long row=0; row<(long)mdVector.size(); ++row) {
		cout << mdVector.at(row).at(0) << "\t" << mdVector.at(row).at(1) << endl;
	}
	
	cout << "Press any key to continue...";
	cin.ignore();
	cin.get();
	return EXIT_SUCCESS;
}



The code above doesnít really contain anything new, just an extension. The critical thing to note here is that the at() method returns a vector; individual elements of the array need to be accessed with the somewhat peculiar mdVector.at(row).at(col) syntax (accessing individual elements can also be done using the [][] operator(s), just as one would with a raw array).

Iím not really going to present anything more on multidimensional arrays constructed from vectors. Although they can incur a serious performance hit when they get large or need to be frequently resized, they are very useful for the convenience of multidimensional arrays without the inconvenience of dealing with memory allocation/deallocation.



Thatís all for now. Hope this helps out some of you, and that any mistakes are caught before they hinder too many.

Is This A Good Question/Topic? 9
  • +

Replies To: C++ Vector Tutorial II

#2 93FFF  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 19-November 07

Posted 10 December 2007 - 01:28 PM

Thank you very much again for clarifying even more about vector functions.
Was This Post Helpful? 0
  • +
  • -

#3 dpacheco  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 27-May 09

Posted 27 May 2009 - 12:50 PM

:) This tutorial will help me a lot. thks :)
Was This Post Helpful? 0
  • +
  • -

#4 codetonic  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 46
  • Joined: 13-May 09

Posted 03 June 2009 - 03:18 PM

Very helpful, thanks.

The difference between the reference front() and the iterator begin()
opened some doors of understanding for me.
Where can I find these kinds of details?
Types of containers and how to use them for example?

Perhaps we could see a demonstration of the containers with vectors:

vector::value_type
vector::reference
vector::iterator
Was This Post Helpful? 0
  • +
  • -

#5 Guest_PC Scripts*


Reputation:

Posted 02 November 2010 - 03:12 PM

I used the swap() function to shuffle a vector of structures to create a deck for a card game. Blackjack to be exact.
Was This Post Helpful? 0

#6 KiraGao  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 18-September 12

Posted 18 September 2012 - 04:18 PM

Such a perfect tutor for vector.
Thanks so much!
Was This Post Helpful? 0
  • +
  • -

#7 theleo  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 27-June 13

Posted 27 June 2013 - 07:53 PM

Thank you for the tutorial. Very helpful!!

Small note:
- size is not a O(N) operation but a constant one.
source: http://www.cplusplus...or/vector/size/
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1