Cao Lin's Blog.

CPP set 简介

C++ 剑指offer
Word count: 654Reading time: 3 min
2020/04/02 Share

主要是记一些理解之内的东西，没理解的东西，记下来也没用，这是一个初步的总结。

更加详细的信息参考cplusplus.com

1、题目：

剑指offer

找出数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

  • 输入：
1
[2, 3, 1, 0, 2, 5, 3]
  • 输出：
1
2 或 3
  • 限制：
1
2 <= n <= 100000
我的解决方案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        set<int> s;
        for (auto i : nums)
        {
            if (!s.insert(i).second)
            {
                return i;
            }
        }
        return -1;
    }
};
/*
执行用时 :148 ms, 在所有 C++ 提交中击败了6.67% 的用户
内存消耗 :28.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/

直接使用set的insert()方法来进行判断当前插入的值是否已经存在，然后就此总结一下set的相关用法。

2、关于set

2.1、Overview and feature

  • Sets are containers that store unique elements following a specific order.

  • In a set, the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. The value of the elements in a set cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.

  • Internally, the elements in a set are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

  • set containers are generally slower than unordered_set containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

  • Sets are typically implemented as binary search trees.

2.2、 Member functions

Iterators:

  • begin

    Return iterator to beginning (public member function )

  • end

    Return iterator to end (public member function )

  • rbegin

    Return reverse iterator to reverse beginning (public member function )

  • rend

    Return reverse iterator to reverse end (public member function )

  • cbegin

    Return const_iterator to beginning (public member function )

  • cend

    Return const_iterator to end (public member function )

  • crbegin

    Return const_reverse_iterator to reverse beginning (public member function )

  • crend

    Return const_reverse_iterator to reverse end (public member function )

Capacity:

  • empty

    Test whether container is empty (public member function )

  • size

    Return container size (public member function )

  • max_size

    Return maximum size (public member function )

Modifiers:

  • insert

    Insert element (public member function )

  • erase

    Erase elements (public member function )

  • swap

    Swap content (public member function )

  • clear

    Clear content (public member function )

  • emplace

    Construct and insert element (public member function )

  • emplace_hint

    Construct and insert element with hint (public member function )

Observers:

  • key_comp

    Return comparison object (public member function )

  • value_comp

    Return comparison object (public member function )

Operations:

  • find

    Get iterator to element (public member function )

  • count

    Count elements with a specific value (public member function )

  • lower_bound

    Return iterator to lower bound (public member function )

  • upper_bound

    Return iterator to upper bound (public member function )

  • equal_range

    Get range of equal elements (public member function )

Allocator:

Author：Cao Lin

原文链接：http://www.cao-lin.top/2020/04/02/std-set%E7%9A%84%E7%94%A8%E6%B3%95%E5%88%9D%E6%AD%A5%E6%80%BB%E7%BB%93/

发表日期：April 2nd 2020, 2:57:22 pm

更新日期：April 13th 2020, 10:23:10 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1、题目：
    1. 1.1. 找出数组中重复的数字
    2. 1.2. 我的解决方案
  2. 2. 2、关于set
    1. 2.1. 2.1、Overview and feature
    2. 2.2. 2.2、 Member functions
Total : 11
Invalid date
2020
Invalid date
Invalid date
2020
Invalid date
2020
C++ 剑指offer python 视觉SLAM