Is it in the STL or BOOST map as a container with a search function and pop operation?

Question

I want my map to be searchable, and I want to be able to eject the elements that have been inserted into it the longest (with api like map.remove(map.get_iterator_to_oldest_inserted_element()) ), for example, a combination of queqe and map. Are there any such containers in STL or Boost?

Answer 1

You can use boost :: multi_index using the ordered_unique and sequence indexes, as in this example.

 #include <iostream> #include <boost/multi_index_container.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/multi_index/sequenced_index.hpp> #include <boost/multi_index/member.hpp> // Element type to store in container struct Element { std::string key; int value; Element(const std::string& key, int value) : key(key), value(value) {} }; namespace bmi = boost::multi_index; // Boost multi_index container typedef bmi::multi_index_container< Element, bmi::indexed_by< bmi::ordered_unique< bmi::member<Element,std::string,&Element::key> >, bmi::sequenced<> > > MyContainer; typedef MyContainer::nth_index<1>::type BySequence; // Helper function that returns a sequence view of the container. BySequence& bySequence(MyContainer& container) {return container.get<1>();} int main() { MyContainer container; // Access container by sequence. Push back elements. BySequence& sequence = bySequence(container); sequence.push_back(Element("one", 1)); sequence.push_back(Element("two", 2)); sequence.push_back(Element("three", 3)); // Access container by key. Find an element. // By default the container is accessed as nth_index<0> MyContainer::const_iterator it = container.find("two"); if (it != container.end()) std::cout << it->value << "\n"; // Access container by sequence. Pop elements in a FIFO manner, while (!sequence.empty()) { std::cout << sequence.front().value << "\n"; sequence.pop_front(); } } 

Answer 2

To do this, you can configure boost multi-index container .

However, it is difficult for me to understand containers with multiple indexes. I think it would be easier to collapse my own class, which has the members std::queue and std::map , and manage it myself.

Answer 3

There is nothing similar in boost and stl, but you can make a hybrid:

 map<Key, Value> Map; deque<Key> Queue; void insert(const Key &k, const Value &v) { Map[k] = v; Queue.push_back(k); } void pop_front() { const Key &k = Queue.front(); Map.erase(k); Queue.pop_front(); } 

Answer 4

Boost :: bimap can be used to create a unidirectional map using a list-based relationship set.

 typedef bimap<set_of<A>, unconstrained_set_of<B>, list_of_relation> custom_map_type; custom_map_type map; map.push_back(custom_map_type::value_type(A(), B())); // delete the front of the list (the first inserted element if only using push_back) map.pop_front(); // otherwise, set.right behave a lot like a std::map<A,B>, with minor changes. 

Answer 5

If you only want to find the oldest (or the newest - or, as a rule, the smallest / largest according to some given criteria, and you can delete this element), priority_queue will complete the task.