The Brief of C++ Standard Template Library

Xiao Wenbin
Last updated on Jan 2, 2020 5 min read C++

STL简介

C++标注库（The Standard Template Library）提供了丰富的泛型组件，包括常用数据结构、算法、容器类、迭代类等模板。

Helper Classes

Pair

  • 定义

    // don't need to include header
template <class U, class V>
struct pair {
    U first;
    V second;
    pair(const U& first = U(), const V& second = V())
      :first(first), second(second) {}
};

template <class U, class Y>
pair<U, V> make_pair(const U& first, const V& second);Description

  • 描述

    pair 是 map 和 set这类关联容器数据结构的基础，可以将pair的第一个元素当作键，第二个元素当作关联的值。此外要注意pair不是类而是一个结构体，因此成员变量是公开的，可以在外部直接访问。

Container Classes

  • 容器类是抽象数据结构（Abstract Data Types ）
  • 容器类是泛型的，因此要通过类型参数来初始化
  • 容器类提供了工厂方法来创建迭代器，以供遍历容器中的元素

Sequential

  • 常用序列类有：vector，deque，list等
  • 以线性方式组织容器中的数据
  • 线性方式组织并不意味着物理储存是线性的

Vector

  • 定义

    #include <vector>
using namespace std;

template <class T>
class vector {
public:
    vector();
    vector(const vector<T>& originalMap);

    typedef implementation_specific_class_1 iterator;
    typedef implementation_specific_class_2 const_iterator;

    bool empty() const;
    long size() const;
    void clear();

    void push_back(const T& elem);
    void pop_back();

    T& operator[](int i);
    const T& operator[](int i) const;
    iterator insert(iterator where, const T& elem);
    iterator erase(iterator where);

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
};

  • 描述

    vector 有点像动态数组，可以使用[]操作符访问以及修改元素，也可以使用成员方法insert和erase来在任何地方插入删除元素（内部自动完成空间的伸缩以及元素的移动）。

    // 将文件流读入到vector中
static void readFile(ifstream& infile, vector<string>& lines)
{
    assert(lines.size() == 0);
    assert(infile.good());

    string line;
    while (infile.peek() != EOF) {
        getline(infile, line); // reassign line to be next line of file
        lines.push_back(line); // append
    }
    cout << "All done! (Number of lines: " << lines.size() << ")" << endl;
}

// 数组方式访问
vector<double> transactionAmounts;
double totalSales = 0.0;
for (int i = 0; i < transactionAmounts.size(); i++)
    totalSales += transactionAmounts[i];

// 迭代器方式访问
vector<double>::const_iterator curr = transactionAmounts.begin();
vector<double>::const_iterator end = transactionAmouts.end();
for (; curr != end; ++curr)
    totalSales += *curr;

Deque

deque 是双端队列，可以高效（常量时间）的在队列两端插入删除元素。

List

list 可以在任何位置高效（常量时间）的插入删除元素（底层用双向链表实现），不支持随机访问。

Associative

  • 支持数据的关联存储（即键-值存储）
  • 底层使用平衡二叉树实现

Set

set 中元素的键唯一

Map

  • 定义

    #include <map>
using namespace std;

template <class Key, class Value>
class map {
public:
        map();
        map(const map<Key, Value>& originalMap);        
        pair<iterator, bool> insert(const pair<Key, Value>& newEntry);
        iterator find(const Key& key);
        const_iterator find(const Key& key) const;
        Value& operator[](const Key& key);
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;
};

  • 描述

    map是泛型符号表，键和值的类型都允许用户来指定

  • Description

    The map is the STL’s generic symbol table, and it allows you to specify the data type for both the key and the value

    // insert是非强制插入，返回值pair的第二个元素用来解释插入是否成功
typedef map<string, vector<string> > chordMap;
chordMap jazzChords;
vector<string> cmajor;
cmajor.push_back("C");
cmajor.push_back("E");
cmajor.push_back("G");
pair<chordMap::iterator, bool> result = jazzChords.insert(make_pair(string("C Major"), cmajor));

if(result.second)
cout << "\" << result.first->first << "\" was successfully inserted." << endl;
else
cout << "\" << result.first->first << "\" already present." << endl;

// find查找是否含有某个键
// 在C语言中，当查找不存在是会返回NULL或者-1，
// 而容器类则通过定义了一个特殊值用来标识未找到
chordMap::const_iterator found = jazzChords.find("F# minor 11");
if (found == jazzChords.end()) // container.end()表示未找到的标识
cout << "Chord was never recorded." << endl;

// []操作符允许访问修改value by key
map<string, int> portfolio;
// portfolio.insert(make_pair(string("LU"), 400));
portfolio["LU"] = 400;
portfolio["AAPL"] = 80;
portfolio["GOOG"] = 6500;
portfolio["GOOG"] += 30

// 迭代访问
int stockCount = 0;
map<string, int>::const_iterator curr = stocks.begin();
while (curr != stocks.end()) {
stockCount += curr->second;
++curr;
}

Multimap

multimap 支持插入相同键，即键不唯一

Adapter

  • stack
  • queue
  • priority
  • queue

Iterator Classes

  • STL迭代器可以看成指针的推广
  • 迭代器一般用来遍历访问一些对象
  • 迭代器是泛型编程的核心，充当容器类和算法类的桥梁

Input Iterator

输入迭代器用来序列数据的读取。支持解引用操作来访问被引用的对象，递增操作来访问下一个迭代器

// Fill a vector with values read from standard input.
std::vector<int> v;
for (istream_iterator<int> i = cin; i != istream_iterator<int> (); ++i)
	v.push_back (*i);

// Fill vector with values read from stdin using std::copy()
std::vector<int> v;
std::copy (std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(v));

Output Iterator

输出迭代器用来序列数据的写入。可以将输出迭代器想象成磁带，支持在当前位置读取、写入、移动到一下位置，但是不能回退。

// Copy a file to cout via a loop.
std::ifstream ifile ("example_file");
int tmp;
while (ifile >> tmp) std::cout << tmp;
// Copy a file to cout via input & output iterators
std::ifstream ifile ("example_file");
std::copy (std::istream_iterator<int> (ifile), std::istream_iterator<int> (), std::ostream_iterator<int> (std::cout));

Forward Iterator

前向迭代器必须同时实现了输入输出迭代器

template <typename ForwardIterator, typename T>

void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) {
	for (; first != last; ++first)
		if (*first == old_value) *first = new_value;
}

std::vector<int> v (3, 1); // 1, 1, 1
v.push_back (7); // 1, 1, 1, 7
replace (v.begin(), v.end(), 7, 1);
assert (std::find (v.begin(), v.end(), 7) == v.end());

Bidirectional Iterator

双向迭代器支持向前和向后访问操作，许多容器类均支持双向迭代，例如：list，set， multiset，map，multimap

template <typename BidirectionalIterator, typename Compare>
void bubble_sort (BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
	BidirectionalIterator left_el = first, right_el = first;
	++right_el;
	while (first != last)
	{
		while (right_el != last) {
			if (comp(*right_el, *left_el)) std::swap (left_el, right_el);
			++right_el;
			++left_el;
		}
		--last;
		left_el = first, right_el = first;
		++right_el;
	}
}

Random Access Iterator

随机访问迭代器允许随机的访问容器中的元素，所谓随机就是可以直接访问容器中任意位置的元素，容器类vector，deque都实现了随机访问

std::vector<int> v (1, 1);
v.push_back (2); v.push_back (3); v.push_back (4); // vector v: 1 2 3 4
std::vector<int>::iterator i = v.begin();
std::vector<int>::iterator j = i + 2; cout << *j << " ";
i += 3; std::cout << *i << " ";
j = i - 1; std::cout << *j << " ";

Generic Algorithms

算法不是直接作用于容器而是作用于迭代器。每个容器类都通过Trait来声明迭代器，vector和deque声明了随机访问迭代器，list、map、set、multimap、multiset等声明了双向迭代器，可以调用容器类的工厂方法begin、end、rbegin、rend来访问迭代器。算法在实现时，通过调用容器类的迭代器来访问容器元素的，一致的容器类迭代器接口使得算法的泛型成为了可能。所谓算法泛型是指，算法不是针对特定容器类而编写的，而是面向迭代器编写的，不同的容器类只要实现了相同的迭代器，就都可以使用相同的算法。

Find

返回被查找元素第一次出现位置的前向迭代器

#include <vector>
#include <algorithm>
#include <assert>
#include <string>

int main (int argc, char *argv[]) {
	std::vector <std::string> projects;
	for (int i = 1; i < argc; ++i)
		projects.push_back (std::string (argv [i]));
	std::vector<std::string>::iterator j = std::find (projects.begin (), projects.end (), std::string ("Lab8"));
	if (j == projects.end ()) return 1;
	assert ((*j) == std::string ("Lab8"));
	return 0;
}

Copy

从输入迭代器复制到输出迭代器

std::vector<int> v;
std::copy (std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(v));
std::copy (v.begin (), v.end (), std::ostream_iterator<int> (std::cout));

Fill

将序列的值都赋值为某个值

int a[10];
std::fill (a, a + 10, 100);
std::fill_n (a, 10, 200);
std::vector<int> v (10, 100);
std::fill (v.begin (), v.end (), 200);
std::fill_n (v.begin (), v.size (), 200);

Replace

替换

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(1);
std::replace (v.begin (), v.end (), 1, 99);
assert (V[0] == 99 && V[3] == 99);

Remove

移除

int *nend = std::remove (pbegin, pend, 20);
// 根据测试条件移除元素
pend = std::remove_if (pbegin, pend, is_odd ());

Transform

std::transform

For each

std::for_each
STL C++
Xiao Wenbin
Xiao Wenbin
Natural Language Processing Engineer

My research interests include machine learning, information retrieval and natural language processing.