C++ STL中的multiset insert()函数

multiset是C++ STL提供的一个关联式容器，它的特点是会根据元素的键值自动进行排序，同时可以保存重复的元素。insert()函数是multiset中常用的一个函数，它可以向multiset中插入一个新元素。

multiset的定义和特点

multiset定义方式如下：

std::multiset<int> myset;

multiset的特点如下:

• 自动排序：multiset会根据元素的键值自动排序，从小到大排列。
• 可以保存重复元素
• 不可以使用下标符号[]来访问元素

例如，我们可以通过如下方法插入若干个元素：

multiset<int> myset;
myset.insert(1);
myset.insert(2);
myset.insert(3);
myset.insert(3);
myset.insert(4);
myset.insert(5);

输出结果如下：

1 2 3 3 4 5

从结果中可以看到，multiset会将元素自动排序，并且可以保存重复元素。

insert()函数的基本使用

insert()函数的定义如下：

iterator insert (const value_type& val);
iterator insert (iterator position, const value_type& val);
template <class InputIterator>
  void insert (InputIterator first, InputIterator last);

下面分别介绍这三种使用方法。

插入一个元素

我们可以使用如下方法，插入单个元素：

multiset<int> myset;
myset.insert(1);

插入一个元素到指定位置

我们可以使用如下方法，插入单个元素到指定位置：

multiset<int> myset;
auto it = myset.insert(2);
myset.insert(it, 1);

输出结果如下：

1 2

插入多个元素

我们可以使用如下方法，插入多个元素：

multiset<int> myset;
std::vector<int> vec{1, 2, 3, 3, 4, 5};
myset.insert(vec.begin(), vec.end());

输出结果如下：

1 2 3 3 4 5

insert()函数的返回值

insert()函数的返回值是一个迭代器，它指向新插入的元素。如果是插入多个元素，则返回最后一个元素的迭代器。

auto it = myset.insert(1);

上面的代码中，it为一个指向新插入的元素1的迭代器。

multiset<int> myset;
std::vector<int> vec{1, 2, 3, 3, 4, 5};
auto it = myset.insert(vec.begin(), vec.end());

上面的代码中，it为一个指向插入的最后一个元素5的迭代器。

性能分析

insert()函数在multiset中的插入是O(log n)的时间复杂度。

结论

insert()函数是multiset中常用的一个函数，可以向multiset中插入单个元素或多个元素，并且返回一个指向新插入元素的迭代器。使用insert()函数插入元素的时间复杂度是O(log n)。