Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Comparison with Associative Containers 與關聯式容器的比較

Table 24.4. Interface differences.
表 24.4. 接口的差異。

Associative Containers 關聯式容器

Unordered Associative Containers 無序關聯式容器

Parameterized by an ordering relation Compare
以一個排序關係 Compare 來參數化

Parameterized by a function object Hash and an equivalence relation Pred

以一個函數對像 Hash 和一個等同性關係 Pred 來參數化

Keys can be compared using key_compare which is accessed by member function key_comp(), values can be compared using value_compare which is accessed by member function value_comp().

鍵值可以使用 key_compare 來比較,後者通過成員函數 key_comp() 來訪問,值可以使用 value_compare 來比較,後者通過成員函數 value_comp() 來訪問。

Keys can be hashed using hasher which is accessed by member function hash_function(), and checked for equality using key_equal which is accessed by member function key_eq(). There is no function object for compared or hashing values.

鍵值可以用 hasher 來散列,它通過成員函數 hash_function() 訪問,並且鍵值使用 key_equal 來檢查等同性,它通過成員函數 key_eq() 訪問。沒有函數對像用於對值進行比較或散列。

Constructors have optional extra parameters for the comparison object.

構造函數有可選的額外參數用於比較用的函數對象。

Constructors have optional extra parameters for the initial minimum number of buckets, a hash function and an equality object.

構造函數有可選的額外參數,用於初始化最小的桶數量、散列函數和等同性函數對象。

Keys k1, k2 are considered equivalent if !Compare(k1, k2) && !Compare(k2, k1)

鍵值 k1, k2 被認為是相等的,如果 !Compare(k1, k2) && !Compare(k2, k1)

Keys k1, k2 are considered equivalent if Pred(k1, k2) 

鍵值 k1, k2 被認為是相等的,如果 Pred(k1, k2)

Member function lower_bound(k) and upper_bound(k) 

成員函數 lower_bound(k)upper_bound(k)

No equivalent. Since the elements aren't ordered lower_bound and upper_bound would be meaningless.
沒有相應的成員函數。因為元素不是有序的,lower_boundupper_bound 沒有意義。

equal_range(k) returns an empty range at the position that k would be inserted if k isn't present in the container.

如果 k 不在容器中,equal_range(k) 返回一個空區間,位於 k 可以被插入的位置。

equal_range(k) returns a range at the end of the container if k isn't present in the container. It can't return a positioned range as k could be inserted into multiple place. To find out the bucket that k would be inserted into use bucket(k). But remember that an insert can cause the container to rehash - meaning that the element can be inserted into a different bucket.

如果 k 不在容器中,equal_range(k) 返回位於容器末尾的區間。它不能返回一個定位的區間,因為 k 可能被插入以多個地方。要找出 k 將被插入的桶,要用 bucket(k)。不過請記住,插入操作可能引起容器的 重散列 - 這意味著該元素可能被插入到另一個桶中。

iterator, const_iterator are of the bidirectional category.

iterator, const_iterator 為雙向迭代器類別。

iterator, const_iterator are of at least the forward category.

iterator, const_iterator 至少為前向迭代器類型。

Iterators, pointers and references to the container's elements are never invalidated.
指向容器元素的迭代器、指針和引用都不會失效。

Iterators can be invalidated by calls to insert or rehash. Pointers and references to the container's elements are never invalidated.

調 用 insert 或 rehash 可能引起迭代器失效。而指向容器元素的指針和引用則不會失效。

Iterators iterate through the container in the order defined by the comparison object.

迭代器按照由比較函數對像所定義的順序遍歷容器。

Iterators iterate through the container in an arbitrary order, that can change as elements are inserted. Although, equivalent elements are always adjacent.

迭代器按任意順序遍歷容器,由元素被插入時還可能改變。不過,相等的元素總是保持連續的。

No equivalent

無對應物

Local iterators can be used to iterate through individual buckets. (I don't think that the order of local iterators and iterators are required to have any correspondence.)

局部迭代器可以用於遍歷單個桶。(我不認為局部迭代器和迭代器的順序有任何對應物)

Can be compared using the ==, !=, <, <=, >, >= operators.

可以用 ==, !=, <, <=, >, >= 操作符進行比較。

No comparison operators are defined in the standard, although implementations might extend the containers to support == and !=.

在標準中沒有定義比較操作符,不過 實 現對容器進行擴展以支持 ==!=

When inserting with a hint, implementations are permitted to ignore the hint.

在帶提示的插入操作時,實現被允許可以忽略提示。

erase never throws an exception

erase 不會拋出異常

The containers' hash or predicate function can throw exceptions from erase

容器的散列函數和謂詞函數可以從 erase 拋出異常


Table 24.5. Complexity Guarantees
表 24.5. 複雜度保證

Operation 操作

Associative Containers 關聯式容器

Unordered Associative Containers 無序關聯式容器

Construction of empty container

空容器的構造

constant

常數

O(n) where n is the minimum number of buckets.

O(n) 其中 n 為桶的最小數量。

Construction of container from a range of N elements

從帶有 N 個元素的區間構造容器

O(N log N), O(N) if the range is sorted with value_comp() 

O(N log N), O(N) 如果區間已按 value_comp() 排序

Average case O(N), worst case O(N2)

平均情況 O(N), 最壞情況 O(N2)

Insert a single element

插入單個元素

logarithmic

對數

Average case constant, worst case linear

平均情況為常數時間,最壞情況為線性時間

Insert a single element with a hint

帶提示插入單個元素

Amortized constant if t elements inserted right after hint, logarithmic otherwise

如果插入的元素恰好在提示位置之後,則為分期常數時間,否則為對數時間

Average case constant, worst case linear (ie. the same as a normal insert).

平均情況為常數時間,最壞情況為線性時間(即與普通插入一樣)

Inserting a range of N elements

插入 N 個元素的區間

N log(size()+N)

Average case O(N), worst case O(N * size())

平均情況為 O(N), 最壞情況為 O(N * size())

Erase by key, k

通過鍵值 k 刪除元素

O(log(size()) + count(k))

Average case: O(count(k)), Worst case: O(size())

平均情況:O(count(k)), 最壞情況:O(size())

Erase a single element by iterator

通過迭代器刪除單個元素

Amortized constant

分期常數時間

Average case: O(1), Worst case: O(size())

平均情況:O(1),最壞情況:O(size())

Erase a range of N elements

刪除 N 個元素的區間

O(log(size()) + N)

Average case: O(N), Worst case: O(size())

平均情況:O(N), 最壞情況: O(size())

Clearing the container

清空容器

O(size())

O(size())

Find

查找

logarithmic

對數時間

Average case: O(1), Worst case: O(size())

平均情況:O(1),最壞情況: O(size())

Count

計數

O(log(size()) + count(k))

Average case: O(1), Worst case: O(size())

平均情況:O(1),最壞情況: O(size())

equal_range(k)

logarithmic

對數時間

Average case: O(count(k)), Worst case: O(size())

平均情況:O(count(k)), 最壞情況:O(size())

lower_bound,upper_bound

logarithmic

對數時間

n/a



PrevUpHomeNext