Sections
Goal: To know how and when to use C++ containers
Vectors
Vectors are containers used to store an unknown number of elements.
In other languages, vectors are also known as flexible arrays.
Vectors allow elements to be added or removed at any given time.
This means that the size of a vector can change.
Elements in a vector have indexes and can be accessed like an array.
Vectors can be used if the <vector> library is included.
Typically, arrays are used over vectors whenever possible.
Vectors are only used when the size of an array will change frequently.
Info on vectors and their member functions can be found
here:
Example Code:
<span id="L1" class="line"><span class="cp">#include <iostream> // cin, cout</span></span>
<span id="L2" class="line"><span class="cp">#include <vector> // vector container</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span></span>
<span id="L5" class="line"></span>
<span id="L6" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span></span>
<span id="L7" class="line"> <span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">vec</span><span class="p">;</span> <span class="c1">// initializes a vector of integers</span></span>
<span id="L8" class="line"> <span class="kt">int</span> <span class="n">temp</span><span class="p">;</span> <span class="c1">// used for vector.push_back</span></span>
<span id="L9" class="line"></span>
<span id="L10" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Add some numbers to the vector"</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L11" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Enter 0 to stop entering numbers"</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L12" class="line"> <span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L13" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">temp</span><span class="p">;</span> <span class="c1">// gets user input</span></span>
<span id="L14" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">temp</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// if 0 is inputted, the loop breaks</span></span>
<span id="L15" class="line"> <span class="k">break</span><span class="p">;</span></span>
<span id="L16" class="line"> <span class="p">}</span></span>
<span id="L17" class="line"> <span class="n">vec</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">temp</span><span class="p">);</span> <span class="c1">// adds an element to the end of the vector</span></span>
<span id="L18" class="line"> <span class="p">}</span></span>
<span id="L19" class="line"></span>
<span id="L20" class="line"> <span class="c1">// vec.size returns the size of the vector</span></span>
<span id="L21" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Your vector has "</span> <span class="o"><<</span> <span class="n">vec</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o"><<</span> <span class="s">" elements: "</span><span class="p">;</span></span>
<span id="L22" class="line"> <span class="c1">// lists all elements in the vector</span></span>
<span id="L23" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><</span><span class="n">vec</span><span class="p">.</span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">){</span></span>
<span id="L24" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="n">vec</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o"><<</span> <span class="s">" "</span><span class="p">;</span> <span class="c1">// elements in a vector have indexes too.</span></span>
<span id="L25" class="line"> <span class="p">}</span></span>
<span id="L26" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L27" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L28" class="line"><span class="p">}</span></span>Sample run:
>>> Add some numbers to the vector .. Enter 0 to stop entering numbers 2 3 4 5 6 0 >>> Your vector has 5 elements: 2 3 4 5 6
Queues (First-in, First-out)
Queues are containers used to store an unknown number of elements. The
first element that is added to a queue will always be the first
element to be removed from a queue. The last element that is added to
a queue will be the last element to be removed. Queues do not allow
every element to be accessed, only the first and the last element in a
queue. They are often used to simulate queues and lines in real life.
Queues can be used if the <queue> library is included.
More info on queues and their member functions can be found here:
Example Code:
<span id="L1" class="line"><span class="cp">#include <iostream> // cin, cout</span></span>
<span id="L2" class="line"><span class="cp">#include <queue> // queue container</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span></span>
<span id="L5" class="line"></span>
<span id="L6" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span></span>
<span id="L7" class="line"> <span class="n">queue</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">line</span><span class="p">;</span> <span class="c1">// initializes queue of integers</span></span>
<span id="L8" class="line"> <span class="kt">int</span> <span class="n">temp</span><span class="p">;</span> <span class="c1">// variable for user input</span></span>
<span id="L9" class="line"></span>
<span id="L10" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"How many numbers are in the queue?"</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L11" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">temp</span><span class="p">;</span></span>
<span id="L12" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><</span><span class="n">temp</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L13" class="line"> <span class="n">line</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">i</span><span class="p">);</span> <span class="c1">// adds an element to the back of the queue</span></span>
<span id="L14" class="line"> <span class="p">}</span></span>
<span id="L15" class="line"></span>
<span id="L16" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"How many numbers will leave the queue?"</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L17" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">temp</span><span class="p">;</span></span>
<span id="L18" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><</span><span class="n">temp</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L19" class="line"> <span class="n">line</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="c1">// removes an element from the front of the queue</span></span>
<span id="L20" class="line"> <span class="p">}</span></span>
<span id="L21" class="line"></span>
<span id="L22" class="line"> <span class="c1">// line.size returns the size of the queue</span></span>
<span id="L23" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"The queue has "</span> <span class="o"><<</span> <span class="n">line</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o"><<</span> <span class="s">" elements."</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L24" class="line"></span>
<span id="L25" class="line"> <span class="c1">// line.front and line.back returns the first and last element</span></span>
<span id="L26" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"The first element is "</span> <span class="o"><<</span> <span class="n">line</span><span class="p">.</span><span class="n">front</span><span class="p">()</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L27" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"The last element is "</span> <span class="o"><<</span> <span class="n">line</span><span class="p">.</span><span class="n">back</span><span class="p">()</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L28" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L29" class="line"><span class="p">}</span></span>Sample Run:
>>> How many numbers are in the queue? 8 >>> How many numbers will leave the queue? 5 >>> The queue has 3 elements. .. The first element is 5 .. The last element is 7
Stacks (Last-in, First-out)
Stacks are containers used to store an unknown number of elements. The
first element that is added to a stack will be the last element to
be removed from a stack, and the last element that is added to a stack
will be the first element to be removed. Only the top element in a
stack can be accessed. Stacks can be used if the <stack> library is
included. More info on stacks and their member functions can be found
here:
Example Code:
<span id="L1" class="line"><span class="cp">#include <iostream> // cin, cout</span></span>
<span id="L2" class="line"><span class="cp">#include <stack> // stack container</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span></span>
<span id="L5" class="line"></span>
<span id="L6" class="line"><span class="kt">int</span> <span class="nf">main</span> <span class="p">()</span> <span class="p">{</span></span>
<span id="L7" class="line"> <span class="n">stack</span><span class="o"><</span><span class="kt">int</span><span class="o">></span> <span class="n">myStack</span><span class="p">;</span> <span class="c1">// initializes a stack</span></span>
<span id="L8" class="line"> <span class="kt">int</span> <span class="n">temp</span><span class="p">;</span> <span class="c1">// variable for user input</span></span>
<span id="L9" class="line"></span>
<span id="L10" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Type in a number to add it to the stack."</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L11" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Press 0 to pop an element or -1 to exit."</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L12" class="line"> <span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L13" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">temp</span><span class="p">;</span> <span class="c1">// gets user input</span></span>
<span id="L14" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">temp</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L15" class="line"> <span class="k">break</span><span class="p">;</span> <span class="c1">// exit user input</span></span>
<span id="L16" class="line"> <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">temp</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span></span>
<span id="L17" class="line"> <span class="n">myStack</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> <span class="c1">// removes the top element of a stack</span></span>
<span id="L18" class="line"> <span class="p">}</span> <span class="k">else</span> <span class="p">{</span></span>
<span id="L19" class="line"> <span class="n">myStack</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">temp</span><span class="p">);</span> <span class="c1">// adds element to the top of the stack</span></span>
<span id="L20" class="line"> <span class="p">}</span></span>
<span id="L21" class="line"> <span class="p">}</span></span>
<span id="L22" class="line"></span>
<span id="L23" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Your stack has "</span> <span class="o"><<</span> <span class="n">myStack</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o"><<</span> <span class="s">" elements."</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L24" class="line"> <span class="c1">// myStack.top returns the element on the top of the stack</span></span>
<span id="L25" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"The element on the top of the stack is "</span> <span class="o"><<</span> <span class="n">myStack</span><span class="p">.</span><span class="n">top</span><span class="p">();</span></span>
<span id="L26" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L27" class="line"><span class="p">}</span></span>Sample Run:
>>> Type in a number to add it to the stack. .. Press 0 to pop an element or -1 to exit. 3 4 6 0 2 3 0 0 0 8 -1 >>> Your stack has 2 elements. .. The element on the top of the stack is 8
Pair
Pairs are used to store two data values. They are often used in
conjunction with other containers such as arrays or vectors. A frequent
scenario that uses pairs is coordinates. In that scenario, an array of
coordinates can be made with pairs. Pairs can be used if the <utility>
library is included. More info on pairs and their member functions can
be found here:
Example Code:
<span id="L1" class="line"><span class="cp">#include <iostream> // cin, cout</span></span>
<span id="L2" class="line"><span class="cp">#include <utility> // stack container</span></span>
<span id="L3" class="line"><span class="cp">#include <string> // string container</span></span>
<span id="L4" class="line"><span class="c1">// this program stores the titles and ratings of shows</span></span>
<span id="L5" class="line"></span>
<span id="L6" class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span></span>
<span id="L7" class="line"></span>
<span id="L8" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span></span>
<span id="L9" class="line"> <span class="kt">int</span> <span class="n">numShows</span><span class="p">;</span> <span class="c1">// variable that stores the number of shows</span></span>
<span id="L10" class="line"> <span class="c1">// Makes an array of pairs. Each pair has a string and an integer</span></span>
<span id="L11" class="line"> <span class="c1">// string is the first data value of pair, integer is the second</span></span>
<span id="L12" class="line"> <span class="n">pair</span><span class="o"><</span><span class="n">string</span><span class="p">,</span> <span class="kt">int</span><span class="o">></span> <span class="n">shows</span><span class="p">[</span><span class="n">numShows</span><span class="p">];</span></span>
<span id="L13" class="line"></span>
<span id="L14" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"How many shows are there? "</span><span class="p">;</span></span>
<span id="L15" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">numShows</span><span class="p">;</span></span>
<span id="L16" class="line"></span>
<span id="L17" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o"><</span><span class="n">numShows</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// for loop for user input</span></span>
<span id="L18" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"What's the show's name: "</span><span class="p">;</span></span>
<span id="L19" class="line"> <span class="n">cin</span><span class="p">.</span><span class="n">ignore</span><span class="p">();</span> <span class="c1">// always put this before getline()</span></span>
<span id="L20" class="line"></span>
<span id="L21" class="line"> <span class="c1">// goes to the ith pair of the array, and stores a string to</span></span>
<span id="L22" class="line"> <span class="c1">// the "first" variable of that pair</span></span>
<span id="L23" class="line"> <span class="n">getline</span><span class="p">(</span><span class="n">cin</span><span class="p">,</span> <span class="n">shows</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">first</span><span class="p">);</span></span>
<span id="L24" class="line"></span>
<span id="L25" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"What's its rating: "</span><span class="p">;</span></span>
<span id="L26" class="line"> <span class="c1">// stores integer in the second variable of the ith pair</span></span>
<span id="L27" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">shows</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">second</span><span class="p">;</span></span>
<span id="L28" class="line"> <span class="p">}</span></span>
<span id="L29" class="line"></span>
<span id="L30" class="line"> <span class="kt">int</span> <span class="n">x</span><span class="p">;</span> <span class="c1">// variable to store the show to be looked at</span></span>
<span id="L31" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"What show do you want to know about?"</span><span class="p">;</span></span>
<span id="L32" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">x</span><span class="p">;</span></span>
<span id="L33" class="line"></span>
<span id="L34" class="line"> <span class="c1">// accesses the value of the (x-1)th pair. Remember that arrays are</span></span>
<span id="L35" class="line"> <span class="c1">// indexed starting with 0</span></span>
<span id="L36" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="n">shows</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">].</span><span class="n">first</span> <span class="o"><<</span> <span class="s">" has a rating of "</span> <span class="o"><<</span> <span class="n">shows</span><span class="p">[</span><span class="n">x</span><span class="o">-</span><span class="mi">1</span><span class="p">].</span><span class="n">second</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L37" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L38" class="line"><span class="p">}</span></span>Sample Run:
How many shows are there? 3 What's the show's name: Bobby the Construction Worker What's its rating: 3 What's the show's name: Doris the Expeditioner What's its rating: 9 What's the show's name: The Magic Garbage Truck What's its rating: 6 What show do you want to know about? 2 Doris the Expeditioner has a rating of 9
Maps
Maps are containers that store corresponding data values. Instead of using an index to refer to a specific data value, it uses another data value. Maps are used whenever a value corresponds to another value. For example, Roman Numerals would use maps because it has a character-integer correspondence (V with 5). That being said, a data value cannot correspond to two or more other data values. Also, if a map receives an index that doesn’t have a corresponding data value, it returns 0 if the corresponding data value should be a an integer or an empty string ("") if the data value should be a string. Maps can be used in a code file if the <map> library is included. More info on maps and their member functions can be found here.
Example Code:
<span id="L1" class="line"><span class="cp">#include <iostream> // cin, cout</span></span>
<span id="L2" class="line"><span class="cp">#include <map> // map container</span></span>
<span id="L3" class="line"><span class="cp">#include <string> // string container</span></span>
<span id="L4" class="line"></span>
<span id="L5" class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span></span>
<span id="L6" class="line"></span>
<span id="L7" class="line"><span class="c1">// map pairs each Canadian province with its two letter abbreviation</span></span>
<span id="L8" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span></span>
<span id="L9" class="line"> <span class="c1">// initializes a map where a string corresponds to another string</span></span>
<span id="L10" class="line"> <span class="n">map</span><span class="o"><</span><span class="n">string</span><span class="p">,</span> <span class="n">string</span><span class="o">></span> <span class="n">provinces</span><span class="p">;</span></span>
<span id="L11" class="line"> <span class="n">provinces</span><span class="p">[</span><span class="s">"AB"</span><span class="p">]</span> <span class="o">=</span> <span class="s">"Alberta"</span><span class="p">;</span> <span class="c1">// gives value for each element</span></span>
<span id="L12" class="line"> <span class="n">provinces</span><span class="p">[</span><span class="s">"BC"</span><span class="p">]</span> <span class="o">=</span> <span class="s">"British Columbia"</span><span class="p">;</span> <span class="c1">// notice how this map has no size</span></span>
<span id="L13" class="line"> <span class="n">provinces</span><span class="p">[</span><span class="s">"MB"</span><span class="p">]</span> <span class="o">=</span> <span class="s">"Manitoba"</span><span class="p">;</span> <span class="c1">// this list could be gigantic</span></span>
<span id="L14" class="line"> <span class="n">provinces</span><span class="p">[</span><span class="s">"NB"</span><span class="p">]</span> <span class="o">=</span> <span class="s">"New Brunswick"</span><span class="p">;</span> <span class="c1">// the list could just continue</span></span>
<span id="L15" class="line"> <span class="n">provinces</span><span class="p">[</span><span class="s">"PE"</span><span class="p">]</span> <span class="o">=</span> <span class="s">"PEI"</span><span class="p">;</span> <span class="c1">// assuming we have much more provinces</span></span>
<span id="L16" class="line"> <span class="c1">// ...This goes on for the remaining 8 provinces/territories</span></span>
<span id="L17" class="line"></span>
<span id="L18" class="line"> <span class="n">string</span> <span class="n">abbreviation</span><span class="p">;</span> <span class="c1">// string for user input</span></span>
<span id="L19" class="line"></span>
<span id="L20" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"Hey! Which province/territory do you live in? "</span><span class="p">;</span></span>
<span id="L21" class="line"> <span class="n">cin</span> <span class="o">>></span> <span class="n">abbreviation</span><span class="p">;</span></span>
<span id="L22" class="line"></span>
<span id="L23" class="line"> <span class="c1">// province[s] would return the string that corresponds with string s</span></span>
<span id="L24" class="line"> <span class="n">cout</span> <span class="o"><<</span> <span class="s">"WOW! You live in "</span> <span class="o"><<</span> <span class="n">provinces</span><span class="p">[</span><span class="n">abbreviation</span><span class="p">]</span> <span class="o"><<</span> <span class="s">"?!?!"</span> <span class="o"><<</span> <span class="n">endl</span><span class="p">;</span></span>
<span id="L25" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L26" class="line"><span class="p">}</span></span>Sample Run 1:
Hey! Which province/territory do you live in? MB WOW! You live in Manitoba?!?!
Sample Run 2:
Hey! Which province/territory do you live in? XX WOW! You live in ?!?!
In Summary
-
A vector is a container that acts like an array, but can change size
-
A queue is a container with a first-in, first-out (FIFO) policy when adding and removing elements
-
A stack is a container with a last-in, first out (LIFO) policy when adding and removing elements
-
A pair is a container that stores two data values
-
A map is a container that gives a one to one correspondence between two data values.