STL (Standard Template Library)

Local

Gotcha's
hash_map
iterator
list
map
queue
Searching: Sorting and Searching
set
Sorting Sorting and Searching
string
Summary
vector
vector, Removing an element
Which container to use

External

Sorting and Searching

Supported by header: <algorithm>

Function	Description
`lower_bound`	This is used to Search
`sort`	Used to sort a container

Reference Articles

http://www.sgi.com/tech/stl/sort.html

Gotcha's

Remember to use the right namespace: using namespace std;

Summary

container	Get	Put	Remove
list	T& front() T& back()	push_front(const T&) push_back(const T&)	remove( const T& val)

list

Reference: http://www.sgi.com/tech/stl/List.html

Function	Description
find	There doesn't seem to be any sort of find method.
`void clear()`	Erases all the elements
`iterator erase( iterator pos)`	Erases the element at pos
`iterator erase( iterator first, iterator last)`	Erases the range [first, last)
`iterator insert(iterator pos, const T& x)`	Inserts x before pos
`void remove( const T& value)`	Removes all elements that compare equal to value. WARNING: Searches all elements, even after finding 1
`void sort();`	Sorts via `operator<(T,T);` ??`operator<(const T, const T);`
`void sort( pfunc);`	Sorts via `bool pfunc(T* v1, T* v2) { return v1 < v2; }`

iterator erase(iterator pos) Sequence Erases the element at position pos. iterator erase(iterator first, iterator last)


list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
// The values that are printed are 1 2 0
int iTemp;
iTemp = L.front();
iTemp = L.back();
L.pop_back();
L.pop_front();

map

Make sure to define a lessThan function, unless you types are basic like int where less than is a standard operation. If you use pointers and don't define a lessThan, it will use the pointers addresses in comparisons, NOT the data that is pointed to.
Accessing elements through iterators is odd as well. They are pairs to get the key use the field first and to get the value use the field second (as shown below)

struct lessThanStr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  map<const char*, int, lessThanStr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "june -> " << months["june"] << endl;
  map<const char*, int, lessThanStr>::iterator cur  = months.find("june");
  map<const char*, int, lessThanStr>::iterator prev = cur;
  map<const char*, int, lessThanStr>::iterator next = cur;    
  ++next;
  --prev;
  cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
  cout << "Next (in alphabetical order) is " << (*next).first << endl;
}

set


struct ltstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) < 0;
  }
};

int main()
{
  const int N = 6;
  const char* a[N] = {"isomer", "ephemeral", "prosaic", 
                      "nugatory", "artichoke", "serif"};
  const char* b[N] = {"flat", "this", "artichoke",
                      "frigate", "prosaic", "isomer"};

  set<const char*, ltstr> A(a, a + N);
  set<const char*, ltstr> B(b, b + N);
  set<const char*, ltstr> C;

  cout << "Set A: ";
  copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
  cout << "Set B: ";
  copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));   
  cout << endl;

  cout << "Union: ";
  set_union(A.begin(), A.end(), B.begin(), B.end(),
            ostream_iterator<const char*>(cout, " "),
            ltstr());   
  cout << endl;

  cout << "Intersection: ";
  set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                   ostream_iterator<const char*>(cout, " "),
                   ltstr());    
  cout << endl;

  set_difference(A.begin(), A.end(), B.begin(), B.end(),
                 inserter(C, C.begin()),
                 ltstr());
  cout << "Set C (difference of A and B): ";
  copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
  cout << endl;
}

Which container to use

type	duplicates	sorted	Key and Value
map	no	yes	yes
set	no	yes	no

queue


#include <queue>

queue<type> q;

type t1;
type t2;
q.push(t1);
q.push(t2);

type ttop;
ttop = q.front();
q.pop();
// ttop is t1
ttop = q.front();
// ttop is t2
q.pop();

// queue is empty

hash_map

!! NOTE !! hash_map is not yet part of the offical released stl, so it should be in the namespace stdext:: and not in the namespace std::


#include <string>
#include <hash_map>
#include <iostream>

// The following class defines a hash function for strings 
class stringhasher : public stdext::hash_compare <std::string>
{
public:
  /**
   * Required by 
   * Inspired by the java.lang.String.hashCode() algorithm 
   * (it's easy to understand, and somewhat processor cache-friendly)
   * @param The string to be hashed
   * @return The hash value of s
   */
  size_t operator() (const std::string& s) const
  {
    size_t h = 0;
    std::string::const_iterator p, p_end;
    for(p = s.begin(), p_end = s.end(); p != p_end; ++p)
    {
      h = 31 * h + (*p);
    }
    return h;
  }

  /**
   * 
   * @param s1 The first string
   * @param s2 The second string
   * @return true if the first string comes before the second in lexicographical order
   */
  bool operator() (const std::string& s1, const std::string& s2) const
  {
    return s1 < s2;
  }
};

typedef stdext::hash_map<std::string, std::string, stringhasher> HASH_S_S;

/**
 * Compile this program with "cl -GX hash_sample.cpp" 
 * if using MSVC++ 7.1 (Visual Studio .NET 2003)
 */
int main (int argc, char *argv[])
{
  HASH_S_S hm;
  HASH_S_S::iterator it;
    
  //-- Inserting the names of months in a hash map
  //-- key = names of the months in Portuguese
  //-- value = names of the months in English
  hm[std::string("janeiro")] = std::string("January");
  hm[std::string("fevereiro")] = std::string("February");
  hm[std::string("março")] = std::string("March");
  hm[std::string("abril")] = std::string("April");
  hm[std::string("maio")] = std::string("May");
  hm[std::string("junho")] = std::string("June");
  hm[std::string("julho")] = std::string("July");
  hm[std::string("agosto")] = std::string("August");
  hm[std::string("setembro")] = std::string("September");
  hm[std::string("outubro")] = std::string("October");
  hm[std::string("novembro")] = std::string("November");
    
  //-- Searching for the translation of the months "março" and "dezembro" in the map
  //-- (dezembro was not put into the map, so you can not find the corresponding element "December")
  it = hm.find(std::string("março"));
  if(it != hm.end())
    std::cout << "The value corresponding to the key 'março' is " << it->second << std::endl;
  else
    std::cout << "The value corresponding to the key 'março' was not found" << std::endl;

  it = hm.find(std::string("dezembro"));
  if(it != hm.end())
    std::cout << "The value corresponding to the key 'dezembro' is " << it->second << std::endl;
  else
    std::cout << "The value corresponding to the key 'dezembro' was not found" << std::endl;
        
  //-- Listing the pairs key, value (they're not ordered.)
  for(it = hm.begin(); it != hm.end(); ++it) 
  {
    std::cout << "Key = \'" << it->first << "\' -> value = \'" << it->second << "\'" << std::endl;
  }
}

http://codeguru.earthweb.net/forum/printthread.php?t=315286

vector, Removing an element

Is this the proper way to do this? (hope there is a better way)


void COpenGLsdiTestApp::RemoveView( void* pView)
{
	std::vector<void*>::iterator it;
	for ( it = m_vViews.begin(); it != m_vViews.end(); it++) {
		if ( (*it) == pView) {
			m_vViews.erase( it);
			break;
		}
	}
}

iterator

string

Reference http://www.sgi.com/tech/stl/basic_string.html

Note! If a substring is not found it returns string::npos since size_t cannot be negative

Function	Description
size_t find(const basic_string& s, size_t pos = 0) const
size_t find(const charT* s, size_t pos, size_t n) const
size_t find(const charT* s, size_t pos = 0) const
size_t find(charT c, size_t pos = 0) const
reference operator[](size_t n)
const_reference operator[](size_t n)
basic_string substr(size_t pos = 0, size_t n = npos) const
…


#include <string>

string str;
str.assign( "new string");
string str2( "2nd string");

vector

Reference Page http://www.sgi.com/tech/stl/Vector.html

Other Info

vector, Removing an element

Selected Methods

Method	Description
void reserve(size_type n)	Expands the vector to at least 'n' elements WARNING: This does not update size()
void resize(n, t = T())	Expands or contracts the vector to exactly 'n' elements, initializing the values to 't'
…