STLのset使用の詳細
31631 ワード
setおよびmultisetを使用する前にヘッダファイル<set>を含むset、multisetはいずれも集合クラスであり、差はsetと重複要素が許されず、multisetと重複要素が許される.彼らはみな秩序ある集合だ.std::set is an associative container(関連コンテナ)that contains a sorted set of unique objects of type Key.Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.
メンバータイプ
メンバー関数
コンストラクタ
コンストラクション関数には次のようなものがあります.
以下の例はよく用いられる構造方式であり,以下のコードからよく用いられる構造方法を容易に把握できる.
#include "stdafx.h"
#include <iostream>
#include <string>
#include <set>
// Helper function for printing pairs.
template<class Ch, class Tr, class A, class B> inline
std::basic_ostream<Ch, Tr>& operator<<(std::basic_ostream<Ch, Tr>& stream, std::pair<A, B> p)
{
return stream << '(' << p.first << ", " << p.second << ')';
}
// Helper function for printing containers.
template<class Ch, class Tr, class Co>
std::basic_ostream<Ch, Tr>& operator<<(std::basic_ostream<Ch, Tr>& stream, Co& c)
{
stream << '{' << *c.begin();
for (auto it = ++(c.begin()); it != c.end(); ++it)
stream << ", " << *it;
stream << '}' << std::endl;
return stream;
}
int main()
{
// (1) Default constructor
std::set<std::string> a; //empty set
a.insert("something");
a.insert("anything");
a.insert("that thing");
std::cout << "a = " << a; // sorted
// (2) Iterator constructor
std::set<std::string> b(a.find("anything"), a.end()); // find() return iterator
std::cout << std::string(80, '-') << std::endl;
std::cout << "b = " << b; // a == b
// (3) Copy constructor
std::set<std::string> c(a);
c.insert("another thing"); // insert and sorted
std::cout << std::string(80, '-') << std::endl;
std::cout << "a = " << a;
std::cout << "c = " << c;
// (4) Move constructor
std::set<std::string> d(std::move(a)); // ok.ok.ok --- a to be empty
std::cout << std::string(80, '-') << std::endl;
std::cout << "a = nullptr" << std::endl;
std::cout << "d = " << d;
// (5) Initializer list constructor
std::set<std::string> e{
"one", "two", "three", "five", "eight"
};
std::cout << std::string(80, '-') << std::endl;
std::cout << "e = " << e;
}出力:
a = {anything, something, that thing} --------------------------------------------------------------------------------
b = {anything, something, that thing} --------------------------------------------------------------------------------
a = {anything, something, that thing}
c = {another thing, anything, something, that thing} --------------------------------------------------------------------------------
a = nullptr
d = {anything, something, that thing} --------------------------------------------------------------------------------
e = {eight, five, one, three, two}こうぞうかんすう
~set();Destructs the container. The destructors of the elements are called and the used storage is deallocated. Note, that if the elements are pointers, the pointed-to objects are not destroyed.
構造関数は2つのタスクを完了します:1)
setの各要素の構造関数を呼び出します.2)要素が占有する空間を解放します.格納されている要素値ポインタの場合、ポインタが指すオブジェクトは解放されず、メモリが漏洩しやすいです.operator=
サンプルコードは次のとおりです.
#include <set>
#include <iostream>
void display_sizes(const std::set<int> &nums1,
const std::set<int> &nums2,
const std::set<int> &nums3)
{
std::cout << "nums1: " << nums1.size()
<< " nums2: " << nums2.size()
<< " nums3: " << nums3.size() << '
';
}
int main()
{
std::set<int> nums1 {3, 1, 4, 6, 5, 9}; //
std::set<int> nums2;
std::set<int> nums3;
std::cout << "Initially:
";
display_sizes(nums1, nums2, nums3);
// copy assignment copies data from nums1 to nums2
nums2 = nums1;
std::cout << "After assigment:
";
display_sizes(nums1, nums2, nums3);
// move assignment moves data from nums1 to nums3,
// modifying both nums1 and nums3
nums3 = std::move(nums1); // move nums1 ， (2) nums3
std::cout << "After move assigment:
";
display_sizes(nums1, nums2, nums3);
}出力:
Initially:
nums1: 6 nums2: 0 nums3: 0
After assigment:
nums1: 6 nums2: 6 nums3: 0
After move assigment:
nums1: 0 nums2: 6 nums3: 6get_allocator
allocator_type get_allocator() const;Returns the allocator associated with the container.
Iterators
begin & cbegin
cはconstを表すiterator begin();
const_iterator begin() const;
const_iterator cbegin() const; (since C++11)end & cend
iterator end();
const_iterator end() const;
const_iterator cend() const; (since C++11)rbegin & crbegin
rはreverseを表すreverse_iterator rbegin();
const_reverse_iterator rbegin() const;
const_reverse_iterator crbegin() const; (since C++11)Returns a reverse iterator to the first element of the reversed container. It corresponds to the last element of the non-reversed container.
rend & crend
reverse_iterator rend();
const_reverse_iterator rend() const;
const_reverse_iterator crend() const; (since C++11)Capacity
empty
bool empty() const;Checks if the container has no elements, i.e. whether begin() == end().
size
size_type size() const;Returns the number of elements in the container, i.e. std::distance(begin(), end()).
max_size
size_type max_size() const;Returns the maximum number of elements the container is able to hold due to system or library implementation limitations,
現在のコンテナがメモリに割り当てられる最大要素値を返します.通常は大きな値です.
max_size() - size()は、割り当てられる要素の数を示します.メモリの再割り当てには関係なく、システムとライブラリの実装にのみ関連しています.#include <iostream>
#include <set>
int main()
{
std::set<char> s;
std::cout << "Maximum size of a 'set' is " << s.max_size() << "
";
}出力:
Maximum size of a 'set' is 18446744073709551615Modifiers
clear
void clear();Removes all elements from the container.
insert
説明:
1−2)1つの値を挿入し、
pairを返し、pair->firstは挿入値の反復器を指し、pair->secondは挿入に成功したかどうかを返し、以下の例では明らかである.3-4)指定した位置に指定した値を挿入します.
5)範囲内の要素を挿入します.
6)初期化リストを挿入しても意味がありません.
#include <set>
#include <cassert>
#include <iostream>
int main()
{
std::set<int> set;
auto result_1 = set.insert(3);
//
assert(result_1.first != set.end()); // it's a valid iterator
assert(*result_1.first == 3);
if (result_1.second)
std::cout << "insert done
";
auto result_2 = set.insert(3);
assert(result_2.first == result_1.first); // same iterator
assert(*result_2.first == 3);
if (!result_2.second) // ， false
std::cout << "no insertion
";
}出力:
insert done no insertionemplace
template< class... Args >
std::pair<iterator,bool> emplace( Args&&... args ); (since C++11)Inserts a new element into the container by constructing it in-place with the given args if there is no element with the key in the container.
Careful use of emplace allows the new element to be constructed while avoiding unnecessary copy or move operations emplace_hint
#include <set>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <functional>
const int nof_operations = 100500;
int set_emplace() {
std::set<int> set;
for(int i = 0; i < nof_operations; ++i) {
set.emplace(i);
}
return set.size();
}
int set_emplace_hint() {
std::set<int> set;
auto it = set.begin();
for(int i = 0; i < nof_operations; ++i) {
set.emplace_hint(it, i);
it = set.end();
}
return set.size();
}
int set_emplace_hint_wrong() {
std::set<int> set;
auto it = set.begin();
for(int i = nof_operations; i > 0; --i) {
set.emplace_hint(it, i);
it = set.end();
}
return set.size();
}
int set_emplace_hint_corrected() {
std::set<int> set;
auto it = set.begin();
for(int i = nof_operations; i > 0; --i) {
set.emplace_hint(it, i);
it = set.begin();
}
return set.size();
}
int set_emplace_hint_closest() {
std::set<int> set;
auto it = set.begin();
for(int i = 0; i < nof_operations; ++i) {
it = set.emplace_hint(it, i);
}
return set.size();
}
void timeit(std::function<int()> set_test, std::string what = "") {
auto start = std::chrono::system_clock::now();
int setsize = set_test();
auto stop = std::chrono::system_clock::now();
std::chrono::duration<double, std::milli> time = stop - start;
if (what.size() > 0 && setsize > 0) {
std::cout << std::fixed << std::setprecision(2)
<< time.count() << " ms for " << what << '
';
}
}
int main() {
timeit(set_emplace); // stack warmup
timeit(set_emplace, "plain emplace");
timeit(set_emplace_hint, "emplace with correct hint");
timeit(set_emplace_hint_wrong, "emplace with wrong hint");
timeit(set_emplace_hint_corrected, "corrected emplace");
timeit(set_emplace_hint_closest, "emplace using returned iterator");
}出力:
18.96 ms for plain emplace
7.95 ms for emplace with correct hint
19.39 ms for emplace with wrong hint
8.39 ms for corrected emplace
7.90 ms for emplace using returned iteratorerase
1)指定した位置の要素を除去し、戻ってきた反復器が次の要素を指す
2)指定した範囲の要素を除去する
3)指定した値を除去する
swap
void swap( set& other );Exchanges the contents of the container with those of other. Does not invoke any move, copy, or swap operations on individual elements. All iterators and references remain valid
Lookup
count
size_type count( const Key& key ) const; (1)
template< class K >
size_type count( const K& x ) const; (2) (since C++14)1)指定した要素値の個数を返し、0または1のみを返します.重複する要素の存在は許されないからである.
2)
Returns the number of elements with key that compares equivalent to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. They allow calling this function without constructing an instance of Key. find
指定した要素を指す反復器を返します.指定した要素が見つからない場合は、後続の反復器を返します.返された反復器と
end()を比較して、指定された要素が見つかったかどうかを判断します.#include <iostream>
#include <set>
int main()
{
std::set<int> example = {1, 2, 3, 4};
auto search = example.find(2);
if(search != example.end()) {
std::cout << "Found " << (*search) << '
';
}
else {
std::cout << "Not found
";
}
}出力:
Found 2equal_range
std::pair<iterator,iterator> equal_range( const Key& key );
template< class K >
std::pair<iterator,iterator> equal_range( const K& x );コレクションに等しい要素が連続的に格納されるため、指定した値に等しい範囲を1つの範囲で表すことができます.
1番目の反復器は指定した値より大きくない位置を指し、2番目の反復器は指定した値より大きい1番目の位置を指します.つまり
[first,second)です.この2つの反復器も、lower_boundおよびupper_boundによって返される反復器が指す位置である.lower_bound
iterator lower_bound( const Key& key ); (1)
const_iterator lower_bound( const Key& key ) const; (1)
template< class K >
iterator lower_bound(const K& x); (2) (since C++14)
template< class K >
const_iterator lower_bound(const K& x) const; (2) (since C++14)返される反復器は、指定した値以上の要素を指します.
upper_bound
iterator upper_bound( const Key& key ); (1)
const_iterator upper_bound( const Key& key ) const; (1)
template< class K >
iterator upper_bound( const K& x ); (2) (since C++14)
template< class K >
const_iterator upper_bound( const K& x ) const; (2) (since C++14)返される反復器は、指定した値より大きい最初の要素を指します.
Observers
key_comp
key_compare key_comp() const;Returns the function object that compares the keys, which is a copy of this container’s constructor argument comp. It is the same as value_comp.
value_comp
std::set::value_compare value_comp() const;Returns the function object that compares the values. It is the same as key_comp.
Non-member functions
operator==,!=,<,<=,>,>=(std::set)2つの容器のサイズが同じで、同じ位置の値が等しい場合、
trueを返します.swap
template< class Key, class Compare, class Alloc >
void swap( set<Key,Compare,Alloc>& lhs, set<Key,Compare,Alloc>& rhs );Specializes the std::swap algorithm for std::set. Swaps the contents of lhs and rhs. Calls lhs.swap(rhs).