Fun with STL

From VT.Prog

Contents 1 Overview 2 Useful Classes 2.1 The Basics 2.2 Getting Fancy 3 Useless Classes 3.1 List clones 4 Using STL to make your life easier 4.1 Iteration 4.2 Basic Set 4.2.1 Key operations 4.3 Basic Map 4.3.1 Key Operators 4.4 Multi-dimensional Map 4.5 Sorting 4.6 Fancy Sorting

Overview

Standard Template Library (STL) is there to make your life simple. Most problems can be handled simply with judicious use of STL.

For the purpose of this document, by STL I mean anything with templated parameters (<>).

Useful Classes

The Basics

• set - an ordered set of elements
• map - an ordered mapping of keys to values
• vector - a growable array of values
• list - list linked list

Getting Fancy

• pair
• multiset
• multimap

Useless Classes

List clones

If you are ever tempted to use any of these, just use a list. It has all the operators and does not limit you.

• deque - same as list.
• stack - same as list.
• queue - same as list.

Using STL to make your life easier

Iteration

For all STL types, they can be iterated via something like:

for(type::iterator I=obj.begin() I!=obj.end(); I++)
{
  //I is a pointer to the object in question now
}

So if you have a set<int> that you want to print:

set<int> Ints;
for(set<int>::iterator I=Ints.begin(); I!=Ints.end(); I++)
{
  int num=*I;
  cout << num << endl;
}

If the STL type is a map, it gets a little more messy, since the iterator will point to a pair<> object containing the values. This means you have to use ->first and ->second to get the key and value respectively.

map<int,string> M;
M[1]="hobo";
M[8]="cat"
for(map<int,string>::iterator I=M.begin(); I!=M.end(); I++)
{
  int num=I->first;
  string str=I->second;
  cout << num << ": " << str << endl;
}

Will print:

1 hobo
8 cat

Note: I'd strongly advise against adding or removing elements from an STL type while iterate through it. You might get that to work, but most likely something odd will occur. Don't even try unless you really know what you are doing. If you need to remove things, I recommend making a remove list or remove set of things to remove. Then iterate through that.

Basic Set

Anytime you have a set of unique things that you need to keep track of. Note, the data type chosen must be sortable via the operator <. All basic data types and all STL types have this.

Sets can be used for the uniqueness that they enforce. For example, you could use one as a list of things that need to be checked. If you insert a duplicate, it will just replace the entry already there.

You can also check the set for the existance of something to enforce uniqueness on something or eliminate cases you have already checked.

Key operations

• .insert(V) - inserts an element into the set. Replace on duplicates.
• .count(V) - returns the count of the given element in the set. Either 0 or 1.
• .remove(V) - removes the given element from the set.
• .clear() - remove all elements

set<string> names;
names.insert("john");
names.insert("robofrance27");
names.insert("john");
if (names.count("hobo")) ...

Basic Map

map<Key,Value>

A map is an ordered set of keys to values, ordered by unique keys. This is probably the most useful STL class.

You can use it like a vector, but one where you don't know or care how high or low the index might go. You can use it keep track of any sparse data that an array or vector would be bad for.

Key Operators

• [K] - allows getting or setting based on the key inside the []'s
• .remove(K) - remove the mapping of K if it exists
• .count(K) - returns number of elements in map with key 'K' (will be 0 or 1)
• .clear() - remove all elements

When [] is used on an element that is not defined, it is created with the default constructor for the value. For interger sorts of classes, this means it will be zero.

map<int,int> M;
cout << M[81] << endl;

Prints: "0"

On the plus side, you can use that behavior to save yourself some time. For example, if you are counting things, you can just do things like:

M[key]++;

And not worry about what if anything was there before.

However, on the negative side, this means that if you are using [] to probe around, each time you use it it will add that key->value mapping to the map. This could be a problem if you plan on iterating through it later or expecting .count() to have meaning.

If you want to check for a key without adding it, use .count().

Multi-dimensional Map

I use this one all the time. Lets say you have some silly map board that you read in from input:

***************
*.............*
*.....H.......*
*...R....r.....
*.......X......
*..............
***************

You can store this in a 2d map:

map<int,map<int,char> > M;
for(int r=0; r<Rows; r++)
for(int c=0; c<Cols; c++)
{
  char z; cin >> z;
  M[r][c]=z;
}

Then, lets say you are doing a flood fill or something, you can poke around without worrying about indexes.

 if (M[i-1][j]=='*')
 { whatever }

If i is 0, i-1 will be -1. This would sink you if you were using a 2d array, but with the map, the uninitialized value is just char(0). No big deal. Same deal for going off the edge on the high side. Access is a little slower, but you don't have index checking to do.

This is also great for memoization. This is where you store the answer to a calculation so that you don't have to redo it.

Lets suppose you are implementing a choose function:

 map<int,map<int,long long> > ChooseCache;
 long long choose(int n, int r)
 {
   if (ChooseCache[n].count(r)) return ChooseCache[n][r];
   long long val;
   ..... do long recursive calculation
   ChooseCache[n][r]=val;
   return val;
 }

Sorting

Fancy Sorting