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 49 template <class InputIt> insert(InputIt first,InputIt last)50 void insert(InputIt first, InputIt last) { 51 for (; first != last; ++first) { 52 insert(*first); 53 } 54 } 55 find(const T & e)56 iterator find(const T &e) { return std::find(data_.begin(), data_.end(), e); } 57 find(const T & e)58 const_iterator find(const T &e) const { return std::find(data_.begin(), data_.end(), e); } 59 contains(const T & e)60 bool contains(const T &e) const { return (find(e) != data_.end()); } 61 erase(const T & e)62 bool erase(const T &e) { 63 auto iter = std::find(data_.begin(), data_.end(), e); 64 if (iter == data_.end()) { 65 return false; 66 } 67 data_.erase(iter); 68 return true; 69 } 70 erase(const iterator & pos)71 iterator erase(const iterator &pos) { return data_.erase(pos); } 72 clear()73 void clear() { data_.clear(); } 74 front()75 const T &front() const { return data_.front(); } back()76 const T &back() const { return data_.back(); } 77 pop()78 T pop() { 79 T e = std::move(data_.front()); 80 (void)data_.erase(data_.begin()); 81 return e; 82 } 83 empty()84 bool empty() const { return data_.empty(); } size()85 std::size_t size() const { return data_.size(); } 86 begin()87 iterator begin() { return data_.begin(); } end()88 iterator end() { return data_.end(); } 89 begin()90 const_iterator begin() const { return data_.cbegin(); } end()91 const_iterator end() const { return data_.cend(); } 92 cbegin()93 const_iterator cbegin() const { return data_.cbegin(); } cend()94 const_iterator cend() const { return data_.cend(); } 95 96 private: 97 data_type data_; 98 }; 99 } // namespace mindspore 100 101 #endif // MINDSPORE_CORE_UTILS_COMPACT_SET_H_ 102