C++标准库笔记三：STL容器
（20141001）
注：multimap可以使用lower_bound和upper_bound方式遍历相同键，例如
std::multimap<std::string, RadioButton *>::iterator iterEnd = mGroupMap.upper_bound(mGroup);
for (iter = mGroupMap.lower_bound(mGroup);
iter != iterEnd;
iter++)
下面的代码用gcc version 3.4.5 (mingw-vista special r3)测试
来源于sgi STL的官方手册以及《泛型编程与STL》（Generic Programming and the STL）
see
http://www.sgi.com/tech/stl/
http://www.sgi.com/tech/stl/stl_index_cat.html
代码上传到这个SVN
svn://www.oksvn.com/weimingtom_tools/msys-1.0.11/home/Administrator/sgi
C++ STL相关介绍请以官方文档为准。
// 编译命令行：
// g++ test007.cpp
//see http://www.cplusplus.com/reference/stl/
// 演示STL容器
#include <assert.h>
#include <vector>
#include <iostream>
#include <iterator>
#include <list>
#include <ext/slist>
#include <deque>
#include <set>
#include <map>
#include <ext/hash_set>
#include <ext/hash_map>
#include <stack>
#include <queue>
//用于排序的函数对象
struct ltstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
//用于哈希查找的函数对象
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
//哈希查找
void lookup(const __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>& Set,
const char* word)
{
__gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr>::const_iterator it
= Set.find(word);
std::cout << word << ": "
<< (it != Set.end() ? "present" : "not present")
<< std::endl;
}
//哈希查找
void lookup(const __gnu_cxx::hash_multiset<const char*, __gnu_cxx::hash<const char*>, eqstr>& Set,
const char* word)
{
int n_found = Set.count(word);
std::cout << word << ": "
<< n_found << " "
<< (n_found == 1 ? "instance" : "instances")
<< std::endl;
}
// 使用typedef简化容器的类型名
typedef __gnu_cxx::hash_multimap<const char*, int, __gnu_cxx::hash<const char*>, eqstr> map_type;
//哈希查找
void lookup(const map_type& Map, const char* str)
{
std::cout << str << ": ";
std::pair<map_type::const_iterator, map_type::const_iterator> p =
Map.equal_range(str);
for (map_type::const_iterator i = p.first; i != p.second; ++i)
std::cout << (*i).second << " ";
std::cout << std::endl;
}
int main(int argc, const char *argv[])
{
{
//vector<T, Alloc>
//支持随机元素访问的动态数组（序列）
std::vector<int> V;
V.insert(V.begin(), 3);
assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);
//扩大vector的容量到指定值，除非已经超过指定值
std::cout << "size:" << V.size() << ",capacity:" << V.capacity() << std::endl;
V.reserve(3);
std::cout << "size:" << V.size() << ",capacity:" << V.capacity() << std::endl;
//用构造函数复制vector，容量会自动压缩
std::vector<int> temp(V.begin(), V.end());
std::cout << "Use vector's ctor copy:" << std::endl;
std::cout << "size:" << temp.size() << ",capacity:" << temp.capacity() << std::endl;
//用swap把序列转移到新的vector，容量不会改变，
//而且原来的vector会被修改（交换了内容）
std::vector<int> temp_swap;
temp_swap.swap(V);
std::cout << "Use vector's swap:" << std::endl;
std::cout << "temp_swap's size:" << temp_swap.size() << ",capacity:" << temp_swap.capacity() << std::endl;
std::cout << "V's size:" << V.size() << ",capacity:" << V.capacity() << std::endl;
//把序列复制到vector，通常用于输入流
//用法类似std::copy
std::cout << "Please input double array (NaN is EOF):" << std::endl;
std::istream_iterator<double> first(std::cin);
std::istream_iterator<double> eof;
std::vector<double> buf(first, eof);
std::cout << "input double numbers are:" << std::endl;
std::copy(buf.begin(), buf.end(),
std::ostream_iterator<double>(std::cout, "\n"));
std::cout << std::flush;
}
{
//list<T, Alloc>
//双向链表
std::list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
std::cout << "list:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
//排序
L.sort();
std::cout << "sorted list:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
//合并
std::list<int> L2;
L2.push_back(3);
L2.push_back(2);
L2.push_back(1);
L.merge(L2);
std::cout << "merged list:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
//颠倒次序
L.reverse();
std::cout << "reversed list:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
{
//slist<T, Alloc>
//单向链表
//从begin()插入
__gnu_cxx::slist<int> L;
L.push_front(0);
L.push_front(1);
L.insert_after(L.begin(), 2);
std::cout << "slist, insert to begin:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
//从end()插入
__gnu_cxx::slist<int>::iterator back = L.previous(L.end());
back = L.insert_after(back, 3);
back = L.insert_after(back, 4);
back = L.insert_after(back, 5);
std::cout << "slist, insert to end:" << std::endl;
std::copy(L.begin(), L.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
{
//deque<T, Alloc>
//双端队列，类似vector，
//支持随机访问和双端插入，
//但不支持capacity()和reserve()
std::deque<int> Q;
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
std::cout << "deque:" << std::endl;
std::copy(Q.begin(), Q.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
{
//set<Key, Compare, Alloc>
//集合，不重复的序列，可执行交、并、差集
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
const char* b[N] = {"flat", "this", "artichoke",
"frigate", "prosaic", "isomer"};
std::set<const char*, ltstr> A(a, a + N);
std::set<const char*, ltstr> B(b, b + N);
std::set<const char*, ltstr> C;
std::cout << "Set A: ";
std::copy(A.begin(), A.end(),
std::ostream_iterator<const char*>(std::cout, " "));
std::cout << std::endl;
std::cout << "Set B: ";
std::copy(B.begin(), B.end(),
std::ostream_iterator<const char*>(std::cout, " "));
std::cout << std::endl;
std::cout << "Union: ";
std::set_union(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<const char*>(std::cout, " "),
ltstr());
std::cout << std::endl;
std::cout << "Intersection: ";
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<const char*>(std::cout, " "),
ltstr());
std::cout << std::endl;
std::set_difference(A.begin(), A.end(), B.begin(), B.end(),
std::inserter(C, C.begin()),
ltstr());
std::cout << "Set C (difference of A and B): ";
std::copy(C.begin(), C.end(),
std::ostream_iterator<const char*>(std::cout, " "));
std::cout << std::endl;
}
{
//map<Key, Data, Compare, Alloc>
//关联数组，映射表，键不可重复
std::map<const char*, int, ltstr> 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;
std::cout << "june -> " << months["june"] << std::endl;
std::map<const char*, int, ltstr>::iterator cur = months.find("june");
std::map<const char*, int, ltstr>::iterator prev = cur;
std::map<const char*, int, ltstr>::iterator next = cur;
++next;
--prev;
std::cout << "Previous (in alphabetical order) is " << (*prev).first << std::endl;
std::cout << "Next (in alphabetical order) is " << (*next).first << std::endl;
//另一种插入键值对的方法（可以判断是否插入成功）
std::map<const char*, int, ltstr> M;
std::pair<std::map<const char*, int>::iterator, bool> p = M.insert(std::make_pair("A", 17));
//第二返回值表示插入是否成功
if(p.second)
std::cout << "insert pair is " << p.first->first << ", " << p.first->second << std::endl;
//<< "pair:" << "," << p.second
}
{
//multiset<Key, Compare, Alloc>
//允许元素重复的集合
const int N = 10;
int a[N] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
int b[N] = {4, 4, 2, 4, 2, 4, 0, 1, 5, 5};
std::multiset<int> A(a, a + N);
std::multiset<int> B(b, b + N);
std::multiset<int> C;
std::cout << "Set A: ";
std::copy(A.begin(), A.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
std::cout << "Set B: ";
std::copy(B.begin(), B.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
std::cout << "Union: ";
std::set_union(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
std::cout << "Intersection: ";
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
std::set_difference(A.begin(), A.end(), B.begin(), B.end(),
std::inserter(C, C.begin()));
std::cout << "Set C (difference of A and B): ";
std::copy(C.begin(), C.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
{
//multimap<Key, Data, Compare, Alloc>
//键允许重复的关联数组
std::multimap<const char*, int, ltstr> m;
m.insert(std::pair<const char* const, int>("a", 1));
m.insert(std::pair<const char* const, int>("c", 2));
m.insert(std::pair<const char* const, int>("b", 3));
m.insert(std::pair<const char* const, int>("b", 4));
m.insert(std::pair<const char* const, int>("a", 5));
m.insert(std::pair<const char* const, int>("b", 6));
std::cout << "Number of elements with key a: " << m.count("a") << std::endl;
std::cout << "Number of elements with key b: " << m.count("b") << std::endl;
std::cout << "Number of elements with key c: " << m.count("c") << std::endl;
std::cout << "Elements in m: " << std::endl;
for (std::multimap<const char*, int, ltstr>::iterator it = m.begin(); it != m.end(); ++it)
std::cout << " [" << (*it).first << ", " << (*it).second << "]" << std::endl;
}
{
//hash_set<Key, HashFcn, EqualKey, Alloc>
//支持哈希查找的集合，不允许元素重复
__gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, eqstr> Set;
Set.insert("kiwi");
Set.insert("plum");
Set.insert("apple");
Set.insert("mango");
Set.insert("apricot");
Set.insert("banana");
lookup(Set, "mango");
lookup(Set, "apple");
lookup(Set, "durian");
}
{
//hash_map<Key, Data, HashFcn, EqualKey, Alloc>
//支持哈希查找的关联数组，不允许键重复
__gnu_cxx::hash_map<const char*, int, __gnu_cxx::hash<const char*>, eqstr> 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;
std::cout << "september -> " << months["september"] << std::endl;
std::cout << "april -> " << months["april"] << std::endl;
std::cout << "june -> " << months["june"] << std::endl;
std::cout << "november -> " << months["november"] << std::endl;
}
{
//hash_multiset<Key, HashFcn, EqualKey, Alloc>
//支持哈希查找的集合，允许元素重复
__gnu_cxx::hash_multiset<const char*, __gnu_cxx::hash<const char*>, eqstr> Set;
Set.insert("mango");
Set.insert("kiwi");
Set.insert("apple");
Set.insert("kiwi");
Set.insert("mango");
Set.insert("mango");
Set.insert("apricot");
Set.insert("banana");
Set.insert("mango");
lookup(Set, "mango");
lookup(Set, "apple");
lookup(Set, "durian");
}
{
//hash_multimap<Key, Data, HashFcn, EqualKey, Alloc>
//支持哈希查找的集合，允许键重复
map_type M;
M.insert(map_type::value_type("H", 1));
M.insert(map_type::value_type("H", 2));
M.insert(map_type::value_type("C", 12));
M.insert(map_type::value_type("C", 13));
M.insert(map_type::value_type("O", 16));
M.insert(map_type::value_type("O", 17));
M.insert(map_type::value_type("O", 18));
M.insert(map_type::value_type("I", 127));
lookup(M, "I");
lookup(M, "O");
lookup(M, "Rn");
}
{
//stack<T, Sequence>
//堆栈，后进先出
std::stack<int> S;
S.push(8);
S.push(7);
S.push(4);
assert(S.size() == 3);
assert(S.top() == 4);
S.pop();
assert(S.top() == 7);
S.pop();
assert(S.top() == 8);
S.pop();
assert(S.empty());
}
{
//queue<T, Sequence>
//队列，先进先出
std::queue<int> Q;
Q.push(8);
Q.push(7);
Q.push(6);
Q.push(2);
assert(Q.size() == 4);
assert(Q.back() == 2);
assert(Q.front() == 8);
Q.pop();
assert(Q.front() == 7);
Q.pop();
assert(Q.front() == 6);
Q.pop();
assert(Q.front() == 2);
Q.pop();
assert(Q.empty());
}
{
//priority_queue<T, Sequence, Compare>
//优先队列，最先弹出的是队列中的最大值
std::priority_queue<int> Q;
Q.push(1);
Q.push(4);
Q.push(2);
Q.push(8);
Q.push(5);
Q.push(7);
assert(Q.size() == 6);
assert(Q.top() == 8);
Q.pop();
assert(Q.top() == 7);
Q.pop();
assert(Q.top() == 5);
Q.pop();
assert(Q.top() == 4);
Q.pop();
assert(Q.top() == 2);
Q.pop();
assert(Q.top() == 1);
Q.pop();
assert(Q.empty());
//让队列中最小元素的先出列
//其中，模板的第二参数表示它的底层实现是std::vector<int>
std::priority_queue< int, std::vector<int>, std::greater<int> > Q2;
Q2.push(4);
Q2.push(2);
assert(Q2.top() == 2);
Q2.pop();
assert(Q2.top() == 4);
}
//标准C++允许main不返回，但标准C要求必须返回
return 0;
}
相关推荐
《深入理解STL：侯捷讲授C++标准模板库》 STL，全称Standard Template Library，是C++编程语言中的一个核心组件，由Alexander Stepanov和Mangus Sander等人设计，为程序员提供了高效且灵活的容器、迭代器、算法和...
在C++编程中，STL（Standard Template Library，标准模板库）是不可或缺的一部分，它为开发者提供了高效且灵活的数据结构和算法。这份“C++进阶STL源码笔记”显然是一个深入研究STL的资源，适合那些已经有一定C++...
STL是C++标准库的重要组成部分，由Alexander Stepanov和Maeve Kline设计，主要包含五大组件：容器、迭代器、算法、函数对象和分配器。这些组件协同工作，为开发者提供了强大而灵活的数据处理能力。 二、STL容器 1. ...
9. **STL(Standard Template Library)**：STL是C++标准库的一部分，提供了容器（如vector、list、map等）、迭代器、算法和函数对象等组件，极大提高了代码的可读性和复用性。 10. **C++新特性**：随着标准的更新，...
STL（Standard Template Library，标准模板库）是C++编程语言中的一个重要组成部分，它提供了高效且灵活的数据结构和算法。这篇学习笔记将深入探讨STL的核心概念、主要组件以及其在实际编程中的应用。 首先，STL的...
STL是C++标准库的核心部分，它提供了一组高效的容器（如`std::vector`、`std::list`、`std::map`等）、迭代器、算法和函数对象。这些组件可以组合使用，实现各种复杂的数据结构和算法。 1. 容器：容器是STL中用于...
C++/STL/读书笔记是对C++标准模板库（Standard Template Library，简称STL）深入学习的重要资源。STL是C++编程中不可或缺的一部分，它提供了高效且可重用的数据结构和算法，极大地提高了代码的编写效率和可读性。...
10. **STL（Standard Template Library）**：STL是C++的标准库，包含容器（如vector、list、set、map等）、算法（如排序、查找等）、迭代器和内存管理工具（如智能指针），极大提高了编程效率。 11. **I/O流库**：...
C++ STL（Standard Template Library，标准模板库）是一组广泛使用的C++编程语言模板，它包含了各种通用数据结构和算法的实现。STL允许程序员不必从零开始就能实现复杂的数据处理和操作，其主要组成部分包括容器、...
- STL（标准模板库）：STL是一个包含容器、迭代器、算法和函数对象的模板库，它提供了一组通用的、经过优化的数据结构和算法实现。 2. 用const、enum和inline替代#define：这一部分强调了使用预处理器宏的缺点，...
6. **智能指针**：虽然《Effective STL》出版时智能指针尚未成为C++标准的一部分，但理解如何使用auto_ptr（C++98）或unique_ptr、shared_ptr（C++11及以后版本）管理动态分配的对象，对于避免内存泄漏和提高代码...
C++中的标准模板库（STL）是一个强大的库，它包含了一系列的数据结构和算法。本次学习笔记将围绕STL中的一些容器和函数进行详细探讨，包括vector、set、string和map等常用容器的定义、操作方法和它们的常见用途。 ...
在C++编程领域，STL（Standard Template Library，标准模板库）是不可或缺的一部分，它极大地提高了程序员的效率，提供了高效且可重用的数据结构和算法。以下是对标题、描述及标签所涉及知识点的详细说明： 一、C++...
8. 标准库应用：STL（Standard Template Library）是C++的标准库，包含容器（如vector、list）、算法和迭代器等，极大地提高了开发效率。C++(day10).txt可能介绍了STL的使用。 9. 多线程编程：C++11引入了内置的多...
《Effective STL》是一本关于C++标准模板库(STL)的权威指南，由Scott Meyers撰写，旨在帮助程序员更高效、更安全地使用STL。精版笔记意味着作者对书中内容进行了精心提炼和总结，以供读者快速掌握STL的核心概念和...
C++标准库中的`std::string`类提供了方便的字符串操作。 4. **结构体与联合体**：结构体是将不同数据类型组合在一起的数据结构，而联合体允许在相同的内存空间内存储不同类型的数据。 5. **类与对象**：C++的核心...
这篇学习笔记主要涉及了C++编程的一些核心概念，包括程序结构、变量、基本类型、初始化与赋值、可读性、常量与引用、typedef、枚举以及标准库中的字符串和向量类型。 1. **程序结构**： - 每个C++程序都必须包含`...
6. **STL（Standard Template Library）**：STL是C++标准库的重要组成部分，包含容器、迭代器、算法和函数对象。了解并熟练使用STL能极大提升代码的效率和可读性。 7. **内存管理**：C++允许程序员直接管理内存，...
5. **STL（Standard Template Library）**：STL是C++的标准库，包含容器（如vector、list、set等）、迭代器、算法和函数对象，为程序员提供了高效的数据结构和算法。 6. **异常处理**：C++提供了异常处理机制，通过...