
%\noindent\textbf{\large Common STL methods}

\section{Common STL Methods}

\texttt{T} = templated type used in declaration

\texttt{i} = integer, \texttt{b} = boolean, \texttt{c} = char

\texttt{IT} = iterator

%\noindent \textbf{Vector}, \texttt{\#include $<$vector$>$}
\subsection*{Vector, \texttt{\#include $<$vector$>$}}

Iterators are invalidated by inserts/deletes

insertion $\mathcal{O}$(1) at back, $\mathcal{O}$(N) front/middle

  \begin{tabular}{llll}
		\texttt{}    &    \texttt{push\_back (T\&)} &               & \texttt{pop\_back ()} \\
		\texttt{b}   &    \texttt{empty ()}         & \texttt{i}   &  \texttt{size ()} \\
		\texttt{T\&} &    \texttt{back ()}          & \texttt{T\&} & \texttt{front ()}  \\
		\texttt{}    &    \texttt{clear ()}         &                &  \texttt{resize (i)} \\
		\texttt{T\&} &    \texttt{operator[i]}      &               &
  \end{tabular}

%\bigskip
%\noindent \textbf{Map}, \texttt{\#include $<$map$>$}
\subsection*{Map, \texttt{\#include $<$map$>$}}

Iterators are \textsl{not} invalidated by inserts/deletes

insertion $\mathcal{O}$($\lg$ N)

\texttt{K} = key type, \texttt{V} = data type;
\texttt{map$<$K, V$>$}

  \begin{tabular}{llll}
		\texttt{b}   &    \texttt{empty ()}         & \texttt{i}   &  \texttt{size ()} \\
		\texttt{}    &    \texttt{clear ()}         &                &  \texttt{insert (pair$<$K,V$>$)} \\
		\texttt{V\&} &    \texttt{operator[\&K]}      &               & \texttt{erase (IT)} \\
		\texttt{IT} &    \texttt{find (\&K)}          &  &   
  \end{tabular}

\noindent Warning: \texttt{operator[\&K]}  will insert an element into the map if
\texttt{K} is not already present.  The value returned will be the default
constructor for \texttt{V}.

Iterators for map point to \texttt{pair$<$K,V$>$}.

%\bigskip
%\noindent \textbf{List}, \texttt{\#include $<$list$>$}
\subsection*{List, \texttt{\#include $<$list$>$}}

Iterators are \textsl{not} invalidated by insertion/deletion.

insertion $\mathcal{O}$(1) at front/back.  $\mathcal{O}$(N) middle

  \begin{tabular}{llll}
		 &    \texttt{push\_back (T\&)}      &               & \texttt{push\_front (T\&)} \\
		 &    \texttt{pop\_back (T\&)}      &               & \texttt{pop\_front (T\&)} \\
		\texttt{T\&}   &    \texttt{back ()}         & \texttt{T\&}   &  \texttt{front ()} \\
		\texttt{b}   &    \texttt{empty ()}         & \texttt{i}   &  \texttt{size ()} \\
    	        &	\texttt{clear ()}      &            & \texttt{insert (IT, \&T)}\\
		&       \texttt{erase (IT)}    &            & \texttt{unique ()}  \\
		&       \texttt{sort ()}            &       & \texttt{reverse ()} 
  \end{tabular}

Note that list supports \texttt{unique ()}, \texttt{sort ()}
and \texttt{reverse ()} as \textsl{member functions}.  These
versions are specialized to lists and should be used instead
of the more generic versions found in the STL.



%\bigskip
%\noindent \textbf{Deque}, \texttt{\#include $<$deque$>$}
\subsection*{Deque, \texttt{\#include $<$deque$>$}}

insertion $\mathcal{O}$(1) at front/back.  $\mathcal{O}$(N) middle

  \begin{tabular}{llll}
   \texttt{   } & \texttt{push\_back (T\&)}    &  \texttt{push\_front (T\&)} \\
   \texttt{   } & \texttt{pop\_back ()}        &  \texttt{pop\_front ()} \\
   \texttt{T\&} & \texttt{back ()}             &  \texttt{T\& front ()}  \\
   \texttt{b  } & \texttt{empty ()}            &  \texttt{clear ()} \\
   \texttt{i  } & \texttt{size ()}             &  \texttt{resize (i)} \\
   \texttt{T\&} & \texttt{operator[i]}         &
  \end{tabular}

\bigskip
\noindent\textbf{stack} Supports
\texttt{push}
\texttt{pop}
\texttt{size}
\texttt{empty}
\texttt{top}

%  \begin{tabular}{ll}
%    \texttt{push (T\&)}   & \texttt{pop ()} \\
%    \texttt{T\& top ()}  &  \\
%    \texttt{b empty ()} &  \texttt{i size ()}
%  \end{tabular}


\smallskip
\noindent\textbf{queue} Supports
\texttt{push}
\texttt{pop}
\texttt{size}
\texttt{empty}
\texttt{front}
\texttt{back}

%  \begin{tabular}{ll}
%    \texttt{push (T\&)}   & \texttt{pop ()} \\
%    \texttt{T\& front ()}  &  \texttt{T\& back ()}\\
%    \texttt{b empty ()} &  \texttt{i size ()}
%  \end{tabular}



\input{strings}

%%\bigskip
%%\noindent\textbf{Generic Algorithms}, \texttt{\#include $<$algorithm$>$}

%%Generic algorithms work on ranges of iterators;
%%\texttt{BIT} = beginning iterator, \texttt{EIT} = end iterator.
%%\texttt{BIT} is included, but \texttt{EIT} is not.



%%% Local Variables:
%%% mode: latex
%%% TeX-master: "ref-doc"
%%% End:
