c++容器与算法概述

容器与算法

• 每个标准库容器都提供了begin() end() 函数，分别返回容器的头部位置和尾部位置。

I/O 流

对于自定义的类型：

struct Entry {
    std::string name;
    int number;
    
};
1
2
3
4
5

如果需要使用标准输出需要重载<< 运算符，特别注意： 这个函数不是定义在Entry 类型内部的， 形式如下：

// 定义entry 类的输出函数，重载operator<<
std::ostream& operator<<(std::ostream& os, const Entry& e) {
        return os<<"{\"" << e.name << "\"," << e.number<< "}";
}
1
2
3
4

对于自定义类型，如果需要使用sort 算法函数，需要重载比较运算符<, 否则会编译报错：

// 只有定义了比较运算符，才能使用sort 进行排序，否则编译会报：
bool operator<(const Entry& a, const Entry& b) {
	return a.number <= b.number;
}
1
2
3
4

测试代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include "config.h"
#include "entry.h"

int main(int argc, char **argv) {
	std::vector<Entry> mEntries;
	mEntries.push_back({"zhangsan", 1});
	mEntries.push_back({"lisi", 2});
	mEntries.push_back({"wangwu", 3});
	std::sort(mEntries.begin(), mEntries.end());
	for(const auto & entry : mEntries) {
		std::cout<< "entry: " << entry << std::endl;
	}

	// use operator << of struct Entry
	// std::cout << "chapter4 entry: " << entry << std::endl;;
	std::cout << "Version " << chapter4_VERSION_MAJOR << "." << chapter4_VERSION_MINOR << std::endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

容器

• 目的是保存一些对象

• vector

  • 是元素类型为T 的容器
  • 不进行范围检查

• list

  • 双向链表

• list & vector

  • 当数据量教小时，vector 的性能会优于list

• map 关联数组或字典 通常用平衡二叉树实现。

  • 值对的容器
  • 支持下标操作，下标是key， 返回的是value， 本质是一次查找动作
  • 搜索map 的时间代价是O(log(n))

• unordered_map 哈希容器 “无序” 容器

• 容器类大多提供了： begin() end() push_back, size() 等函数。

• 使用标准库， 同我们大多数自己实现的库函数类似，需要平衡效率等，斟酌使用。

算法

• 对于容器类，find() 函数通过返回end() 来表示未找到

find(s.begin(), s.end()， c) != s.end()  用来判断在s 中是否查找到c

1
2

迭代器

• 对于使用迭代器的场合

  for (auto p : s) {

  }
  // 此时的auto p 需要根据使用场合来确定是否使用const &
  // (1) for (const auto& p : s)  只会读取，不会进行拷贝，也不会修改s 中的元素
  // (2) for (const auto p : s)  需要拷贝元素，但不可修改拷贝出来的值
  // (3) for (auto p : s)  拷贝一份s元素，而不会改变s中元素
  // (4) for (auto& p : s)  不会拷贝一份s 元素， 可以修改s 中的元素

  
1
2
3
4
5
6
7
8
9
10

• 返回迭代器

const std::vector<std::string::iterator> find_all(std::string&s, char c) {
	std::vector<std::string::iterator> res;
	for (auto p = s.begin(); p != s.end(); ++p) {
		if (*p == c) {
			res.push_back(p);
		}
	}
	return res;
}
1
2
3
4
5
6
7
8
9

• 使用模板
  • 迭代器 和标准算法库在所有标准库容器上的工作方式是相同的，所以可以对于迭代起的使用进行泛化

// 使用模板
// 需要注意iterator 的声明方式，前面有个typename
template<typename C, typename V>
std::vector<typename C::iterator> find_all(C& s, V v) {
	std::vector<typename C::iterator> res;
	for (auto p = s.begin(); p != s.end(); ++p) {
		if (*p == v) {
			res.push_back(p);
		}
	}
	return res;
}

如果觉得typename C::iterator 方式太丑， 可以采用如下形式
template<typename T>
using Iterator = typename T::iterator; // T  的迭代器
// P90 使用的是
// using Iterator<T> = typename T::iterator; // T  的迭代器 , 编译不过？？
template<typename C, typename V>
std::vector<Iterator<C>> find_all(C& s, V v) {
	std::vector<Iterator<C>> res;
	for (auto p = s.begin(); p != s.end(); ++p) {
		if (*p == v) {
			res.push_back(p);
		}
	}
	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• baidu 的时候，发现可以使用typedef 给类型其别名：

template<typename T>
typedef typename T::iterator Iterator;
1
2

但是发现会编译失败：

• baidu 的解释 以及解决办法
  

• 综上， 在使用模板的时候，还是老实的使用“using" 进行重命名吧

算法概述

• 算法提供了很多有用的方法， find count, replace (居然还有这个接口)