C++中的Associative containers（关联容器）

文章目录

1.set
2.map:
3.multiset
4.multimap
6.无序关联容器

1.set

set底层实现为红黑树。

#include "set"

using namespace std;

int main() {
    set ss = {1, 6, 3, 9, 2, 9};
    for (auto i: ss) {
        cout << i << endl;
    }
    return 0;
}

output

注意：

进入set的元素会被排序；
set中的元素是唯一的；
进入set的元素不能再修改，但是可以移除之后再添加新的元素；
set的是实现使用的是二分查找树；
set中的元素是无法索引的。

2.map:

key-value的集合，按照key进行排序，key是唯一的
使用示例如下：

#include 
#include 
#include 
using namespace std;
  
int main()
{
  
    // empty map container
    map gquiz1;
  
    // insert elements in random order
    gquiz1.insert(pair(1, 40));
    gquiz1.insert(pair(2, 30));
    gquiz1.insert(pair(3, 60));
    gquiz1.insert(pair(4, 20));
    gquiz1.insert(pair(5, 50));
    gquiz1.insert(pair(6, 50));
    gquiz1.insert(pair(7, 10));
  
    // printing map gquiz1
    map::iterator itr;
    cout << "nThe map gquiz1 is : n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
    cout << endl;
  
    // assigning the elements from gquiz1 to gquiz2
    map gquiz2(gquiz1.begin(), gquiz1.end());
  
    // print all elements of the map gquiz2
    cout << "nThe map gquiz2 after"
         << " assign from gquiz1 is : n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
    cout << endl;
  
    // remove all elements up to
    // element with key=3 in gquiz2
    cout << "ngquiz2 after removal of"
            " elements less than key=3 : n";
    cout << "tKEYtELEMENTn";
    gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
  
    // remove all elements with key = 4
    int num;
    num = gquiz2.erase(4);
    cout << "ngquiz2.erase(4) : ";
    cout << num << " removed n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
  
    cout << endl;
  
    // lower bound and upper bound for map gquiz1 key = 5
    cout << "gquiz1.lower_bound(5) : "
         << "tKEY = ";
    cout << gquiz1.lower_bound(5)->first << 't';
    cout << "tELEMENT = " << gquiz1.lower_bound(5)->second
         << endl;
    cout << "gquiz1.upper_bound(5) : "
         << "tKEY = ";
    cout << gquiz1.upper_bound(5)->first << 't';
    cout << "tELEMENT = " << gquiz1.upper_bound(5)->second
         << endl;
  
    return 0;
}

output

The map gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10


The map gquiz2 after assign from gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10


gquiz2 after removal of elements less than key=3 : 
    KEY    ELEMENT
    3    60
    4    20
    5    50
    6    50
    7    10

gquiz2.erase(4) : 1 removed 
    KEY    ELEMENT
    3    60
    5    50
    6    50
    7    10

gquiz1.lower_bound(5) :     KEY = 5        ELEMENT = 50
gquiz1.upper_bound(5) :     KEY = 6        ELEMENT = 50

3.multiset

类似于set，只是元素可以重复，底层使用的还是红黑树

4.multimap

类似于map，只是其中的key可以重复
使用示例如下：

#include 
#include 
#include 
using namespace std;
 
// Driver Code
int main()
{
    multimap gquiz1; // empty multimap container
 
    // insert elements in random order
    gquiz1.insert(pair(1, 40));
    gquiz1.insert(pair(2, 30));
    gquiz1.insert(pair(3, 60));
    gquiz1.insert(pair(6, 50));
    gquiz1.insert(pair(6, 10));
 
    // printing multimap gquiz1
    multimap::iterator itr;
    cout << "nThe multimap gquiz1 is : n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
    cout << endl;
 
    // adding elements randomly,
    // to check the sorted keys property
    gquiz1.insert(pair(4, 50));
    gquiz1.insert(pair(5, 10));
 
    // printing multimap gquiz1 again
 
    cout << "nThe multimap gquiz1 after adding extra "
            "elements is : n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
    cout << endl;
 
    // assigning the elements from gquiz1 to gquiz2
    multimap gquiz2(gquiz1.begin(), gquiz1.end());
 
    // print all elements of the multimap gquiz2
    cout << "nThe multimap gquiz2 after assign from "
            "gquiz1 is : n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
    cout << endl;
 
    // remove all elements up to
    // key with value 3 in gquiz2
    cout << "ngquiz2 after removal of elements less than "
            "key=3 : n";
    cout << "tKEYtELEMENTn";
    gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
 
    // remove all elements with key = 4
    int num;
    num = gquiz2.erase(4);
    cout << "ngquiz2.erase(4) : ";
    cout << num << " removed n";
    cout << "tKEYtELEMENTn";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << 't' << itr->first << 't' << itr->second
             << 'n';
    }
 
    cout << endl;
 
    // lower bound and upper bound for multimap gquiz1 key =
    // 5
    cout << "gquiz1.lower_bound(5) : "
         << "tKEY = ";
    cout << gquiz1.lower_bound(5)->first << 't';
    cout << "tELEMENT = " << gquiz1.lower_bound(5)->second
         << endl;
    cout << "gquiz1.upper_bound(5) : "
         << "tKEY = ";
    cout << gquiz1.upper_bound(5)->first << 't';
    cout << "tELEMENT = " << gquiz1.upper_bound(5)->second
         << endl;
 
    return 0;
}

output

The multimap gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    6    50
    6    10


The multimap gquiz1 after adding extra elements is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    50
    5    10
    6    50
    6    10


The multimap gquiz2 after assign from gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    50
    5    10
    6    50
    6    10


gquiz2 after removal of elements less than key=3 : 
    KEY    ELEMENT
    3    60
    4    50
    5    10
    6    50
    6    10

gquiz2.erase(4) : 1 removed 
    KEY    ELEMENT
    3    60
    5    10
    6    50
    6    10

gquiz1.lower_bound(5) :     KEY = 5        ELEMENT = 10
gquiz1.upper_bound(5) :     KEY = 6        ELEMENT = 50

6.无序关联容器

unordered_set
unordered_map
unordered_mutilset
unordered_multimap
以上都是用hashtable实现的无序关联容器

C++中的Associative containers（关联容器）

C/C++/C#相关栏目本月热门文章