Boost 中好用的算法
基于 boost 1.82…
timer 计时器
过去老的 boost/timer.hpp 已经废弃了,目前推荐使用的是 boost/timer/timer.hpp, 主要包括下面了2个类
| class | detail |
|---|---|
boost::timer::cpu_timer | 计时器 |
boost::timer::auto_cpu_timer | 计时器,基于cpu_timer实现,在析构的时候输出耗时 |
struct cpu_times {
nanosecond_type wall; // 挂钟时间
nanosecond_type user; // 用户时间
nanosecond_type system; // 系统时间
void clear() {wall = user = system = 0LL; }
};默认的输出格式为下:
“%w s wall, %u s user + %s s system = %t s CPU (%p%)\n”
| format | meaning |
|---|---|
| %w | times.wall |
| %u | times.user |
| %s | times.system |
| %t | times.user + times.system |
| %p | The percentage of times.wall represented by times.user + times.system |
来个简单的例子:
#include <boost/timer/timer.hpp>
#include <cmath>
#include <iostream>
using namespace std;
using namespace boost;
int main() {
timer::cpu_timer t;
timer::auto_cpu_timer auto_timer(6, "%ws real time\n");
for (long i = 0; i < 100000000; ++i)
auto _ = sqrt(i * i); // spend some time
cout << t.format(2, "%us user + %ss system = %ts(%p%)") << endl;
t.start();
for (long i = 0; i < 100000000; ++i)
auto _ = sqrt(i * i); // spend some time
cout << t.format(2, "%us user + %ss system = %ts(%p%)") << endl;
return 0;
}split
stl缺少个split, 好难受啊
头文件为boost/algorithm/string/split.hpp
#include <boost/algorithm/string.hpp>
#include <iostream>
#include <string>
#include <set>
int main(int argc, char *argv[]) {
std::string str = "123,,345,qwe;adq,345";
std::set<std::string> st;
boost::split(st, str, boost::is_any_of(",; "), boost::token_compress_on);
for_each(st.begin(), st.end(), [](const std::string& x) {std::cout << "[" << x << "]\n";});
return 0;
}默认为 token_compress_off: 表示遇见多个token时候,不合并成一个token, 这时候,,分割后,会多一个空string,表示2个逗号中间的空string
需要链接的库: libboost_system (通常自动链接)
circular_buffer 环形缓冲区
Boost.Circular_buffer 提供了固定大小的环形缓冲区,当缓冲区满时自动覆盖最旧的数据。C++23 标准库中没有类似功能。
头文件: boost/circular_buffer.hpp
#include <boost/circular_buffer.hpp>
#include <iostream>
int main() {
// 创建容量为 5 的环形缓冲区
boost::circular_buffer<int> cb(5);
// 添加元素
for (int i = 0; i < 7; ++i) {
cb.push_back(i);
std::cout << "Added " << i << ", size: " << cb.size()
<< ", capacity: " << cb.capacity() << "\n";
}
// 输出内容
std::cout << "Contents: ";
for (const auto& item : cb) {
std::cout << item << " ";
}
std::cout << "\n";
// 访问元素
std::cout << "Front: " << cb.front() << "\n";
std::cout << "Back: " << cb.back() << "\n";
std::cout << "cb[2]: " << cb[2] << "\n";
// 插入到指定位置
cb.insert(cb.begin() + 2, 99);
std::cout << "After insert: ";
for (const auto& item : cb) {
std::cout << item << " ";
}
std::cout << "\n";
// 弹出元素
cb.pop_front();
std::cout << "After pop_front: ";
for (const auto& item : cb) {
std::cout << item << " ";
}
std::cout << "\n";
return 0;
}需要链接的库: libboost_circular_buffer (通常为 header-only)
bimap 双向映射
Boost.Bimap 提供了双向映射容器,可以从两个方向查找键值对。C++23 标准库中没有类似功能。
头文件: boost/bimap.hpp
#include <boost/bimap.hpp>
#include <iostream>
#include <string>
int main() {
// 创建 bimap,左边是 int,右边是 string
boost::bimap<int, std::string> bm;
// 插入数据
bm.insert(boost::bimap<int, std::string>::value_type(1, "one"));
bm.insert(boost::bimap<int, std::string>::value_type(2, "two"));
bm.insert(boost::bimap<int, std::string>::value_type(3, "three"));
// 通过 int 查找 string
auto leftIt = bm.left.find(2);
if (leftIt != bm.left.end()) {
std::cout << "2 -> " << leftIt->second << "\n";
}
// 通过 string 查找 int
auto rightIt = bm.right.find("three");
if (rightIt != bm.right.end()) {
std::cout << "three -> " << rightIt->second << "\n";
}
// 遍历
std::cout << "Left view (int -> string):\n";
for (const auto& pair : bm.left) {
std::cout << " " << pair.first << " -> " << pair.second << "\n";
}
std::cout << "Right view (string -> int):\n";
for (const auto& pair : bm.right) {
std::cout << " " << pair.first << " -> " << pair.second << "\n";
}
// 使用 tagged 类型提高可读性
struct id {};
struct name {};
boost::bimap<boost::tagged<int, id>, boost::tagged<std::string, name>> taggedBm;
taggedBm.insert(boost::bimap<boost::tagged<int, id>, boost::tagged<std::string, name>>::
value_type(100, "Alice"));
auto byId = taggedBm.by<id>().find(100);
if (byId != taggedBm.by<id>().end()) {
std::cout << "ID 100: " << byId->get<name>() << "\n";
}
return 0;
}需要链接的库: libboost_bimap (通常为 header-only)
multi_index 多索引容器
Boost.Multi_index 提供了可以从多个索引访问的容器,类似于数据库表。C++23 标准库中没有类似功能。
头文件: boost/multi_index_container.hpp
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <iostream>
#include <string>
using namespace boost::multi_index;
struct Employee {
int id;
std::string name;
int age;
Employee(int i, const std::string& n, int a)
: id(i), name(n), age(a) {}
};
// 定义多索引容器
typedef multi_index_container<
Employee,
indexed_by<
ordered_unique<member<Employee, int, &Employee::id>>,
ordered_non_unique<member<Employee, std::string, &Employee::name>>,
ordered_non_unique<member<Employee, int, &Employee::age>>
>
> EmployeeContainer;
int main() {
EmployeeContainer employees;
// 插入数据
employees.insert(Employee(1, "Alice", 30));
employees.insert(Employee(2, "Bob", 25));
employees.insert(Employee(3, "Charlie", 35));
employees.insert(Employee(4, "Alice", 28)); // 同名不同人
// 通过 ID 查找(第一个索引)
auto& idIndex = employees.get<0>();
auto it = idIndex.find(2);
if (it != idIndex.end()) {
std::cout << "Found by ID: " << it->name << ", age " << it->age << "\n";
}
// 通过姓名查找(第二个索引)
auto& nameIndex = employees.get<1>();
auto nameRange = nameIndex.equal_range("Alice");
std::cout << "Employees named Alice:\n";
for (auto i = nameRange.first; i != nameRange.second; ++i) {
std::cout << " ID: " << i->id << ", age: " << i->age << "\n";
}
// 通过年龄查找(第三个索引)
auto& ageIndex = employees.get<2>();
auto ageIt = ageIndex.lower_bound(30);
std::cout << "Employees age >= 30:\n";
for (; ageIt != ageIndex.end(); ++ageIt) {
std::cout << " " << ageIt->name << ", age " << ageIt->age << "\n";
}
// 遍历所有员工
std::cout << "All employees:\n";
for (const auto& emp : employees) {
std::cout << " ID: " << emp.id << ", Name: " << emp.name
<< ", Age: " << emp.age << "\n";
}
return 0;
}需要链接的库: libboost_multi_index (通常为 header-only)
heap 优先队列
Boost.Heap 提供了多种优先队列实现,包括二叉堆、斐波那契堆等。C++23 只有 std::priority_queue,功能有限。
头文件: boost/heap/priority_queue.hpp
#include <boost/heap/priority_queue.hpp>
#include <iostream>
#include <string>
int main() {
// 使用 priority_queue(二叉堆)
boost::heap::priority_queue<int> pq;
// 插入元素
pq.push(5);
pq.push(3);
pq.push(8);
pq.push(1);
pq.push(4);
std::cout << "Priority queue size: " << pq.size() << "\n";
std::cout << "Top element: " << pq.top() << "\n";
// 弹出元素
while (!pq.empty()) {
std::cout << "Pop: " << pq.top() << "\n";
pq.pop();
}
// 使用自定义比较器
auto cmp = [](const std::string& a, const std::string& b) {
return a.length() < b.length(); // 按长度排序
};
boost::heap::priority_queue<std::string, boost::heap::compare<decltype(cmp)>>
strPq(cmp);
strPq.push("hello");
strPq.push("hi");
strPq.push("hey there");
strPq.push("a");
std::cout << "\nString priority queue (by length):\n";
while (!strPq.empty()) {
std::cout << "Pop: " << strPq.top() << "\n";
strPq.pop();
}
// 使用 fibonacci_heap(更好的合并性能)
boost::heap::fibonacci_heap<int> fibHeap;
fibHeap.push(10);
fibHeap.push(20);
fibHeap.push(5);
std::cout << "\nFibonacci heap top: " << fibHeap.top() << "\n";
return 0;
}需要链接的库: libboost_heap (通常为 header-only)
string_algo 字符串算法
Boost.String_algo 提供了丰富的字符串处理算法,比 STL 的字符串操作更强大。
头文件: boost/algorithm/string.hpp
#include <boost/algorithm/string.hpp>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string text = " Hello, World! ";
// 大小写转换
std::string upper = boost::to_upper_copy(text);
std::string lower = boost::to_lower_copy(text);
std::cout << "Upper: " << upper << "\n";
std::cout << "Lower: " << lower << "\n";
// 去除空白
std::string trimmed = boost::trim_copy(text);
std::cout << "Trimmed: " << trimmed << "\n";
// 查找和替换
std::string replaced = boost::replace_all_copy(text, "World", "Boost");
std::cout << "Replaced: " << replaced << "\n";
// 查找子串
if (boost::contains(text, "Hello")) {
std::cout << "Contains 'Hello'\n";
}
// 检查前缀和后缀
if (boost::starts_with(text, " ")) {
std::cout << "Starts with spaces\n";
}
if (boost::ends_with(text, " ")) {
std::cout << "Ends with spaces\n";
}
// 分割字符串
std::string data = "apple,banana,orange";
std::vector<std::string> fruits;
boost::split(fruits, data, boost::is_any_of(","));
std::cout << "Fruits:\n";
for (const auto& fruit : fruits) {
std::cout << " " << fruit << "\n";
}
// 连接字符串
std::string joined = boost::join(fruits, ";");
std::cout << "Joined: " << joined << "\n";
// 删除字符
std::string removed = boost::erase_all_copy(text, " ");
std::cout << "Removed spaces: " << removed << "\n";
// 查找第N个位置
std::string str = "a-b-c-d-e";
size_t pos = boost::find_nth(str, "-", 2).begin() - str.begin();
std::cout << "3rd '-' at position: " << pos << "\n";
// 查找所有匹配
std::vector<boost::iterator_range<std::string::iterator>> matches;
boost::find_all(matches, str, "-");
std::cout << "Found " << matches.size() << " '-' characters\n";
return 0;
}需要链接的库: libboost_algorithm (通常为 header-only)
tokenizer 字符串分词器
Boost.Tokenizer 提供了灵活的字符串分词功能,支持多种分词策略。
头文件: boost/tokenizer.hpp
#include <boost/tokenizer.hpp>
#include <iostream>
#include <string>
int main() {
// 使用字符分隔符
std::string str1 = "Hello,World,Boost,C++";
boost::char_separator<char> sep(",");
boost::tokenizer<boost::char_separator<char>> tokens1(str1, sep);
std::cout << "Character separator:\n";
for (const auto& token : tokens1) {
std::cout << " " << token << "\n";
}
// 使用空格分隔(跳过连续空格)
std::string str2 = "Hello World Boost";
boost::char_separator<char> space_sep(" ", "", boost::drop_empty_tokens);
boost::tokenizer<boost::char_separator<char>> tokens2(str2, space_sep);
std::cout << "\nSpace separator (drop empty):\n";
for (const auto& token : tokens2) {
std::cout << " " << token << "\n";
}
// 使用 escaped_list_separator(类似 CSV)
std::string str3 = "1,\"Hello, World\",3.14";
boost::escaped_list_separator<char> els("\\", ",", "\"");
boost::tokenizer<boost::escaped_list_separator<char>> tokens3(str3, els);
std::cout << "\nEscaped list separator (CSV-like):\n";
for (const auto& token : tokens3) {
std::cout << " " << token << "\n";
}
// 使用 offset_separator(固定宽度)
std::string str4 = "1234567890";
int offsets[] = {3, 3, 4};
boost::offset_separator off_sep(offsets, offsets + 3);
boost::tokenizer<boost::offset_separator> tokens4(str4, off_sep);
std::cout << "\nOffset separator (fixed width):\n";
for (const auto& token : tokens4) {
std::cout << " " << token << "\n";
}
return 0;
}需要链接的库: libboost_tokenizer (通常为 header-only)
xpressive 正则表达式
Boost.Xpressive 提供了静态和动态正则表达式支持,比 Boost.Regex 更灵活。
头文件: boost/xpressive/xpressive.hpp
#include <boost/xpressive/xpressive.hpp>
#include <iostream>
#include <string>
using namespace boost::xpressive;
int main() {
// 静态正则表达式(编译时检查)
sregex static_num = +_d; // 一个或多个数字
sregex static_email = (alpha >> *(alnum | '_' | '.' | '-') >> '@' >>
+(alnum | '.' | '-'));
std::string text1 = "12345";
std::string text2 = "user@example.com";
if (regex_match(text1, static_num)) {
std::cout << "Text1 is a number\n";
}
if (regex_match(text2, static_email)) {
std::cout << "Text2 is an email\n";
}
// 动态正则表达式(运行时构建)
sregex dynamic = sregex::compile("\\d{3}-\\d{4}");
std::string phone = "123-4567";
if (regex_match(phone, dynamic)) {
std::cout << "Phone number matches\n";
}
// 搜索和替换
std::string content = "Hello 123, World 456, Test 789";
sregex pattern = _d >> _d >> _d; // 三位数字
smatch what;
std::string::const_iterator it = content.begin();
std::string::const_iterator end = content.end();
std::cout << "\nFound numbers:\n";
while (regex_search(it, end, what, pattern)) {
std::cout << " " << what[0] << " at position "
<< (what[0].first - content.begin()) << "\n";
it = what[0].second;
}
// 替换
std::string replaced = regex_replace(content, pattern, "XXX");
std::cout << "\nAfter replacement: " << replaced << "\n";
// 捕获组
std::string date = "2024-01-18";
sregex date_pattern = (s1 = _d >> _d >> _d >> _d) >> '-' >>
(s2 = _d >> _d) >> '-' >>
(s3 = _d >> _d);
smatch date_match;
if (regex_match(date, date_match, date_pattern)) {
std::cout << "\nDate parts:\n";
std::cout << " Year: " << date_match[s1] << "\n";
std::cout << " Month: " << date_match[s2] << "\n";
std::cout << " Day: " << date_match[s3] << "\n";
}
return 0;
}需要链接的库: libboost_xpressive (通常为 header-only)
lockfree 无锁数据结构
Boost.Lockfree 提供了无锁队列、栈等数据结构,用于高并发场景。C++23 标准库中没有类似功能。
头文件: boost/lockfree/queue.hpp
#include <boost/lockfree/queue.hpp>
#include <boost/lockfree/stack.hpp>
#include <iostream>
#include <thread>
#include <vector>
int main() {
// 无锁队列
boost::lockfree::queue<int> q(100); // 固定大小
// 生产者线程
auto producer = [&]() {
for (int i = 0; i < 1000; ++i) {
while (!q.push(i)) {
// 队列满,重试
}
}
};
// 消费者线程
std::atomic<int> sum{0};
auto consumer = [&]() {
int value;
while (true) {
if (q.pop(value)) {
sum += value;
} else {
// 队列空,检查是否完成
if (sum.load() >= 499500) { // 0+1+...+999 = 499500
break;
}
}
}
};
std::thread t1(producer);
std::thread t2(consumer);
t1.join();
t2.join();
std::cout << "Sum: " << sum << "\n";
// 无锁栈
boost::lockfree::stack<int> s(100);
for (int i = 0; i < 10; ++i) {
s.push(i);
}
std::cout << "Stack contents:\n";
int value;
while (s.pop(value)) {
std::cout << value << " ";
}
std::cout << "\n";
return 0;
}需要链接的库: libboost_lockfree (通常为 header-only)
pool 内存池
Boost.Pool 提供了高性能的内存池实现,适用于频繁分配/释放小对象的场景。
头文件: boost/pool/object_pool.hpp
#include <boost/pool/object_pool.hpp>
#include <iostream>
#include <vector>
class Node {
public:
int value;
Node* next;
Node(int v) : value(v), next(nullptr) {}
~Node() { std::cout << "Node " << value << " destroyed\n"; }
};
int main() {
// object_pool - 对象池
boost::object_pool<Node> nodePool;
std::cout << "Creating nodes from pool:\n";
Node* n1 = nodePool.construct(1);
Node* n2 = nodePool.construct(2);
Node* n3 = nodePool.construct(3);
n1->next = n2;
n2->next = n3;
std::cout << "Nodes linked: " << n1->value << " -> "
<< n1->next->value << " -> " << n2->next->value << "\n";
// 手动释放
nodePool.destroy(n1);
nodePool.destroy(n2);
nodePool.destroy(n3);
std::cout << "\nCreating more nodes:\n";
std::vector<Node*> nodes;
for (int i = 0; i < 1000; ++i) {
nodes.push_back(nodePool.construct(i));
}
std::cout << "Pool memory used: " << nodePool.get_memory_usage() << "\n";
std::cout << "Pool size: " << nodePool.get_free_count() << "\n";
// 清空池
nodes.clear();
nodePool.purge_memory();
std::cout << "After purge, free count: " << nodePool.get_free_count() << "\n";
return 0;
}需要链接的库: libboost_pool (通常为 header-only)
lexical_cast 类型转换
Boost.Lexical_cast 提供了类似 Python 的类型转换功能。
头文件: boost/lexical_cast.hpp
#include <boost/lexical_cast.hpp>
#include <iostream>
#include <string>
#include <vector>
int main() {
// 字符串转数字
std::string strNum = "123";
int num = boost::lexical_cast<int>(strNum);
std::cout << "String to int: " << num << "\n";
double d = boost::lexical_cast<double>("3.14159");
std::cout << "String to double: " << d << "\n";
// 数字转字符串
int n = 456;
std::string str = boost::lexical_cast<std::string>(n);
std::cout << "Int to string: " << str << "\n";
// 其他类型转换
bool b = boost::lexical_cast<bool>("true");
std::cout << "String to bool: " << std::boolalpha << b << "\n";
// 容器转换
std::vector<int> vec = boost::lexical_cast<std::vector<int>>("[1,2,3,4,5]");
std::cout << "Vector from string: ";
for (int v : vec) {
std::cout << v << " ";
}
std::cout << "\n";
// 自定义类型的转换
struct Point {
int x, y;
};
try {
Point p = boost::lexical_cast<Point>("(10,20)");
std::cout << "Point: (" << p.x << ", " << p.y << ")\n";
} catch (const boost::bad_lexical_cast& e) {
std::cout << "Conversion failed: " << e.what() << "\n";
}
return 0;
}需要链接的库: libboost_lexical_cast (通常为 header-only)
总结
| 库 | 功能 | 需要链接的动态库 |
|---|---|---|
| timer | 计时器 | libboost_timer, libboost_chrono |
| algorithm/string | 字符串分割、处理 | libboost_algorithm (header-only) |
| circular_buffer | 环形缓冲区 | libboost_circular_buffer (header-only) |
| bimap | 双向映射 | libboost_bimap (header-only) |
| multi_index | 多索引容器 | libboost_multi_index (header-only) |
| heap | 优先队列 | libboost_heap (header-only) |
| lockfree | 无锁数据结构 | libboost_lockfree (header-only) |
| string_algo | 字符串算法 | libboost_algorithm (header-only) |
| tokenizer | 字符串分词器 | libboost_tokenizer (header-only) |
| xpressive | 正则表达式 | libboost_xpressive (header-only) |
| pool | 内存池 | libboost_pool (header-only) |
| lexical_cast | 类型转换 | libboost_lexical_cast (header-only) |
注意: 标记为 “header-only” 的库通常不需要链接动态库,直接包含头文件即可使用。但某些情况下可能仍需要链接 libboost_system 等基础库。




