数据结构首先拉扯 - java [英] Data structures that have pull first and lest - java
问题描述
- 具有键和值
- 可以在O（n）> t> O（logn）或O（1 ）
- 可以拉第一个元素和我插入的最后一个元素。
TreeMep不好，因为如果我插入键（作为字符串）b然后键入a如果我将拉第一个我将获得a而不是b
ConcurrentSkipListMap不好，因为我不能依赖
感谢任何帮助
谢谢
您可以使用 multimap交叉引用的 deque （双端队列） code>（通常是一个二叉搜索树），它允许重复的键。
队列的每个元素都将有一个对应元素的引用（迭代器）的地图，反之亦然。
这样，您可以在O（日志N）的地图中搜索，您可以在顺序的两端进行推/拉e in O（log N）。
您可以决定将字符串存储在地图或队列中。
这是C ++中的一个实现：
#include< string>
#include< map>
#include< deque>
typedef int my_key_type; //键入类型
typedef std :: string my_value_type; //值类型
struct queueitem; //队列元素
typedef std :: deque< queueitem> my_queue // Queue
typedef std :: multimap< my_key_type，
my_queue :: iterator> my_map; // Map
typedef std :: pair< my_key_type，
my_queue :: iterator> my_map_pair // Map元素
struct queueitem
{
my_value_type value;
my_map :: iterator mapitem;
queueitem（const my_value_type& val）：value（val）{}
};
class mapqueue
{
public：
mapqueue（）{}
my_value_type find（my_key_type key）const;
size_t index_of（my_key_type key）const;
my_value_type front_value（）const {return Q.front（）。value; }
my_value_type back_value（）const {return Q.back（）。value; }
my_key_type front_key（）const
{return Q.front（）。mapitem-> first; }
my_key_type back_key（）const
{return Q.back（）。mapitem-> first; }
void push_front（my_key_type key，
const my_value_type& value）;
void push_back（my_key_type key，
const my_value_type& value）;
void pop_front（）;
void pop_back（）;
私人：
my_queue Q;
my_map M;
mapqueue（const mapqueue&）{}
mapqueue& operator =（const mapqueue&）{return * this; }
};
使用namespace std;
my_value_type mapqueue :: find（my_key_type key）const
{
my_map :: const_iterator it = M.find（key）;
if（it == M.end（））
throwNot found;
return it-> second-> value;
}
size_t mapqueue :: index_of（my_key_type key）const
{
my_map :: const_iterator it = M.find（key）;
if（it == M.end（））
throwNot found;
return it-> second - Q.begin（）;
}
void mapqueue :: push_front（my_key_type key，
const my_value_type& value）
{
Q.push_front（queueitem（value）） ;
my_queue :: iterator qit = Q.begin（）;
qit-> mapitem = M.insert（my_map_pair（key，qit））;
}
void mapqueue :: push_back（my_key_type key，
const my_value_type& value）
{
Q.push_back（queueitem（value）） ;
my_queue :: iterator qit = Q.end（） - 1;
qit-> mapitem = M.insert（my_map_pair（key，qit））;
}
void mapqueue :: pop_front（）
{
M.erase（Q.front（）。mapitem）;
Q.pop_front（）;
}
void mapqueue :: pop_back（）
{
M.erase（Q.back（）。mapitem）;
Q.pop_back（）;
}
这也支持在O中找到任何给定键的队列中的索引（日志N）。如果您不需要此功能，您可以简化存储地图中字符串的设计，并将地图中的引用从队列中移除。
更新： 现在，键值和值类型通过 typedef 指定。这样很容易改变它们。将整个事物转换为由这两种类型参数化的模板将是有趣的。这样，即使在同一个程序中，相同的代码也可以重复使用不同的键值类型。
更新：一般情况的工具： Boost Multi-index Containers Library 请参见此示例文件。
I am looking for a data structures that have the next features: - have key and value - can find the value in O(n) > t > O(logn ) or O(1) - can pull the first element and the last element I insert.
TreeMep is not good, because if I insert key (as string) "b" and then key "a" if I will pull the first one I will get "a" instead of "b"
ConcurrentSkipListMap is not good because I can't rely on size func'
will appreciate any help
thanks
You can use a deque (double ended queue) cross-referenced with a multimap (tipically a binary search tree), which allows duplicate keys.
Every element of the queue would have a reference (an iterator) to the corresponding element of the map and vice-versa.
This way, you can search in the map in O(log N) and you can push/pull at either ends of the sequence in O(log N).
You can decide to store the strings in the map or in the queue.
Here is an implementation in C++:
#include <string>
#include <map>
#include <deque>
typedef int my_key_type; // Key type
typedef std::string my_value_type; // Value type
struct queueitem; // Queue element
typedef std::deque<queueitem> my_queue; // Queue
typedef std::multimap <my_key_type,
my_queue::iterator> my_map; // Map
typedef std::pair <my_key_type,
my_queue::iterator> my_map_pair; // Map element
struct queueitem
{
my_value_type value;
my_map::iterator mapitem;
queueitem (const my_value_type & val) : value(val) {}
};
class mapqueue
{
public:
mapqueue () {}
my_value_type find (my_key_type key) const;
size_t index_of (my_key_type key) const;
my_value_type front_value () const { return Q.front().value; }
my_value_type back_value () const { return Q.back().value; }
my_key_type front_key () const
{ return Q.front().mapitem->first; }
my_key_type back_key () const
{ return Q.back().mapitem->first; }
void push_front (my_key_type key,
const my_value_type & value);
void push_back (my_key_type key,
const my_value_type & value);
void pop_front ();
void pop_back ();
private:
my_queue Q;
my_map M;
mapqueue (const mapqueue &) {}
mapqueue & operator= (const mapqueue &) { return *this; }
};
using namespace std;
my_value_type mapqueue::find (my_key_type key) const
{
my_map::const_iterator it = M.find (key);
if (it==M.end())
throw "Not found";
return it->second->value;
}
size_t mapqueue::index_of (my_key_type key) const
{
my_map::const_iterator it = M.find (key);
if (it==M.end())
throw "Not found";
return it->second - Q.begin();
}
void mapqueue::push_front (my_key_type key,
const my_value_type & value)
{
Q.push_front (queueitem(value));
my_queue::iterator qit = Q.begin ();
qit->mapitem = M.insert (my_map_pair(key,qit));
}
void mapqueue::push_back (my_key_type key,
const my_value_type & value)
{
Q.push_back (queueitem(value));
my_queue::iterator qit = Q.end () - 1;
qit->mapitem = M.insert (my_map_pair(key,qit));
}
void mapqueue::pop_front ()
{
M.erase (Q.front().mapitem);
Q.pop_front ();
}
void mapqueue::pop_back ()
{
M.erase (Q.back().mapitem);
Q.pop_back ();
}
This also supports finding the index in the queue of any given key in O(log N). If you don't need this, you can simplify the design storing the strings in the map and removing the references from the map to the queue.
Update: The key and value types are now specified via typedefs. This way it's easy to change them. It would be interesting to convert the whole thing in a template parametrized by these two types. This way, the same code would be reusable for different pairs of key-value types even in the same program.
Update: There is a tool for the general case: the Boost Multi-index Containers Library. See this example in the documentation.
这篇关于数据结构首先拉扯 - java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
