Containers

Vector

List

• A node-based container
• #include <bsl_list.h>

Deque

• #include <bsl_deque.h>

Set/Multiset

• Has O(log n) complexity for searching, insertion and deletion.
• Attention, use stl::lower_bound on set is not a good choice. It assume the container is sequential, use member function version, the same case for erase etc.
• Set elements are const, if you want to modify it, always use a map instead of set.
• Of course, you can use set of const pointers, but not preferred.

Map

• The only real difference, structurally, between a set and a map is the type of the container element. A set<T> is (usually) implemented as a red-black tree whose nodes contain a const T. (A tree node probably contains three pointers and a byte that indicates whether the node is red or black.) A map<K ,T> is implemented in exactly the same way (and probably uses the same code), but the tree node contains a pair<const K, T>.

• Like set and multiset, map and multimap automatically sort their elements according to a sorting criterion but only used on keys

• typedef of map is strongly preferred, because it is vert long.

#include <bsl_map.h>
#include <bsl_string.h>
#include <cusip.h>
typedef bsl::map<bsl::string, Cusip> Securities;
typedef Securities::iterator I;
typedef Securities::const_iterator CI;
typedef Securities::value_type VT; // important!
typedef Securities::size_type ST;  // less important
typedef bsl::pair<I, bool> InsertRet;

• Like set, a map insertion returns an iterator-bool pair first is an iterator to the element in the map second is a bool that tells you if the insertion took place

• Indexing can be used for inserting, but NEVER USE FOR LOOKUP!

Summary

• A sorted vector is gonna outperform almost any container in terms of searching,
• because during search, it has higher chance of hitting cache, in contrary, node-based
• container, nodes along search path may be very far away in memory.
• Node-based OR sequential? check iterator validation.
• Cost of insertion and erasure, and where they happens to
• Memory overhead.
• Use typedef to hide your implementation so that you can modify it later.

• Abstraction of a pointer to an element.
• has dereference operator defined (if it is an iterator, *it is the element it points to)
• similar pitfalls, dangling reference etc. !
• iterator的++逻辑包含了如何去寻找下一个元素
• Each STL container has corresponding iterator and const_iterator types.
  • vector<Security>::iterator
  • list<Cusip>::const_iterator
• syntax:

bsl::vector<Security> sv;
typedef bsl::vector<Security>::const_iterator CI;
for (CI i = sv.begin(); i != sv.end(); ++i) {
    bsl::cout << *i << '\n'; 
}

Iterator categories:

There are five categories of iterators:

1. output iterators

• only write access to the underlying element
• cannot write same element more than once
• cannot compare to other iterators

1. input iterators

• only read access to the underlying element
• cannot read same element more than once

1. forward iterators

• all capabilities of input iterators
• most capabilities of output iterators
• can access same element many times, or move forward

1. bidirectional iterators

• all capabilities of forward iterators
• can also move backward

1. random access iterators

• all capabilities of bidirectional iterators

• can also move many steps (in either direction) in constant time

• Random access iterators: vector, deque, array

• Bidirectional iterators: list, map, set

• Forward iterators: unordered_set, unordered_map, forward_list

• Input/output iterators: iostream iterators

Iterator & Const Iterator

• Const 是一个可以在iterator这层impose的一个语法
• 比如const-iterator是可以定义在一个non-const的vector上
• 但是在一个const的vector上只能定义const-iterator
• 当用来表示一个range的时候，front和end iterator必须是相同的type

Reverse-iterator & insert iterator

extern double readings[];
extern list<double> seq;
copy(readings, readings+n,
     seq.begin());         // overwrite!
copy(readings, readings+n,
     back_inserter(seq));  // append
copy(readings, readings+n,
     front_inserter(seq)); // prepend in reverse order

typedef vector<int> Cont;
typedef Cont::iterator I;
typedef Cont::reverse_iterator RI;
Cont v;
...
sort(v.begin(), v.end());     // sort in order
sort(v.rbegin(), v.rend());   // sort in reverse order
I i = find(v.begin(), v.end(), 3);    // find first 3
RI r = find(v.rbegin(), v.rend(), 3); // find last 3

Copy

list<Cusip> c1;
...
vector<Cusip> c2;
// copy c1 to c2, version 1
typedef list<Cusip>::iterator I;
for (I i = c1.begin(); i != c1.end(); ++i)
  c2.push_back(*i);  // low-tech, gauche
// copy c1 to c2, version 2
copy(c1.begin(), c1.end(), c2.begin()); // error!
// copy c1 to c2, version 3
copy(c1.begin(), c1.end(),
     back_inserter(c2));  // works!
// copy c1 to c2, version 4
vector<Cusip> c2(c1.begin(), c1.end()); // best way

Algorithm

• #include <bsl_algorithm.h>

Find

#include <bsl_iostream.h>
#include <bsl_algorithm.h>
#include <bsl_cstring.h>
void main() {
  const char *s = "IBM|76.89";
  size_t len = strlen(s);
  const char *p = find(s, s+len, '|');
  if (p != s+len) {
    bsl::cout << "Price: " << p+1 << '\n';
    // prints Price: 76.89
  }
}

Find_if

#include <bsl_list.h>
#include <bsl_algorithm.h>
list<unsigned long> nums;
bool isRamanujan(unsigned long);
...
list<unsigned long>::const_iterator i = 
   find_if(nums.begin(), nums.end(), isRamanujan);
if (i == nums.end()) {
   // not found
} else {
   // found
}

Erase/Remove

v.erase(remove(v.begin(), v.end(), 8), v.end());
v.erase(remove_if(v.begin(), v.end(), isPrime),
        v.end());

DO NOT eraser remove on a container of poiner 因为remove之后保存在后面的内容是undefined，有可能误删掉valid的内容，同时应该被删的内容有可能会 leak

SOLUTION: use unique_ptr or use partition instead of erase.

Sort

Comparator

• A binary predicate that serves as a less-than-like operation
• only > and <
• Example

struct Score {
  string name;
  long score;
};
bool scoreComp(const Score &a, const Score &b) {
  return (a.score > b.score)
    ? true : (b.score > a.score)
      ? false : a.name < b.name;
}
Score *scores;
size_t numScores = 0;
...
sort(scores, scores+numScores, scoreComp);

• Another solution is to use stable_sort

nth_element

• Quick way to find the smallest/largest n elements.

Equivalence and Equality

Equivalence means neither one is less than the other. Equality means one is equal to the other.

VS. Other predicate

• Sort requires a comparator
• Unique requires a similarity predicate.

Binary Search

• lower_bound returns the head of the equivalent sequence.
• upper_bound returns one past the tail of the equivalent sequence.
• They all return the place to insert.

• standard function object is very much like functor, you need to initiate an object to use it.
• greater<T>, is a binary function, we sometimes want to use it as unary, we can use bind1st, bind2nd to make it unary.