2014年3月10日 星期一

Insert operation of map and set in C++ STL

single element (1)
pair<iterator,bool> insert (const value_type& val);
with hint (2)
iterator insert (iterator position, const value_type& val);

STL的 set 之 insert, 提供兩個可用的方式,

第一種傳入一個欲插入的值,
若已經出現在 set 中, 則插入失敗會回傳相同的key之位置的 iterator 及 false
否則會回傳插入後之位置的 iterator 及 true

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

#include <set>
#include <iostream>
using namespace std;

int main( ){
    set<int> s;

    s.insert( 1 );
    s.insert( 2 );

    {
        pair<set<int>::iterator,bool> ret = s.insert( 2 );
        cout << *(ret.first) << " " << ret.second;
    }
    cout << endl;
    {
        pair<set<int>::iterator,bool> ret = s.insert( 3 );
        cout << *(ret.first) << " " << ret.second;
    }
}

Output:
1
2

2 false
3 true



第二種傳入一個搜尋的起點當作 set 找出欲插入位置的 hint,
如果提供的資訊正確, 則可以達到 O(1) 的插入時間


以下比較 hint 之功用:

1
2
3

set<int> s;
for( int i = 0 ; i < 10000000; ++i )
    pair<set<int>::iterator,bool> ret = s.insert(i);
執行時間約11秒

1
2
3

set<int> s;
for( int i = 0 ; i < 10000000; ++i )
    set<int>::iterator ret = s.insert(s.end(), i);
執行時間約3秒






張貼者： 於
標籤： ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)