C++ set insert详解

一、概述

C++中的set容器是一种基于红黑树(Red-Black Tree)的高效实现，它会自动进行排序。在set中我们可以使用insert方法向set中插入元素。set insert方法的实现非常高效，时间复杂度一般为O(logn)。下面我们将通过代码示例来详细介绍set insert的各个方面。

二、基本用法

我们首先来看set insert的基本用法。下面的代码示例中，我们创建一个set并向其中插入一些元素：

#include <set>
#include <iostream>
  
int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // set some initial values:
  for (int i=1; i<=5; ++i) myset.insert(i*10);   // set: 10 20 30 40 50

  ret = myset.insert(20);               // no new element inserted

  if (ret.second==false) it=ret.first;  // "it" now points to element 20

  myset.insert(it,25);                 // max efficiency inserting
  myset.insert(it,24);                 // max efficiency inserting
  myset.insert(it,26);                 // no max efficiency inserting

  int myints[]= {5,10,15};              // 10 already exists
  myset.insert (myints,myints+3);
  
  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

上述代码将输出：10 15 20 24 25 30 40 50。

三、insert返回值

set insert方法的返回值比较特殊，返回值实际上是一个pair，其中pair的第一个元素是一个迭代器，指向插入元素的位置，pair的第二个元素是一个bool值，表示是否插入成功。在上面的代码示例中，我们可以看到一个例子：

ret = myset.insert(20);

if (ret.second==false) it=ret.first;

上述代码将把20插入到myset中。因为set中已经有20这个元素，所以set insert方法不会真正插入20，而是返回一个pair，其中第二个元素为false，表示插入不成功。在这种情况下，第一个元素(it)会指向set中的20元素。如果插入成功，第二个元素为true，表示插入成功。

四、insert高效插入

set insert方法的一个非常重要的特点是它可以进行高效插入。下面的代码示例中，我们将使用insert方法向set中插入大量的元素：

#include <set>
#include <iostream>
#include <ctime>
#include <cstdlib>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it;
  std::pair<std::set<int>::iterator,bool> ret;

  // set some initial values:
  srand(time(NULL));
  for (int i=0; i<10; ++i) myset.insert(rand() % 100); 

  clock_t start, end;
  double total_time;
  start = clock();

  for (int i=0; i<1000000; ++i) 
  {
    myset.insert(rand() % 100); 
  }

  end = clock();
  total_time = ((double) (end - start));
  std::cout << "Time taken by program is : " << total_time / CLOCKS_PER_SEC << " sec " << std::endl; 

  return 0;
}

上述代码将向set中插入1000000个随机整数，并计算插入所花费的时间。在我的机器上，insert插入1000000个元素只需要0.6秒左右，非常高效。

五、使用insert插入结构体

我们还可以使用set insert方法插入自定义的类型。下面的代码示例中，我们将一个结构体中的两个元素放入set中：

#include <set>
#include <iostream>

struct Person
{
  std::string name;
  int age;
};

bool operator < (const Person& lhs, const Person& rhs)
{
    return lhs.name < rhs.name;
}

int main ()
{
  std::set<Person> myset;
  std::set<Person>::iterator it;
  std::pair<std::set<Person>::iterator,bool> ret;

  Person p1 = {"Tom", 20};
  Person p2 = {"Mike", 30};
  Person p3 = {"Alice", 25};

  myset.insert(p1);
  myset.insert(p2);
  myset.insert(p3);

  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << it->name << ", " << it->age << '\n';

  return 0;
}

上述代码中，我们创建了一个Person结构体，并定义了一个小于运算符，用于比较两个Person对象的大小。然后我们可以使用set insert方法将三个Person对象放入set中，并遍历输出。

六、使用insert插入指针

我们还可以使用set insert方法插入指针。下面的代码示例中，我们将三个整数指针放入set中：

#include <set>
#include <iostream>

int main ()
{
  std::set<int *> myset;
  std::set<int *>::iterator it;

  int a = 10;
  int b = 20;
  int c = 30;

  myset.insert(&a);
  myset.insert(&b);
  myset.insert(&c);

  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << **it << '\n';

  return 0;
}

上述代码中，我们定义了一个set，其中存放了3个整数指针。我们可以通过迭代器遍历set并输出它们指向的整数我们使用了**it来访问指针指向的整数。

七、使用insert插入pair

最后我们可以使用set insert方法插入pair类型。下面的代码示例中，我们将三个pair放入set中：

#include <set>
#include <iostream>

int main ()
{
  std::set<std::pair<int, std::string>> myset;
  std::set<std::pair<int, std::string>>::iterator it;

  std::pair<int, std::string> p1 = {10, "Tom"};
  std::pair<int, std::string> p2 = {20, "Mike"};
  std::pair<int, std::string> p3 = {30, "Alice"};

  myset.insert(p1);
  myset.insert(p2);
  myset.insert(p3);

  for (it=myset.begin(); it!=myset.end(); ++it)
    std::cout << it->first << ", " << it->second << '\n';

  return 0;
}

上述代码中，我们定义了一个set，其中存放3个pair类型。我们可以通过迭代器遍历set并输出它们的first和second成员。