[#STL使用] #cpp #STL

algorithm.md

不改变元素的算法

不改变元素的算法既不改变元素的顺序，又不改变元素的值.这些算法操作forward迭代器和input迭代器，所以，这类算法适用于所有标准的容器。

常见的算法

• for_each() 对容器中的某个元素执行某个操作。
• count() 返回元素的个数
• count_if() 返回某个标准的元素的个数
• min_element() 返回最小的元素
• max_element() 返回最大的元素
• minmax_element() 返回最小和最大的元素
• find() 找到集合中的第一元素
• find_if() 找到适合某个标准的第一个元素
• find_if_not() 找到不适合标准的第一个元素
• search_n() 找到满足某一性质的连续的几个元素
• search(ForwardIt1 first, ForwardIt1 last,ForwardIt2 s_first, ForwardIt2 s_last) 找到某个范围第一次出现的位置
• find_end(ForwardIt1 first, ForwardIt1 last,ForwardIt2 s_first, ForwardIt2 s_l) 找到某个子范围元素最后出现的位置
• find_first_of()
• adjacent_find()
• equal() 判断两个range的元素是否相等。
• is_permutation()
• mismatch() 返回两个序列中不匹配的第一个元素
• is_sorted() 返回所有的元素是否排序
• is_sorted_until()
• is_partitioned()
• partition_point()
• is_heap()
• is_heap_until()
• all_of() 返回是否所有的元素满足某个条件。
• any_of() 返回元素中，是否有满足条件的元素。
• none_of() 返回元素中是否有元素不满足标准。

典型算法的使用

std::vector<int> v = {1,2,3,4,5};
std::fill_n(v.begin(),5,-1); //先前5个换成-1 , 现在就是-1,-1,-1,-1,-1; 参数是输出迭代器
std::fill(v.begin(),v.end(),1); //现在变成了1,1,1,1,1 注意参数是前向迭代器。
std::for_each(v.begin(),v.end(),[](int &n) {
    n++;
}); //这里的迭代器是输入迭代器，现在变成了2，2，2，2，2.
std::count(v.begin(),v.end(),2); //输出5 ,这里也是输入迭代器。
std::find(v.begin(),v.end(),2);

// for_range的使用

include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {0, 1, 2, 3, 4, 5};
 
    for (const int &i : v) // access by const reference
        std::cout << i << ' ';
    std::cout << '\n';
 
    for (auto i : v) // access by value, the type of i is int
        std::cout << i << ' ';
    std::cout << '\n';
 
    for (auto&& i : v) // access by reference, the type of i is int&
        std::cout << i << ' ';
    std::cout << '\n';
 
    for(int n : {0,1,2,3,4,5}) // the initializer may be a braced-init-list
        std::cout << n << ' ';
    std::cout << '\n';
}

改变元素的算法

• for_each() 对集合中的某个元素执行操作
• copy() 将某个集合中的元素复制到另一个元素集合中。
• copy_if() 复制集合中满足某个条件的元素到另一个集合中
• copy_n() 从集合1中赋值n个元素到另一个集合中
• copy_backward()
• move()
• move_backward()
• transform() 讲一个操作作用于一个范围，把结果存在另一个范围
• merge() 合并两个集合，前提是已经排序好了。
• swap_ranges() 交换两个集合的元素
• fill() 用给定的值，替换所指范围内所有的元素
• fill_n() 用给定的值，来替换所指范围内的n个元素
• generate() 用某个操作的结果来替换集合中的元素
• generate_n()
• replace() 用给定的值替换指定集合中的某个元素
• replace_if() 替换满足某个条件的所有元素。
• replace_copy() 替换某个元素，并且复制整个集合。
• replace_copy_if() 替换某个条件的元素，并且复制整个元素的集合。

删除元素的算法

• remove() 删除在指定范围内给定值的元素
• remove_if() 删除在指定范围内符合某个标准的元素
• remove_copy() 复制元素的值到另一个集合中，忽略掉给定的值
• remove_copy_if() 复制集合中的值到另一个集合中，忽略掉元素不符合标准的值。
• unique() 删除指定范围内中重复的相邻元素，比如1,2,2,2,3,3,3,运行后就是1,2,3
• unique_copy() 复制指定范围内的元素，如果相邻的元素是重复的，只复制一个。

注意到这些删除元素的算法，不会改变以前容器的大小，以前是4个元素，删除元素后，仍然是4个。相反，它们返回的是新的范围的结束迭代器。对于要复制元素到另一个集合中去的时候，你不能够将关联容器和非排序的容器作为目标范围。

#include <iostream>
int main() {
	std::list<int> a = { 1, 2, 2, 4 };
        
        //返回的是删除后，新的结束迭代器
	std::list<int>::iterator last_it = std::remove_if(a.begin(), a.end(), [](const int &elem){
		return elem == 2;
	});

	for (auto it = a.begin(); it != last_it; it++) {
		std::cout << *it;
	}
       //容器的大小没有改变。
	std::cout << "the size is " << a.size();
 }

改变容器元素顺序的算法

这些算法同样不能够用关联容器好非排序的容器作为目标范围。

• reverse() 将所给范围的值逆序。
• reverse_copy() 将所给范围内的值，以逆序的方式付给目标的范围
• rotate() 对给定范围内的元素执行左旋转
• rotate_copy()
• next_permutation() 对当前的范围[first,last),进行下一轮的排序，如果有，则返回true
• prev_permutation()
• shuffle() 对元素进行随机的顺序进行排列
• random_shuffle()
• partition() 按照某种标准来划分元素，符合标准的在集合的前面。但是元素的相对顺序并没有保存。
• stable_partition() 按照某种标准来划分元素，符合标准的在集合的前面。但是元素的相对顺序得到保存。
• partition_copy()

排序算法

• sort() 对所给的范围进行排序
• stable_sort() 对所给的范围进行排序，想等的元素的顺序能够保持
• partial_sort()
• partial_sort_copy()
• nth_element()
• partition() 按照某种标准来划分元素，符合标准的在集合的前面。但是元素的相对顺序并没有保存
• stable_partition()
• partition_copy()
• make_heap() 将一个范围的元素转成堆。
• push_heap() 将元素添加到堆。
• pop_heap() 删除堆中的元素。
• sort_heap() 对堆进行排序，之后，已经不是堆了。

hash_map

• https://gcc.gnu.org/onlinedocs/gcc-4.7.1/libstdc++/api/a00047.html

effective stl.md

/ 对结构体的排序
struct data {
    string word;
    int number;

    bool operator<(const data& a) const
    {
        return word.size() < a.word.size();
    }
};
// 从小到大排序
std::sort(data.begin(), data.end());
std::sort(data.rbegin(), data.rend()); // 从大到小排序

注意在operator < 实现的时候，相等的元素传进来，一定要返回false，否则会core dump。

• https://stackoverflow.com/questions/39933036/core-dump-when-using-stdsort

std::unique

用来删除连续的几个相同的元素。

int main() 
{
    // remove duplicate elements (normal use)
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
    v.erase(last, v.end()); 
    for (int i : v)
      std::cout << i << " ";
    std::cout << "\n";
 
    // remove consecutive spaces
    std::string s = "wanna go    to      space?";
    auto end = std::unique(s.begin(), s.end(), [](char l, char r){
        return std::isspace(l) && std::isspace(r) && l == r;
    });
    // s now holds "wanna go to space?xxxxxxxx", where 'x' is indeterminate
    std::cout << std::string(s.begin(), end) << '\n';
}

std::inserted

// std::inserter的使用
// std::inserter可以返回一个Output iterator 
// std::inserter(Container& x, typename Container::iterator it);
// x: Container in which new elements will  be inserted.

// it: Iterator pointing to the insertion point.
// Returns: An insert_iterator that inserts elements into x at the position indicated by it.
// C++ program to demonstrate std::inserter
// 注意inserter能够只能够用于包含insert方法的容器，也就是vector，deque,  list

// Declaring first container
deque<int> v1 = { 1, 2, 3 };

// Declaring second container for
// copying values
deque<int> v2 = { 4, 5, 6 };

deque<int>::iterator i1;
i1 = v2.begin() + 1;
// i1 points to next element of 4 in v2

// Using std::inserter inside std::copy
std::copy(v1.begin(), v1.end(),  std::inserter(v2, i1));
// v2 now contains 4 1 2 3 5 6
// Displaying v1 and v2
cout << "v1 = ";

int i;
for (i = 0; i < 3; ++i) {
  cout << v1[i] << " ";
}

cout << "\nv2 = ";
for (i = 0; i < 6; ++i) {
  cout << v2[i] << " ";
}
return 0;

set.md

插入

int main()
{
  std::set<int> set;
 
  auto result_1 = set.insert(3);
  assert(result_1.first != set.end()); // it's a valid iterator
  assert(*result_1.first == 3);
  if (result_1.second)
    std::cout << "insert done\n";
 
  auto result_2 = set.insert(3);
  assert(result_2.first == result_1.first); // same iterator
  assert(*result_2.first == 3);
  if (!result_2.second)
    std::cout << "no insertion\n";
}

交集

 std::set<std::string> res;
 std::set_intersection(matched_game_id.begin(),
                       matched_game_id.end(),
                        hash_map[tag].begin(),
                        hash_map[tag].end(),
                        std::inserter(res, res.begin()));

• 交集注意这两个集合都必须有序

string.md

substr

获取子字符串。

 std::string a = "0123456789abcdefghij";
 
    // count is npos, returns [pos, size())
    std::string sub1 = a.substr(10);
    std::cout << sub1 << '\n';
 
    // both pos and pos+count are within bounds, returns [pos, pos+count)
    std::string sub2 = a.substr(5, 3);
    std::cout << sub2 << '\n';
 
    // pos is within bounds, pos+count is not, returns [pos, size()) 
    std::string sub4 = a.substr(a.size()-3, 50);
    std::cout << sub4 << '\n';
 
    try {
        // pos is out of bounds, throws
        std::string sub5 = a.substr(a.size()+3, 50);
        std::cout << sub5 << '\n';
    } catch(const std::out_of_range& e) {
        std::cout << "pos exceeds string size\n";
    }

vec.md

vector大小和容量

Vector提供了size()，和max_size()，capacity()函数来提供元素的个数的功能。其中，capacity这个函数用来返回Vector实际能够容纳的元素的个数。一个Vector的容量很重要的原因如下：

• 重新分配Vector的内存将使得容器元素的引用，指针(指向该地址)，迭代器失效。
• 重新分配内存将耗费更多的时间。

导致重新分配内存的代码:

int main(int argc, char *argv[]) {
    int data[] = { 1, 2, 3 };
    std::vector vec(data, data + 3);
    // vector contains 1, 2, 3
    std::vector::iterator i = vec.begin();
    cout << *i << endl; // prints 1
    int &ref = *i;
    cout << ref << endl; // prints 1
    vec.resize(6, 99);
    // vector now contains 1, 2, 3, 99, 99, 99
    // WRONG! may crash, may do the wrong thing, might work...
    // cout << *i << endl;
    // WRONG! invalid reference
    // cout << ref << endl;
    return 0;
}

避免重新分配内存

有两种方法

std::vector<int> v ; 创建一个空的vector
v.reserve(80); //至少有80个元素的空间
//或者是 
std::vector<int> v(5);  //至少5个值