map => vector

map<string, int> M;
vector< pair<string, int> > V(all(M));

• sort order of vector elements same as map
• useful to access elements by their indices

copy

copy(from_begin, from_end, to_begin);

• copies elements from 1st interval to 2nd
• 2nd interval should have sufficient space
• from_{begin,end} can be .r{begin,end}()

vector<int> v1, v2;
v1.resize(v1.size() + v2.size());
// v1 = (original v1) + (v2)
copy(all(v2), v1.end() - v2.size());

+inserters

vector<int> v;
set<int> s;
// add some elements to set...
copy(all(v), inserter(s));
/* equivalent to:
	tr(v, it) {
		s.insert(*it);
	}
*/

• to insert elements to vector with push_back, use back_inserter
• front_inserter available for deque ### merge 2 sorted lists

• MUST BE SORTED

• single-pass; O(N1+N2) complexity

common operations X:

• union: R=A+B
• intersection: R=A*B
• difference: R=A*() or R=A-B
• symmetric difference: R=A^B

end_result = set_X(begin1, end1, begin2, end2, begin_result);

• input: [begin1,end1), [begin2,end2)
• begin_result: iterator where result will be written
• returns end iterator of output
• ...from which size can be derived

int data1[] = { 1, 2, 5, 6, 8, 9, 10 };
int data2[] = { 0, 2, 3, 4, 7, 8, 10 };
vector<int> v1(data1, data1+sizeof(data1)/sizeof(data1[0]));
vector<int> v2(data2, data2+sizeof(data2)/sizeof(data2[0]));
vector<int> tmp(max(v1.size(), v2.size());
vector<int> res = vector<int> (tmp.begin(), set_intersection(all(v1), all(v2), tmp.begin());
int cnt = set_intersection(all(v1), all(v2), tmp.begin()) - tmp.begin();

fewer mallocs (preferred)

set<int> s1, s2;
for(int i = 0; i < 500; i++) {
	s1.insert(i*(i+1) % 1000);
	s2.insert(i*i*i % 1000);
}
static int temp[5000]; // greater than we need
vector<int> res = vi(temp, set_symmetric_difference(all(s1), all(s2), temp));
int cnt = set_symmetric_difference(all(s1), all(s2), temp) - temp;

accumulate()

vector<int> v;

// sum all elements
int sum = accumulate(all(v), 0);

// specify type
long long sum = accumulate(all(v), (long long)0);

// calculate product of values
double product = accumulate(all(v), double(1), multiplies<double>());

• calculate scalar product of 2 intervals

vector<int> v1;
vector<int> v2;

for(int i = 0; i < 3; i++) {
	v1.push_back(10-i);
	v2.push_back(i+1);
}

// multiply corresponding elements
int r = inner_product(all(v1), v2.begin(), 0);

// multiply complementary elements, eg. 0th with (N-1)th
int r = inner_product(all(v), v.rbegin(), 0);

// inner_product for the hyperplane object in multidimensional space
inner_product(all(normal), point.begin(), -shift);

convolution filter

set<int> values_ordered_data(all(data));
int n = sz(data); // int n = int(data.size());
vector<int> convolution_kernel(n);
for(int i = 0; i < n; i++) {
	convolution_kernel[i] = (i+1)*(n-i);
}
double result = double(inner_product(all(ordered_data), convolution_kernel.begin(), 0)) / accumulate(all(convolution_kernel), 0);

sorting with comparators

• all comparison is based on operator<

struct fraction {
	int n, d; // (n/d)
	// ...
	bool operator < (const fraction& f) const {
		if(false) {
			return (double(n)/d) < (double(f.n)/f.d);
			// Try to avoid this, you're the TopCoder!
		}
		else {
			return n*f.d < f.n*d;
		}
	}
};
vector<fraction> v;
sort(all(v));

• nontrivial fields: default,copy,(assignment) operators
• prototype of 'operator <' : return type bool, const modifier, parameter const reference

comparison functor: sort points, pair<double,double>, by polar angle

typedef pair<double, double> dd;
const double epsilon = 1e-6;
struct sort_by_polar_angle {
       dd center;
       // Constuctor of any type
       // Just find and store the center
       template<typename T> sort_by_polar_angle(T b, T e) {
            int count = 0;
            center = dd(0,0);
            while(b != e) {
                        center.first += b->first;
                        center.second += b->second;
                   b++;
                count++;
            }
                   double k = count ? (1.0/count) : 0;
            center.first *= k;
                   center.second *= k;
       }
 // Compare two points, return true if the first one is earlier
 // than the second one looking by polar angle
 // Remember, that when writing comparator, you should
 // override not ‘operator <’ but ‘operator ()’
       bool operator () (const dd& a, const dd& b) const {
            double p1 = atan2(a.second-center.second, a.first-center.first);
            double p2 = atan2(b.second-center.second, b.first-center.first);
            return p1 + epsilon < p2;
       }
 };
 vector<dd> points;
 sort(all(points), sort_by_polar_angle(all(points)));

• 'operator <' should always return false for equal objects
• Elements in set and map are ordered, so if you want to enable using of your objects in set or map you should make them comparable

const double epsilon = 1e-7;
struct point {
       double x, y;
       // Declare operator < taking precision into account
       bool operator < (const point& p) const {
            if(x < p.x - epsilon) return true;
            if(x > p.x + epsilon) return false;
            if(y < p.y - epsilon) return true;
            if(y > p.y + epsilon) return false;
            return false;
       }
 };

• set<point> / map<point, string> to lookup if point \in list of intersections
• map<point, vector<int> > list the list of indices of segments that intersect at this point

vector memory management

• STL <vector> double in memory size allocation when push_back() is invoked
• Conserve memory

1. v.reserve(1050); — will not enlarge until specified size is reached
   • usually v.reserve(); copy(..., back_inserter(v));
2. freeze vector from further additions, and memory allocation

vector<int> v; 
// ... 
vector<int>(all(v)).swap(v);

implement real algorithms with STL