1 /** 2 * Copyright 2021 Huawei Technologies Co., Ltd 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef MINDSPORE_CORE_UTILS_COMPACT_SET_H_ 18 #define MINDSPORE_CORE_UTILS_COMPACT_SET_H_ 19 20 #include <vector> 21 #include <utility> 22 #include <algorithm> 23 24 namespace mindspore { 25 // CompactSet uses a std::vector to hold data, it keeps insertion order 26 // but use less memory than OrderedSet. It could be more efficient than 27 // OrderedSet when used with a small number of elements. 28 template <typename T> 29 class CompactSet { 30 public: 31 using data_type = std::vector<T>; 32 using iterator = typename data_type::iterator; 33 using const_iterator = typename data_type::const_iterator; 34 add(T && e)35 void add(T &&e) { 36 auto iter = std::find(data_.begin(), data_.end(), e); 37 if (iter == data_.end()) { 38 data_.emplace_back(std::move(e)); 39 } 40 } 41 insert(const T & e)42 void insert(const T &e) { 43 auto iter = std::find(data_.begin(), data_.end(), e); 44 if (iter == data_.end()) { 45 data_.push_back(e); 46 } 47 } 48 find(const T & e)49 iterator find(const T &e) { return std::find(data_.begin(), data_.end(), e); } 50 find(const T & e)51 const_iterator find(const T &e) const { return std::find(data_.begin(), data_.end(), e); } 52 contains(const T & e)53 bool contains(const T &e) const { return (find(e) != data_.end()); } 54 erase(const T & e)55 bool erase(const T &e) { 56 auto iter = std::find(data_.begin(), data_.end(), e); 57 if (iter == data_.end()) { 58 return false; 59 } 60 data_.erase(iter); 61 return true; 62 } 63 erase(iterator pos)64 iterator erase(iterator pos) { return data_.erase(pos); } 65 clear()66 void clear() { data_.clear(); } 67 front()68 const T &front() const { return data_.front(); } back()69 const T &back() const { return data_.back(); } 70 pop()71 T pop() { 72 T e = std::move(data_.front()); 73 data_.erase(data_.begin()); 74 return e; 75 } 76 empty()77 bool empty() const { return data_.empty(); } size()78 std::size_t size() const { return data_.size(); } 79 begin()80 iterator begin() { return data_.begin(); } end()81 iterator end() { return data_.end(); } 82 begin()83 const_iterator begin() const { return data_.cbegin(); } end()84 const_iterator end() const { return data_.cend(); } 85 cbegin()86 const_iterator cbegin() const { return data_.cbegin(); } cend()87 const_iterator cend() const { return data_.cend(); } 88 89 private: 90 data_type data_; 91 }; 92 } // namespace mindspore 93 94 #endif // MINDSPORE_CORE_UTILS_COMPACT_SET_H_ 95