Friday, July 30, 2010

Invalidating Iterators

A call to push_back() on a vector can invalidate all of it's iterators.

If the vector's capacity is reached, then a reallocation occurs. All of the elements will be copied to the new location, and deleted from the old location. Reallocations typically increase the capacity from 1.5 to 2 times. You can tell what the capacity is by calling the member function, capacity(). You can set the capacity by calling the member function reserve(). You see how much capacity you have left by calculating v.capacity() - v.size(). You can call resize() to increase or decrease the size. You can increase the memory footprint of the vector with resize, but you cannot decrease the memory footprint with resize(). If you want to do this, you can use the "Swap Trick", where you copy the elements to a newly created empty vector, then call swap() on the old and new vectors.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 241.

Wednesday, July 28, 2010

For Loop Iterators

The for loop end criterion with an STL iterator can use the '<' operator instead of the '!=' operator only if the STL iterator is a random access iterator.

It is recommended to always use '!=' for consistency, and for the small chance that someone changes to a container that does not have a random access iterator.

Reference: "The C++ Standard Library" by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 257.

Sunday, July 25, 2010

Modifying Temporary Values

For fundamental types, like int and float, you are not allowed to modify temporary values, while you are allowed to modify the temporary values of classes and structs.

This sometimes shows up when porting code from a compiler that uses classes for vector iterators, to pointers as vector iterators. In the first case, ++v.begin() would compile, while in the second case it wouldn't, because you cannot modify the temporary created from b.begin().

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis, Addison-Wesley, 1999, p. 258.

The advance() Function Template

Given an STL container with 1 element,and an iterator, i, pointing to that element; then advance(i, 2) is undefined.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis, Addison-Wesley, 1999, p. 259.

Thursday, July 22, 2010

The advance() Function Template

The advance() function template, which is declared in the <iterator> header file has constant complexity for random access iterators, and linear complexity for all other iterators.

This is because advance() typically uses += for random access iterators, and a loop of ++ for the other iterators.

Reference: The C++ Standard Library: A Tutorial and Reference Nicolai M. Josuttis. Addison-Wesley, 1999, p. 259-260.

Wednesday, July 21, 2010

Class Inheritance


Public Inheritance:
-------------------
     Base            Client
    +----------+    +-------+
+---|Public<========|       |
|+--|Protected |    |       |
||  |Private   |    |       |
||  +----------+    +-------+
||
||    Derived 1      Client 1
||   +----------+   +-------+
+|-->|Public<=======|       |
+--->|Protected |   |       |
     |Private   |   |       |
     +----------+   +-------+

Protected Inheritance:
----------------------
     Base            Client
    +----------+    +--------+
+---|Public<========|        |
|+--|Protected |    |        |
||  |Private   |    |        |
||  +----------+    +--------+
||
||    Derived 1      Client 1
||   +----------+   +--------+
||   |Public<=======|        |
++-->|Protected |   |        |
     |Private   |   |        |
     +----------+   +--------+

Private Inheritance:
--------------------
     Base            Client
    +----------+    +--------+
+---|Public<========|        |
|+--|Protected |    |        |
||  |Private   |    |        |
||  +----------+    +--------+
||
||    Derived 1      Client 1
||   +----------+   +--------+
||   |Public<=======|        |
||   |Protected |   |        |
++-->|Private   |   |        |
     +----------+   +--------+

The single line arrows show what becomes brought into the derived class's access levels.  The double line arrows show what the clients see.

Tuesday, July 20, 2010

vector and string Iterator Implementations

Eventhough the implementation of an iterator is implementation-defined, vector and string iterators are usually implemented as T* and char*, respectively.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 258-259.

Sunday, July 18, 2010

Reverse Iterators

With respect to iterators and reverse iterators, the iterator has the same physical and logical position, and the reverse iterator has a physical position different that then the logical position. Note that the Physical location is where the iterator really points, and logical location is where the value will be read or written.

This is because it is not valid to point to an element before the first element in a container, but you are allowed to point to the element after he last element in the container. When you call base(), it adjusts this discrepancy.

Below is an example of a vector of ints containing 0, 1, and 2:

          begin()                   end()
          |Logical                  |Logical
          |Physical                 |Physical
          V                         V
x         0        1       2        y
^         ^                ^        ^
|Logical  |Physical        |Logical |Physical 
|         |                |        | 
rend()    rend()           rbegin() rbegin()


Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis, Addison-Wesley, 1999, p. 267.

Friday, July 16, 2010

Reverse Iterators


If v is an object of type vector<int>, then
 v.rbegin()==vector<int>::reverse_iterator(v.end())   &&
 v.rend()  ==vector<int>::reverse_iterator(v.begin()) &&
 v.begin() ==v.rend().base()                          &&
 v.end()   ==v.rbegin().base()

Notice the base() calls to adjust the iterators as shown in the following diagram:

           begin()                     end()
           |Logical                    |Logical
           |Physical                   |Physical
           V                           V
x          0         1       2         y
^          ^                 ^         ^
|Logical   |Physical         |Logical  |Physical 
|          |                 |         | 
rend()     rend()            rbegin()  rbegin()

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 269. 

Wednesday, July 14, 2010

Insert Iterators

insert iterators are output iterators.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999. p. 271.

Monday, July 12, 2010

Insert Iterators

An insert iterator implements its assignment operator to call the container's push_back(), push_front(), or insert() member function.

There are three kinds of insert iterators:
               1) Front Inserter (front_inserter())
               2) Back Inserter (back_inserter())
               3) General Inserter (inserter())
They can be used on containers that have the corresponding member functions (push_front(), push_back(), and insert()).
Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 272.

Saturday, July 10, 2010

Insert Iterators

For an insert iterator, iter, the following are true:
       1. *iter is a no-op that returns iter
       2. iter = value; calls one of push_back(),
                        push_front(), or insert().
       3. iter = value; behaves the same as
          *iter = value; but *iter = value; is 
          the preferred syntax.
Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 272.

Thursday, July 8, 2010

Inserting into a vector

Given a vector v, all of the following do the same thing:
    back_inserter(v) = 42;
    inserter(v, v.end()) = 42;
    v.push_back(42);
Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 272.

Tuesday, July 6, 2010

Iterator Categories

The Output Iterator (output_iterator_tag) category is the only iterator category not related to the other iterator categories by inheritance:
  • Input Iterator (input_iterator_tag)
  • Forward Iterator (forward_iterator_tag)
  • Bidirectional Iterator (bidirectional_iterator_tag)
  • Random Access Iterator (random_access_iterator_tag)
Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 284.

Sunday, July 4, 2010

Struct Inheritance

Structs can inherit from structs. This is how the various interator categories inherit from each other. Structs can also inherit from classes.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 284.

Friday, July 2, 2010

Iterator Traits

The following are iterator traits: value_type, difference_type, iterator_category, pointer, reference.

Reference: The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 285.