文先生的博客 求职，坐标深圳。（wenfh2020@126.com）

stl 基础知识

2018-02-12
c/c++

主要对旧知识对温习和知识盲点的记录。

1. list

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

/* g++ -g -O0 -std=c++11 test_list.cpp -o test && ./test */
#include <iostream>
#include <list>

int main() {
    int i = 0;
    std::list<int> ls;

    for (i = 0; i < 10; i++) {
        ls.push_back(i);
    }
    std::cout << "cnt: " << ls.size() << std::endl;

    auto it = ls.begin();
    for (; it != ls.end() && i < 5;) {
        ls.erase(it++);
        i++;
    }

    for (auto v : ls) {
        std::cout << v << std::endl;
    }
    return 0;
}

2. set

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

/* g++ -g -O0 -std=c++11 test_set.cpp -o test && ./test */
#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    s.insert(1);
    s.insert(3);
    s.insert(2);
    auto ret = s.insert(1);
    if (!ret.second) {
        std::cout << "duplicate, data: " << *ret.first << std::endl;
    }
    auto it = s.find(2);
    if (it != s.end()) {
        std::cout << "find data: " << *it << std::endl;
        s.erase(it);
    }
    s.erase(3);
    std::cout << "size: " << s.size() << std::endl;
    for (auto v : s) {
        std::cout << v << std::endl;
    }
    return 0;
}

3. map

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/* g++ -g -O0 -std=c++11 test_map.cpp -o test && ./test */
#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m;

    m.insert(std::pair<int, std::string>(1, "1"));
    m.insert(std::pair<int, std::string>(2, "2"));
    auto ret = m.insert({1, "1"});
    if (!ret.second) {
        std::cout << "insert failed! key: " << ret.first->first << std::endl;
    }

    m[1] = "2";
    std::cout << "replace: " << m[1] << std::endl;
    for (auto it : m) {
        std::cout << it.first << " " << it.second << std::endl;
    }

    m[1] = "1";
    m[2] = "2";
    m[3] = "3";
    m[4] = "4";
    m[5] = "5";
    auto f = m.find(4);
    if (f != m.end()) {
        m.erase(f);
    }
    m.erase(5);

    m[6] = "6";
    m[7] = "7";
    /* 返回 map 中第一个大于或等于 key 的迭代器指针。 */
    auto l = m.lower_bound(6);
    if (l != m.end()) {
        std::cout << "lower_bound: " << l->first << std::endl;
    }

    /* 返回 map 中第一个大于 key 的迭代器指针。 */
    auto u = m.upper_bound(6);
    std::cout << "upper_bound: " << u->first << std::endl;

    std::cout << "reverse: " << std::endl;
    auto it = m.rbegin();
    for (; it != m.rend(); it++) {
        std::cout << it->first << std::endl;
    }
    return 0;
}

4. vector

4.1. 动态内存

vector 容器内部是动态内存管理，当分配的内存使用完后，不得不重新分配新的内存：以 加倍当前容量 的分配策略实现重新分配。

因为动态内存分配数组，数组内部会根据内容输入的容量增长，不断重新分配内存，将旧内容拷贝到新内存，频繁的内存申请和数据拷贝，会出现效率问题，所以如果数组要连续输入数量比较多的内容，可以通过 reserve （或者 resize）接口为目标数据预分配足够的空间，这样，数组在操作过程中，就不会频繁进行内存的重新分配，导致效率低下。

接口 解析
capacity 当前容器容量，capacity 增长的策略不同的平台下，情况不一样，mac 和 centos 就不一样。
size 当前数据长度。
reserve 根据目标数据告诉容器应该预留多少个元素的存储空间，影响 capacity。
resize 调整当前数据大小，对数据有初始化功能；小于那么 capc 不变，大于capc 要改变，当resize 大小有改变且大于当前 capacity，那么 capacity 会加倍增长。 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
#include <vector>

const int g_array_len = 612;
using namespace std;

void traversal(int len) {
    vector<int> v;
    for (int i = 0; i < len; i++) {
        v.push_back(i);
        printf("data: %d, size: %lu, capc: %lu\n", v[i], v.size(), v.capacity());
    }
}

void reserve(int len) {
    vector<int> v;
    v.reserve(len);
    for (int i = 0; i < len; i++) {
        v.push_back(i);
        printf("data: %d, size: %lu, capc: %lu\n", v[i], v.size(), v.capacity());
    }
}

void resize(int len) {
    vector<int> v;
    v.reserve(len);
    printf("vector size: %lu, capc: %lu\n", v.size(), v.capacity());
    v.resize(len+1, 5);
    printf("vector size: %lu, capc: %lu\n", v.size(), v.capacity());
    printf("v[%d] = %d\n", len+1, v[len+1]);
}

int main() {
    // 可以通过遍历数据，观察 vector 内部的内存分配情况。
    // traversal(g_array_len);

    // 预分配容器容量，观察容器内部的内存分配情况。
    // reserve(g_array_len);

    // 预分配容器容量，目标数据超出容量，观察容器内部的内存分配情况。
    // reserve(g_array_len + 1);

    resize(g_array_len);
    return 0;
}

4.2. 排序

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

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    int n;
    std::string s;
    std::vector<std::string> words;

    std::cin >> n;
    while (n-- > 0) {
        std::cin >> s;
        words.push_back(s);
    }

    std::sort(words.begin(), words.end());

    for (auto& v : words) {
        std::cout << v << std::endl;
    }
    return 0;
}

5. emplace 操作

容器元素的深浅拷贝是影响性能的一个比较重要的因素，c++11 某些容器增加了 emplace 功能，可以避免对象拷贝动作，提高程序性能。

我在使用容器保存自定义类或者结构体时，容器参数一般传递对象指针，这样就可以避免容器内部的深拷贝动作。容器保存 std::string 还是比较常用的操作，所以要注意 emplace 的使用。

  • 测试源码。
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <vector>

struct A {
    std::string s;

    A(std::string str) : s(std::move(str)) {
        std::cout << s << " constructed\n";
    }
    A(const A& o) : s(o.s) {
        std::cout << s << " copy constructed\n";
    }
    A(A&& o) : s(std::move(o.s)) {
        std::cout << s << " move constructed\n";
    }
    A& operator=(const A& other) {
        s = other.s;
        std::cout << s << " copy assigned\n";
        return *this;
    }
    A& operator=(A&& other) {
        s = std::move(other.s);
        std::cout << s << " move assigned\n";
        return *this;
    }
};

int main() {
    std::vector<A> objs;
    objs.reserve(16);

    A a("aa");
    objs.push_back(a);
    std::cout << std::endl;

    objs.push_back(A("bb"));
    std::cout << std::endl;

    A c("cc");
    objs.emplace_back(c);
    std::cout << std::endl;

    objs.emplace_back(A("dd"));
    std::cout << std::endl;

    objs.emplace_back("ee");
    return 0;
}
  • 结果。
1
2
3
4
5
6
7
8
9
10
11
12
13

aa constructed
aa copy constructed

bb constructed
bb move constructed

cc constructed
cc copy constructed

dd constructed
dd move constructed

ee constructed
  • 结果分析。高版本的 c++11 的 std::vector::push_back 内部封装了 emplace_back。
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
29
30
31
32
33
34
35
36
37
38
39

/// Class std::vector with safety/checking/debug instrumentation.
template<typename _Tp,
    typename _Allocator = std::allocator<_Tp> >
class vector
: public __gnu_debug::_Safe_container<
vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
    public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
    public __gnu_debug::_Safe_vector<
vector<_Tp, _Allocator>,
_GLIBCXX_STD_C::vector<_Tp, _Allocator> >
{
    ...
#if __cplusplus >= 201103L
      template<typename _Up = _Tp>
    typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
                    void>::__type
    push_back(_Tp&& __x)
    { emplace_back(std::move(__x)); }

      template<typename... _Args>
#if __cplusplus > 201402L
    reference
#else
    void
#endif
    emplace_back(_Args&&... __args)
    {
      bool __realloc = this->_M_requires_reallocation(this->size() + 1);
      _Base::emplace_back(std::forward<_Args>(__args)...);
      if (__realloc)
        this->_M_invalidate_all();
      this->_M_update_guaranteed_capacity();
#if __cplusplus > 201402L
      return back();
#endif
    }
#endif
    ...
};

6. 参考

作者公众号
微信公众号，干货持续更新~
目录

我的链接

文集

归档