Previous Section
 < Free Open Study > 
Next Section


Containers

The STL provides three kinds of containers: sequence containers, container adapters, and associative containers.

In a sequence container, every item in the container has a position, which depends on the time and place of insertion but not on the item's value. The sequence containers are vector, list, and deque. These containers are sometimes referred to as "first class containers." Each STL container provides a different set of operations that have different tradeoffs in terms of time and space complexity. Selection of a container should be made accordingly. The vector provides random access to its elements, and insertions and deletions at the back (but not in the middle) are very efficient. The C++ Standard suggests that vector is the sequence type that should be used by default. If your program requires frequent insertions and deletions in the middle of a sequence, the list should be used. The deque should be used if frequent insertions and deletions are needed at the beginning and the end of the sequence.

The associative containers are map, multimap, set, and multiset. These containers are based on the concept of an associative array, a data structure that holds pairs of values: a key and a value associated with that key. We discuss associative containers later but do not explore them in detail in this appendix.

The container adapters are queue, stack, and priority_queue. These are called adapters because they use one of the three sequence containers (vector, list, or deque) to actually hold the items and simply present a different interface (stack, queue, or priority queue) to the programmer.

We begin by looking at the sequence containers vector, list, and deque, along with another class provided by the standard library: string.

The vector<T> Class

The vector container provides fast random access into sequences of varying length, as well as fast insertion and deletion at the end of the vector.vector<T> is a template class implemented with a dynamically allocated array that may be used with any type T that is assignable and copyable. This means that if T is a class or struct type, both operator= and a copy constructor must be defined for T.

A vector's behavior is similar to the C++ array, the main difference being that a built-in array is of fixed size that must be known at compile time, whereas the vector automatically expands to accommodate new entries. As with the List ADT from Chapter 3, a vector divides its storage into an initial segment that contains the inserted items and a final segment of unused items called the reserve. Unlike the List ADT, when the reserve is exhausted, the vector allocates new memory space twice of that currently allocated, copies the data to the new memory, then deallocates the old memory space. This operation is called a resize. There is a member function that is available to carry out this operation, but most often it occurs implicitly. This process of allocating more memory is sometimes referred to as reallocation, especially when done implicitly.

We speak of the first position in the vector as the front and the last used position as the back. The vector container supports insertion and deletion at the back of the container in amortized time of O(1). The term amortized time to do a task is a weighted average of two things: the time to do just the primary task (which usually takes a short time and occurs frequently) and the additional time to carry out another associated task (which usually takes considerably longer but occurs infrequently). For the vector, the insertion operation takes a very short time but has high probability. The additional task is to reallocate memory and copy data when the reserve is exhausted, which takes a fairly long time but has a very low probability.

The following are some properties of vector containers:

  • vectors provide random access, either through an unchecked index ([]) or through a range-checked at () member function.

  • vector iterators are random access iterators. Therefore, the behavior is essentially that of C++ pointers. The iterators may be indexed, and pointer arithmetic may be applied. An iterator is of a type defined within class vector<T> and may be declared by writing

    vector<T>::iterator vIter;
    
  • Insertion and deletion can be done in O(1) time at the back of a vector and O(N) time elsewhere.

  • Insertion and deletion invalidate any iterators referring to items beyond the deletion position.

There are two sizes associated with a vector v. One, the value returned by v.size(), is the number of items that have been inserted into the vector. The other, the value returned from v.capacity(), is the number of items inserted plus the number of places in the reserve. In Figure A.2, the capacity is 9, and the size is 4.

 

Inserted items

Reserve

Iterator position

begin()

     

end()

       

Conceptual position

Front

   

Back

         

Index

0

1

2

3

4

5

6

7

8

Value

8

2

34

2

         

Figure A.2: vector memory allocation

The function call v.front() returns the first item in the vector, and v.back() returns the last item. The values stored in the reserve section are inaccessible. The position referred to by v.begin() is the position of index O, which is also from where the v.front() function fetches. The position referred to by v.end()is the one-past-the-end position. It is one beyond the position from where the v.back() function fetches.

To describe the member functions of the vector<T> class, we now present a series of tables along with examples. Please note that we include only a representative sample of the available member functions. For a comprehensive list, you should consult one of the references at the end of the appendix.

Table A.6: vector Constructors and Destructor

vector<T> v;

Default constructor. Creates an empty vector object, v

vector<T> vNew(vOld);

Copy constructor. Creates a vector, vNew, as a copy of another vector, vOld, of the same type. All members are copied

vector<T> v(n);

Creates a vector of size n, with each element constructed by the default constructor for type T

vector<T> v(n, value);

Creates a vector of size n, with each element initialized to value, which is of type T

vector<T> v(first, pastLast);

Creates a vector whose elements are copies of a subrange of another container of any type having the same base type T. The subrange is [first, pastLast)-that is, from the position denoted by the iterator first up to but not including the position denoted by the iterator pastLast

v.~vector<T> ()

Destructor. Deallocates storage for v and invokes destructors (if any) for its elements of type T. Not usually called explicitly; the destructor is called automatically when v goes out of scope

Here is a short program illustrating the uses of several of the constructors.

    // Code to illustrate vector constructors using primitive types and a
    // user-defined type as base types.

    #include <vector>    // For vector<T> class
    #include <cassert>   // For assert() function

    struct node
    {
      node ()
      {
        iValue = 0;
        dValue = 0.0;
      }

      int iValue;
      double dValue;
    };

    int main()
    {
      using namespace std;

      vector<double> doubleVec;     // Empty vector of doubles
      vector<int> intVec(5, 999);   // Vector of 5 int values, each
                                    // initialized to 999
      vector<node> nodeVec(100);    // Vector of 100 nodes, each
                                    // initialized with default
                                    // constructor node()
      assert(doubleVec.size() == 0);
      assert(intVec.size() == 5);
      assert(intVec[0] == 999);
      assert(nodeVec.size() == 100);
      assert(nodeVec[9].iValue == 0);
      assert(nodeVec[9].dValue == 0.0);
        
    }

Table A.7: vector Element Access

v [index]

Indexed access with no range checking. Index range is 0 through v.size() - 1. The expression v [index] may return a value or have a value assigned to it

v.at (index)

Indexed access with range checking. Index range is 0 through v. size() - 1. Throws an out_of_range exception if index v.size (). The expression v.at (index) may return a value or have a value assigned to it

v.front()

Returns the first item in the vector. Same as v[0] or v.at (0)

v.back()

Returns the last item in the vector. Same as v[v. size () - 1]

    // Illustrates use of vector element access

    #include <vector>     // For vector<T> class
    #include <iostream>

    int main ()
    {
      using namespace std;

      const int SIZE = 12;
      int array[SIZE] = {1, 2, 3, 5, 8, 13, 21, 25, 16, 9, 4, 1};
      vector<int> v(12);

      for (int i = 0; i < SIZE; i++)
        v[i] = array[i] ;

      cout << v.at(SIZE);  // Would generate an exception

      for (int i = 0; i < SIZE; i++)  // Or use i <= v.size()
        cout << v.at(i) << end1;

      // Illustrates use of front and back member functions
      cout << v.front() << " same as " << v[0] << end1;
      cout << v.back () << " same as " << v[SIZE - 1] << end1;
    }

Table A.8: vector Member Functions for Insertion

v.push_back(item);

Inserts item onto the back of the vector. (If needed, resize. Store into first reserve location, and adjust internal pointers)

v.insert (iter, item);

Inserts item into the vector before the position denoted by iterator iter. (Copy last item into reserve, resizing if needed. Successively copy items until position denoted by iter is reached. Copy item into position denoted by iter)

v.insert (iter, n, item);

Inserts n copies of item, starting at the position denoted by iter

v.swap (vOther);

Swaps the contents of vectors v and vOther. The vectors must be of the same type. This operation is fast, as only internal pointers are changed

    // Illustrates use of vector member functions for insertion

    #include <vector>     // For vector<T> class
    #include <iostream>

    int main ()
    {
      using namespace std;

      const int SIZE = 12;
      int array[SIZE] = {l, 2, 3, 5, 8, 13, 21, 25, 16, 9, 4, 1};
      vector<int> v(12);
      vector<int> w(12);

      // Give v the items from array using the push_back member
      for (int i = 0; i < SIZE; i++)
        v.push_back(array[i]);

      // Give w the values 0 through SIZE - 1
      for (int i = 0; i < SIZE; i++)
        w.push_back(i);

      // Display v
      for (int i = 0; i < SIZE; i++)
        cout << v[i] << end1;

      // Exchange the identities of v and w
      v.swap(w);
      // and display v, then w
      for (int i = 0; i < SIZE; i++)
        cout << v[i] << end1;

      for (int i = 0; i < SIZE; i++)
        cout << v[i] << end1;
    }
Table A.9: vector Member Functions for Item Removal

v.pop_back ();

Removes the last item from v. (This only changes internal pointers)

v.erase (iter);

Removes the item at the position denoted by iter. (Copies data from the position following the one denoted by iter to the position denoted by iter, then copies successively until the last item is copied. Internal pointers are adjusted)

v.erase(first, pastLast);

Removes all items in the range [first, pastLast]

Table A.10: vector Member Functions Related to Size

v.empty()

Returns true if v contains no items, else returns false

v.size()

Returns the number of items currently in v

v.capacity()

Returns number of items in container + number of available positions in reserve memory

v.reserve (n);

Increases container capacity to n

v.resize(n, value);

if (n > v.size())
  v.insert(v.end(), n - v.size(), value);
else if (n < v.size())
  v.erase(v.begin() + n, v.end());

Reallocation invalidates all references, pointers, and iterators into a vector that were set prior to reallocation, because those iterator values all point into the old (previously allocated) memory. It is guaranteed that no reallocation takes place for insertions that take place after a call to reserve() until the vector reaches a size specified in the call to reserve().

Table A.11: vector Member Functions Related to Iterators

vector<T>:: iterator itr;

Creates a random access iterator for a vector<T>

vector<T>:: reverse_iterator itr;

Creates a (random access) reverse iterator for a vector<T>

v.begin()

Returns a random access iterator value denoting the position of the first item

v.end ()

Returns a random access iterator value denoting the position of the imaginary past-the-end item

v.rbegin ()

Returns a reverse iterator value denoting the position of the first item of a reverse iteration (i.e., the last item in the container)

v.rend ()

Returns a reverse iterator value denoting the position of the imaginary past-the-end item of a reverse iteration (i.e., the imaginary before-the-first item in the container)

Before we look at the next sequence container, list, we examine the string class, which is somewhat similar to vector<char> but has member functions and optimizations more appropriate to character strings.

The string Class

This section presents the string class from the C++ standard library. Although string is not part of the STL, it is an integral part of the standard library. A knowledge of the string class is essential in a programmer's toolbox.

The standard library defines a class char_traits that defines properties of ordinary characters (type char) and wide characters (type wchar_t, which is the wide [16-bit] character type in which the Unicode character set is encoded). Although the C++ Standard deals with character traits, we do not in this appendix. We deal only with the simpler situation in which the character type is char.

The word string can be a source of confusion in Standard C++. By string, do we mean the strings that are inherited from the C language-namely, null-terminated char arrays? Or do we mean Standard C++ string class objects? To help remove some of this ambiguity, we will consistently use string to refer only to the class string. In contrast, we use the term cstring to refer to the kind of strings that C++ inherits from C (null-terminated char arrays). We do so partly because the header file that provides functions that manipulate C-style strings is the file <cstring>, and partly because cstrings are inherited from the C language.

Standard C++ provides two string types, string and wstring. The names are created by two typedef statements that specialize the template class basic_string:

    typedef basic_string<char> string;     // Usual string using ASCII
                                           // characters
    typedef basic_string<wchar_t> wstring; // Wide character string

We mention this fact so that you might better understand compiler error messages that mention basic_string. Also, you may need to deal with wide character strings (type wstring) at some time in the future. We do not discuss wstring any further in this appendix.

We begin our discussion of the string class by presenting a program that uses both vector and string. The program reads a line from standard input, splits the line into words, and then outputs the words in reverse order from which they appeared in the input. First we present the program, and then we explain the details.

    #include <iostream>
    #include <string>     // For string class
    #include <vector>     // For vector<T> class

    using std::string;
    using std::vector;

    void parse(string& line, string& delimiters, vector<string>& strVec)
    // Action: Splits line into words using delimiters,
    //         returns words in strVec
    // Pre:  line and delimiters have been initialized,
    //         and strVec is empty
    // Post: strVec contains the words
    {
      using namespace std;
      int lineLength = line.length();
      int wordPastEnd;
      int wordStart = line.find_first_not_of(delimiters, 0);

      while ( wordStart >= 0 && wordStart < lineLength )
      {
       wordPastEnd = line.find_first_of(delimiters, wordStart);

       if (wordPastEnd < 0 || wordPastEnd > lineLength)
         wordPastEnd = lineLength;

       strVec.push_back(line.substr(wordStart, wordPastEnd - wordStart));

       // Find first character not in the delimiter list after the 2nd arg
       wordStart = line.find_first_not_of(delimiters, wordPastEnd + 1);
      }
    }

    int main()
    {
      using namespace std;
      string line;
      string delimiters(" ,.?!:;");
      vector<string> wordVec;

      getline(cin, line, '\n');
      parse(line, delimiters, wordVec);

      vector<string>::iterator itr;

      // Output words in the order that the words appear in wordVec
      for (itr = wordVec.begin(); itr < wordVec.end(); itr++)
        cout << *itr << end1;

      // Output words in the reverse order that they appear in wordVec
      vector<string>::reverse_iterator revItr;
      for (revItr = wordVec.rbegin(); revItr < wordVec.rend(); revItr++)
        cout << *revItr << end1;
    }

Given the input

    Now is the time for

the program produces this output:

    Now
    is
    the
    time
    for
    for
    time
    the
    is
    Now

The main function declares the string object line to hold the input from the keyboard, and the string object delimiters holds the separator characters space, comma, period, question mark, exclamation mark, colon, and semicolon. The getline stand-alone function, available through the header file <string>, has prototype

    ostream& getline( istream& is, string str, char delim);

The effect of getline is to extract characters from the input stream is until one of the following occurs: the end of file on the stream is encountered, the delimiter character is extracted from the input stream, or str.max_size() characters have been extracted. The value str.max size() is the size of the largest possible string container. The value is implementation dependent but is about 4 x 109 for a typical 32-bit C++ implementation.

The function with signature

    void parse(string& line, string& delimiters,
               vector<string>& strVec);

is called to split line into words separated by characters from the string delimiters. The parse function uses the string member function find_first_of, which returns an int value that is the index of the first character in line that matches any character of the delimiter string. Similarly, find_first_not_of returns the int value that is the index of the first character in line that is not in the delimiter string. These two numbers are used to locate the start and past-the-end indexes of successive words. Successive substrings are extracted from line using the substr member function and are inserted at the end of strVec using the push_back member function of vector.

Back in the main function, when control returns from the parse function, the argument wordVec contains the successive substrings of line. The successive strings are extracted first to last by use of a vector<string> iterator. A vector iterator is declared, then initialized in a for statement to the location of the front item in wordVec that is returned by the begin() member function. The iterator's referent is output, and the iterator is stepped forward with the ++ operator and compared to the past-the-end value obtained from the end() member function. The result is to display the substrings from line in front to back order.

Next, the strings in strVec are output last to first. An iterator of type vector<string>::reverse_iterator is declared and then initialized in a second for statement to a reverse iterator value that refers to the last item in wordVec by means of the rbegin() member function. The iterator's referent is output. Then the iterator is stepped forward with the ++ operator. (The operator ++ is overloaded to move the iterator's position toward the front of the list.) Then the iterator is compared to an iterator value obtained from the rend() member function. This value behaves as if it were a "before-the-first" position, enabling the iteration from back to front to terminate. The result is that the substrings from line are displayed in reverse order.

In this example, we have used the following features of string and vector:

  • The use of vector with string as a base type

  • The getline function for strings

  • The string member functions find_first_of, find_first_not_of, length, and substr

  • The use of the type vector<T>::iterator

  • The use of the type vector<T>::reverse_iterator

Now let's look in more detail at the string class. Figure A.3 depicts a string that contains the characters in "Bill" and has a size of 4 and a capacity of 9. The string class has members begin () and end () that return iterator values denoting the front and past-the-end positions of the string. A difference between vector and string is that the vector members front() and back () are missing from string. On the other hand, string has several useful search members that, if needed in a vector, must be imitated by generic "find" and "conditional find" STL algorithms.

 

Inserted items

Reserve

Iterator position

begin()

     

end()

       

Index

0

1

2

3

4

5

6

7

8

Value

'B'

'i'

'|'

'|'

         

Figure A.3: string memory allocation

As we did with the vector<T> class, we now present a series of tables describing many (but not all) of the available string member functions, interspersed with remarks.

Table A.12: string Constructors and Destructor

string s ;

Default constructor. Creates an empty string

string s(str) ;

Copy constructor. Creates a new string s as a copy of another string, str

string s(str, indx) ;

Creates a new string s from characters starting at index indx of str

string s(str, indx, count) ;

Creates a new string s initialized by at most count characters from str, starting at index indx in str

string s (cstr) ;

Creates a new string s initialized with characters from the cstring cstr

string s(charArray, count) ;

Creates a new string s initialized with at most count characters from char array charArray

string s (count, ch) ;

Creates a new string s initialized with count instances of character ch

string s(first, pastLast) ;

Creates a new string s initialized with characters in the iterator range [first, pastLast) of any char container

s.~string();

Destructor. Frees the memory allocated to string s

Here is a short code segment demonstrating some of the string constructors.

    std::string s0("string"); // Create string s0 containing
                              // 's' 't' 'r' 'i' 'n' 'g'
    std::string s1;           // Create empty string s1
    std::string s2(s0);       // Create string s2 with characters from s0
    std::string s3(s0, 3);    // Create string s3 with the characters
                              // starting at index 3 from s0: characters
                              // 'i', 'n' 'g'
    char x[] = "string";      // Create a cstring
    std::string s4(x, x+3);   // Create s4 as a string with 's' 't' 'r'
        // x and x + 3 are pointers into cstring x. Pointers behave as
        // random access iterators.
Table A.13: string Element Access

s[i]

Indexed access with no range checking. Character at index i may be fetched or stored

s.at(i)

Indexed access with range checking. Character at index i may be fetched or stored. Throws an out_of_range exception if i s.size ()

s.c_str()

Returns a pointer (type const char *) to a cstring representing the data in string s. The cstring is terminated by a null character (' \0')

s.data()

Returns a pointer (type const char *) to s [0]. Warning: The pointed-to sequence should not be treated as a cstring because it is not guaranteed to be terminated by a null character ('\0')

Table A.14: string Member Functions Related to Size

s.length ()

Returns the number of characters currently in s

s.size ()

Same as s.length()

s.resize (newSize, padChar);

Changes the size of s to newSize, filling with repetitions of the character padChar if necessary

s.empty ()

Returns true if s is empty, else returns false

s.capacity ()

Returns the number of characters that s can contain without having to reallocate (i.e., number of characters in reserve + size of s)

Table A.15: string Member Functions for Searching and Substrings

s.find (str)

Returns the integer index of the first position of the first occurrence of string str in s

s.find(str, pos)

Returns the integer index of the first position of the first occurrence of string str in s, with the search starting at position pos of s

s.find_first_of (delim, pos)

Returns the integer index of the first position of the first occurrence of any character from the string delim, with the search starting at position pos of s

s.find_first_not_of (delim, pos)

Returns the integer index of the first position of the first occurrence of any character not in the string delim, with the search starting at position pos of s

s.substr (pos, len)

Returns a string object that represents a substring of s of at most len characters, starting at position pos of s. If len is too large, it means "to the end" of string s. If pos is too large, an out_of_range exception is thrown

Note: If any version of find fails to find the search value, the function's return value is the constant string::npos, which is the largest possible value of type string::size_type, an unsigned integer type defined by the string class.

Table A.16: string Comparisons

s1 == s2

Returns true if all characters of s1 and s2 are pairwise equal, else returns false

s1 != s2

Returns true if not all characters of s1 and s2 are pairwise equal, else returns false

s1 < s2

Returns true if s1 comes before s2 lexicographically, else returns false

s1 > s2

Returns true if s1 comes after s2 lexicographically, else returns false

s1 <= s2

Same as ! (s1 > s2)

s1 >= s2

Same as ! (s1 < s2)

Lexicographic ordering compares characters at corresponding positions sequentially until a position i is found where sl[i] s2[i]. Then the expression s1 < s2 has the same Boolean value as s1 [i] < s2 [i].

Table A.17: string I/O Operations

This table assumes the following declarations:

  ostream os;
  istream is;

os << str

Places characters from string str onto stream os

is >> str

Extracts characters from stream is into string str. Leading whitespace characters are skipped, and input stops at the first trailing whitespace character

getline(is, str, delimiter)

Reads characters from stream is into string str up to end-of-file or until the character delimiter is extracted. The delimiter is removed from is and discarded. Note: getline is not a member function of the string class. It is a stand-alone, global function

The list<T> Class

The list is the second of the three STL sequence containers. A list is a sequential access container that is optimized for insertions and deletions anywhere in the list. Although the C++ Standard does not require any particular implementation, the requirements of fast insertion and deletion and support for bidirectional iterators, together with the lack of a requirement of random access, suggest that the implementation be a doubly linked list.

To create an object of type list<T>, the data type T must be assignable and copyable. That is, if T is a class or struct type, both operator= and a copy constructor must be defined for T.

The following are some properties of list containers:

  • lists provide sequential access, so there is no indexed access and no at() member

  • Iterators are bidirectional

  • Insertion and deletion can be done in O(1) time at any location in the list.

  • Insertion and deletion do not invalidate iterators referring to items not involved in the deletion.

  • There are many member functions that do the same task that external STL algorithms do, but they are faster for lists, because internal pointers are changed instead of data being moved.

  • The list provides the best exception safety in that more of its operations either succeed or have no effect than in other containers

As we have done with vector and string, we now present a series of tables detailing many (but not all) of the list member functions.

Reminder: The iterator range [first, pastLast) refers to the container position denoted by first up to but not including the position denoted by pastLast.

Table A.18: list Constructors and Destructor

list<T> lst;

Default constructor. Creates 1st as an empty list

list<T> lst (oldList);

Copy constructor. Creates 1st as a copy of oldList

list<T> lst (count);

Creates a list of count items, each constructed by the default constructor for type T

list<T> lst(count, typeTobj);

Creates a list of count items, each one a copy of typeTobj, an object of type T

list<T> lst(first, pastLast);

Creates a list initialized with type T objects from the range [first, pastLast) in another container

1st.~list<T>() ;

Destructor. Frees the memory allocated to 1st

A list does not provide random access. In addition to dereferencing iterators, list elements are accessed through the member functions front() and back().

Table A.19: list Element Access

1st.front()

Returns the first item in the list

lst.back()

Returns the last item in the list

Table A.20 describes list insertion and deletion operations. Note that class list<T> provides member functions for deletion, but there is also a generic STL algorithm for this purpose. However, a member function is preferred to the algorithm because it changes internal pointers instead of moving data, so it is likely to be faster.

Table A.20: list Member Functions for Insertion and Removal

1st.insert (iter, item)

Inserts item into the list before the position denoted by iter. Returns an iterator value that points to the inserted item

1st.insert (iter, count, item);

Inserts count copies of item into the list before the position denoted by iter. The return type is void

1st.push_front (item);

Inserts item at the front of the list

lst.push_back (item);

Appends item to the back of the list

1st.pop_back();

Removes the item at the back of the list

1st.pop_front();

Removes the item at the front of the list

1st.remove (item);

Removes all list elements equal to item

1st.remove_if (pred);

Removes all items for which the predicate pred returns true. The argument pred can be either the name of a Boolean function or a function object (defined later in this appendix)

lst.erase (iter)

Removes the item at the position denoted by iter. Returns an iterator value that points to the next item

1st.erase (first, pastLast)

Removes all items in the range [first, pastLast). Returns an iterator value that points to the next item

1st.clear ();

Removes all items in the list

Table A.21: list Assignment and Swap Operations

1st1 = 1st2;

After removing all items in lst1, copies all items from list lst2 to lst1

1st.assign (first, pastLast);

After removing all items in 1st, copies to 1st all items in the range [first, pastLast) from another container of type T objects

lstl.swap (lst2);

Swaps the contents of lists lst1 and lst2

Table A.22: list Member Functions Related to Iterators

list<T>::iterator itr;

Creates a bidirectional iterator for a list<T>

list<T>::reverse_iterator itr:

Creates a (bidirectional) reverse iterator for a list<T>

1st.begin ()

Returns a bidirectional iterator value denoting the position of the first item

1st.end ()

Returns a bidirectional iterator value denoting the past-the-end position

1st. rbegin()

Returns a reverse iterator value denoting the position of the first item of a reverse iteration (i.e., the last item in the container)

1st.rend()

Returns a reverse iterator value denoting the past-the-end position of a reverse iteration (i.e., the before-the-first position in the container)

Table A.23: list Member Functions Related to Size and Comparisons

1st.empty ()

Returns true if 1st contains no items. Returns same result as lst.size () == 0, but lst.empty () might be faster

1st.size ()

Returns the number of items currently in the list

lst.resize(newSize);

If newSize > lst.size(), then append newSize - 1st.size() instances of a default-constructed type T object to the end of the list.

Otherwise, if newSize < 1st.size (), erase the last lst.size() - newsize items from the list, else do nothing.

lst.resize(newSize, typeTobj);

If newSize > lst.size(), then append newSize - lst.size() copies of typeTobj to the end of the list.

Otherwise, if newSize < 1st.size(), erase the last lst.size() -newSize items from the list, else do nothing.

lst1 == lst2

Returns true if the lists have the same number of items and contain the same items in the same order, else returns false

lstl < lst2

lstl > lst2

lstl <= lst2

lstl >= lst2

Comparisons are in lexicographic order. (Successive pairs of items are compared. The order of the first unequal pair determines which order relations return true)

Table A.24: Operations That Modify lists

lst1.splice(iter, lst2);

Requirement: &lst1 &lst2

Effect: Inserts the contents of lst2 into lst1 before the position in lst1 denoted by iter, and lst2 becomes empty

lst1.splice (position, lst2, iter);

Removes the item at the position denoted by iter in lst2 and inserts it before the position denoted by position in lst1.

lst1.splice (position, lst2, first, pastLast);

Requirement: If &lst1 = &lst2, position must not be in the range [first, pastLast)

Effect: Removes all items in the range [first, pastLast) of lst2 and inserts them before the position denoted by position in lst1

lst.sort();

Sorts the list items into ascending order using the < operator to compare items

lst.sort (cmp);

Sorts the list items using the comparison function cmp, which can be either the name of a Boolean function or a function object (defined later in this appendix)

lst1.merge (lst2);

Requirement: The items in both lists are in sorted order (ordered by the < operator)

Effect: Removes all items from lst2 and merges them into lst1 so that lst1 is still sorted

lst1.merge (lst2, cmp);

Requirement: The items in both lists are in sorted order (ordered by the cmp function). The comparison function cmp can be either the name of a Boolean function or a function object (defined later in this appendix)

Effect: Removes all items from lst2 and merges them into lst1 so that lst1 is still sorted

lst.unique ();

Removes all but the first in any sequence of consecutive items that are equal (satisfy the == relation)

lst.unique (cmp);

Removes all but the first in any sequence of consecutive items that satisfy the comparison function cmp, which can be either the name of a Boolean function or a function object (defined later in this appendix)

lst.reverse();

Reverses the order of the items in 1st

The deque<T> Class

The third of the three STL sequence containers is the deque. The word deque (pronounced "deck," "deek," or "dee queue") is short for double-ended queue. The deque container, like the vector, provides fast random access into sequences of varying length. Unlike the vector, the deque provides fast insertion and deletion at both ends of the collection. This is accomplished by providing unused reserve not only at the start of the deque, as does the vector, but also at the end of the container.

The following are the primary differences between the deque and the vector:

  • Insertion into a deque is fast (amortized time 0(1)) at the front as well as the back. The vector is fast only at the back.

  • Memory allocated to a vector is typically contiguous (that is, a built-in array), so vector iterators are usually C++ pointers. Memory allocated to a deque is not guaranteed to be contiguous, so iterators typically are implemented as class objects that mimic pointers. Therefore, accessing items in a deque tends to be slower than accessing items in a vector.

  • Unlike the vector, no member functions are provided in the deque to control reallocation or capacity, so any insertion or deletion other than at the ends invalidates all iterators to the deque.

When should you choose a deque over a vector? If you require random access and frequent insertions at the front and the back, then the deque is the better structure.

Table A.25 displays a representative sample of the deque member functions.

Table A.25: deque Member Functions

Constructors, Assignment, and Swap Operations

deque<T> d;

Default constructor. Creates an empty deque object, d

deque<T> d (otherDeque);

Copy constructor. Creates a new deque d as a copy of otherDeque

deque<T> d(count);

Creates a deque of count items, each constructed by the default constructor for type T

deque<T> d (count, typeTobj );

Creates a deque of count items, each being a copy of typeTobj, an object of type T

d = otherDeque;

After removing all items from deque d, copies all items from otherDeque to d

d. swap (otherDeque);

Swaps the contents of d and otherDeque

Element Access and Insertion Operations

d [index]

Indexed access with no range checking. The element at index index may be fetched or stored

d. at (index)

Indexed access with range checking. Throws an out_of_range exception if index d.size ( )

d.front ()

Returns the first item in the container. Same as d [0]

d.back()

Returns the last item in the container. Same as d[d.size() - 1]

d.insert (iter, item);

Inserts item before the position denoted by iter. Returns an iterator value that points to the inserted item

d.insert (iter, first, pastLast);

Inserts before the position denoted by iter all items in the range [first, pastLast) from another container holding objects of type T

d.push_front (item);

Inserts item at the front of the deque

d.push_back (item);

Inserts item at the back of the deque

Deletion Operations

d.pop_front();

Removes the item at the front of the deque

d.pop_back();

Removes the item at the back of the deque

d.erase(iter)

Removes the item at the position denoted by iter. Returns an iterator value that points to the next item

d.erase(first, pastLast)

Removes all items in the range [first, pastLast). Returns an iterator value that points to the next item

d.clear();

Removes all items in the deque

Size-Related Operations

d.size()

Returns the number of items currently in the deque

d.empty()

Returns true if d contains no items. Returns same result as d.size() == 0, but d.empty () might be faster

d.resize(number);

Changes the size to number. If the deque grows, new items are constructed by the default constructor for type T

Iterator-Related Operations

deque<T>::iterator itr;

Creates a random access iterator for a deque<T>

deque<T>::reverse_iterator itr;

Creates a (random access) reverse iterator for a deque<T>

d.begin()

Returns a random access iterator value denoting the position of the first item

d.end()

Returns a random access iterator value denoting the past-the-end position

d.rbegin()

Returns a reverse iterator value denoting the position of the first item of a reverse iteration (i.e., the last item in the container)

d.rend()

Returns a reverse iterator value denoting the past-the-end position of a reverse iteration (i.e., the before-the-first position in the container)

The Container Adapters stack, queue, and priority_queue

An adapter does not directly implement the structures that hold the data items. Rather, it provides a new interface between the user and an existing container. It "adapts" the interface of one of the sequence containers to provide the operations appropriate for a stack or queue.

The stack Adapter Any sequence container that provides members empty(), size(), push_back(), pop_back(), and back() is suitable as a container for the stack container adapter. All three sequence containers-vector<T>, deque<T>, and list<T>-satisfy these requirements. By default, deque<T> is the container used by the stack<T> adapter.

The stack operations shown in Table A.26 are familiar to anyone who has studied this book.

Table A.26: Some stack Member Functions

stack<int> stck;

Default constructor. Uses, by default, a deque<int> to hold items of type int

stack<float, vector<float> > stck;

Default constructor. Uses a vector<float> to hold items of type float. (Note the required space within "> >" to distinguish it from the built-in operator >>)

stack<string, list<string> > stck;

Default constructor. Uses a list<string> to hold items of type string

stack<char, vector<char> > stck(otherStck);

Copy constructor. Initializes stck to be a copy of otherStck, another stack of the same type (i.e., type stack<char, vector<char> >)

stack<char, vector<char> > stck(charVec) ;

Copy constructor. Initializes stck to be a copy of charVec, an object of the underlying container type vector<char>

stck.empty ()

Returns true if stack contains no items. Equivalent to stck.size () == 0 but may be faster

stck.size ()

Returns the number of items currently in the container

stck.push(item);

Pushes a copy of item onto the top of the stack

stck.pop();

Requirement: stck.size() >0

Effect: Removes and discards the top item from the stack. The return type is void

stck.top()

Requirement: stck. size() >0

Effect: Returns the top item on the stack without removing it.

stck1 < stck2

stck1 > stck2

stck1 <= stck2

stck1 >= stck2

stck1 == stck2

stck1 != stck2

Two stacks are equal if they have the same size and all pairs of items are equal. Comparisons are made lexicographically. The first pair of elements that are unequal determines which relational operator returns true

The queue Adapter Any sequence container that has members back(), front(), push_back(), pop_front(), empty(), and size() can be used to hold queue<T> items. In particular, list<T> and deque<T> may be used. By default, deque<T> is the container used by the queue<T> adapter.

Notice in Table A.27 that the STL uses push() instead of enqueue() and pop() instead of dequeue (). Regardless of what we call the operation, we are still dealing with a queue-a FIFO (first-in, first-out) data structure-and push () and pop () mean insert and remove. The structure still returns the oldest item in the structure, just as a queue should.

Table A.27: Some queue Member Functions

queue<int> q;

Default constructor. Uses a deque<int> to hold items of type int. The queue<T> class supports the same variety of constructors shown in Table A.26 for the stack<T> class (except that vector<T> cannot be the underlying container)

q.empty()

Returns true if the queue is empty

q.size()

Returns the number of items in the queue

q.front()

Requirement: q.size() >0

Effect: Returns the first item in the queue

q.back()

Requirement: q. size() >0

Effect: Returns the last item in the queue

q.push(item);

Inserts item at the back of the queue

q.pop();

Requirement: q. size() >0

Effect: Removes and discards the first item from the queue. The return type is void

q1 < q2

q1 > q2

q1 <= q2

q1 >= q2

q1 == q2

q1 != q2

Two queues are equal if they have the same size and all pairs of items are equal. Comparisons are made lexicographically. The first pair of items that are unequal determines which relational operator returns true

The following program demonstrates how to declare and use a queue of string objects, using the default underlying container deque<string> to hold the strings.

    // A queue example using the default (deque) underlying container

    #include <iostream>
    #include <queue>      // For queue<T> class
    #include <string>     // For string class
    #include <deque>      // For deque<T> class

    int main()
    {
      using namespace std;

      deque<string> deq;
      string str;

      // Build a list of words
      cout << "Type some words; 'quit' quits:" << end1 << end1;
      cin >> str;
      while ( string("quit") !=  str )
      {
      deq.push_back(str);
      cin >> str;
      }

      // Create quel by copying from an instance of a deque--the
      // underlying container
      queue<string> quel(deq);

      // Create que2 as a copy of quel
      queue<string> que2(quel);

      cout << "The number of strings entered is " << que1.size() << end1;
      cout << "quel.front() yields: " << que1.front() << endl;
      cout << "que2.back() yields: " << que2.back()  << end1;

      cout << "The strings from quel are: ";
      while ( !que1.empty())
      {
        cout << quel.front() << " ";
        que1.pop() ;
      }
      cout << end1;
      cout << "The strings from que2 are: ";
      while ( !que2.empty())
      {
        cout << que2.front() << " ";
        que2.pop():
      }
      cout << end1;
    }

Execution of this program yields

    Type some words; 'quit' quits:

    now is the time quit

    The number of strings entered is 4
    que1.front() yields: now
    que2.back() yields: time
    The strings from que1 are: now is the time
    The strings from que2 are: now is the time

The priority_queue Adapter A priority_queue, whose declaration is located in the header file <queue>, has operations empty(), size(), push(), pop(), and top(). A priority_queue is like a queue in the sense that push() means enqueue and pop() means dequeue. However, the enqueued items are ordered by the < operator as follows. Whenever push() is called to enqueue an item, the item is inserted at the back of the sequence and then reordering takes place immediately to ensure that the item with the greatest value (the "highest priority") is at the front of the queue. Therefore, the top() operation always returns the highest priority item.

The priority_queue<T> adapter can use any of vector<T>, list<T>, or deque<T> as the underlying container. The default is vector<T>.

The Associative Containers

Earlier we said that the STL provides three kinds of containers: sequence containers, container adapters, and associative containers. We have looked at the first two and now give a brief overview of the third.

The associative containers are based on the concept of an associative array or map, a data structure that holds ordered pairs of the form (key, value). For each key, there is an associated value in the map. The keys can be of one data type, and the associated values can be of another. Here is a code segment that uses the template class map<K, T>, where K means the key type and T means the value type:

    #include <map>    // For map<K, T> class
      
    map<int,float> m;
    m[0] = 36.43;
    m[l] = -15.9;
    m[2] = 0.0;

As you can see, an associative array in which the key values are integers looks very much like an ordinary one-dimensional array. However, look at the following code:

    map<string,int> age;

    age["Mary"] = 18;
    age["Bill"] = 22;

An associative array can be thought of as an array that allows indexes other than integers. By default, the contents of a map are ordered by key values using the < operator, and map iterators step through the container, delivering the items in ascending order of the keys.

The <map> header file declares two container types: map<K, T> and multimap<K, T>. In a map, the keys must be unique; in a multimap, duplicate keys are allowed.

The STL provides two other associative containers, set and multiset, which are available through the header file <set>. The set is an abstraction of a mathematical set. In the context of the STL, it is simply a special case of an associative array in which no value is associated with a key. Hence, the template class set<K> requires only one template parameter-the data type of its keys (hence, the data type of the set elements). The difference between the set and multiset containers is that all elements of a set must be unique (as in a mathematical set), whereas a multiset allows duplicate elements.

Space limitations prevent us from further exploration of the associative containers. For more information, see the references at the end of the appendix.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)