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成員。