Monday, May 7, 2012

operations on vector in c++


Create, Copy, and Destroy Operations
Table 1, below lists the constructors and destructors for vectors. You can create vectors with and without elements for initialization. If you pass only the size, the elements are created with their default constructor. Note that an explicit call of the default constructor also initializes fundamental types such as int with zero, for some remarks about possible initialization sources.

Table 1. Constructors and Destructors of Vectors


Nonmodifying Operations

Table 2, lists all nonmodifying operations of vectors.

Note: reserve() manipulates the vector because it invalidates references, pointers, and iterators to elements. However, it is mentioned here because it does not manipulate the logical contents of the container.

Table 2. Nonmodifying Operations of Vectors

Assignments

Table 3. Assignment Operations of Vectors

Table 3 lists the ways to assign new elements while removing all ordinary elements. The set of assign() functions matches the set of constructors. All assignment operations call the default constructor, copy constructor, assignment operator, and/or destructor of the element type, depending on how the number of elements changes. For example:

std::list<Elem> l;
std::vector<Elem> coll;
...
//make coll be a copy of the contents of l
coll.assign(l.begin(),l.end());

Element Access

Table 4, shows all vector operations for direct element access. As usual in C and C++, the first element has index 0 and the last element has index size()-1. Thus, the nth element has index n-1. For nonconstant vectors, these operations return a reference to the element. Thus you could modify an element by using one of these operations (provided it is not forbidden for other reasons).

Table 4. Direct Element Access of Vectors


The most important issue for the caller is whether these operations perform range checking. Only at() performs range checking. If the index is out of range, it throws an out_of_range
exception. All other functions do not check. A range error results in undefined behavior. Calling operator [], front(), and back() for an empty container always results in undefined behavior:

std::vector<Elem> coll; // empty!
coll [5] = elem; // RUNTIME ERROR ? undefined behavior
std::cout << coll. front (); // RUNTIME ERROR ? undefined behavior


So, you must ensure that the index for operator [] is valid and the container is not empty when either front() or back() is called:

std::vector<Elem> coll; // empty!
if (coll.size() > 5) {
coll [5] = elem; // OK
}
if (!coll.empty()) {
cout << coll.front(); // OK
}
coll.at(5) = elem; // throws out_of_range exception


Iterator Functions
Vectors provide the usual operators to get iterators (Table 5). Vector iterators are random access iterators. Thus, in principle you could use all algorithms of the STL.

Table 5. Iterator Operations of Vectors


The exact type of these iterators is implementation defined. However, for vectors they are often ordinary pointers. An ordinary pointer is a random access iterator, and because the internal structure of a vector is usually an array, it has the correct behavior. However, you can't count on it. For example, if a safe version of the STL that checks range errors and other potential problems is used, the iterator type is usually an auxiliary class.

Iterators remain valid until an element with a smaller index gets inserted or removed, or reallocation occurs and capacity changes. 

Inserting and Removing Elements

Table 6 shows the operations provided for vectors to insert or to remove elements. As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container. Regarding performance, you should consider that inserting and removing happens faster when 

  • Elements are inserted or removed at the end
  • The capacity is large enough on entry
  • Multiple elements are inserted by a single call rather than by multiple calls
Table 6: Insert and Remove Operations of Vectors


Vectors provide no operation to remove elements directly that have a certain value. You must use an algorithm to do this. For example, the following statement removes all elements that have the value val:

std::vector<Elem> coll;
...
//remove all elements with value val
coll.erase(remove(coll.begin(),coll.end(),
val),
coll.end());

To remove only the first element that has a certain value, you must use the following statements:

std::vector<Elem> coll;
...
//remove first element with value val
std::vector<Elem>::iterator pos;
pos = find(coll.begin(),coll.end(),
val);
if (pos != coll.end()) {
coll.erase(pos);
}

Splice Function


Linked lists have the advantage that you can remove and insert elements at any position in constant time. If you move elements from one container to another, this advantage doubles in that you only need to redirect some internal pointers (figure below)

Figure : Splice Operations to Change the Order of List Elements


To support this ability, lists provide not only remove() but also additional modifying member functions to change the order of and relink elements and ranges. You can call these operations to move elements inside a single list or between two lists, provided the lists have the same type the table below lists these functions.

Figure : Special Modifying Operations for List


See Also:

No comments:

Post a Comment