/
ordered_map.impl.hpp
126 lines (99 loc) · 3.69 KB
/
ordered_map.impl.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*****************************************************************************/
/* Milliways - B+ trees and key-value store C++ library */
/* */
/* Copyright 2016 Marco Pantaleoni and J CUBE Inc. Tokyo, Japan. */
/* */
/* Author: Marco Pantaleoni <marco.pantaleoni@gmail.com> */
/* */
/* Licensed under the Apache License, Version 2.0 (the "License"); */
/* you may not use this file except in compliance with the License. */
/* You may obtain a copy of the License at */
/* */
/* http://www.apache.org/licenses/LICENSE-2.0 */
/* */
/* Unless required by applicable law or agreed to in writing, software */
/* distributed under the License is distributed on an "AS IS" BASIS, */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
/* See the License for the specific language governing permissions and */
/* limitations under the License. */
/*****************************************************************************/
#ifndef MILLIWAYS_ORDERED_MAP_H
#include "ordered_map.h"
#endif
#ifndef MILLIWAYS_ORDERED_MAP_IMPL_H
#define MILLIWAYS_ORDERED_MAP_IMPL_H
#include <map>
#include <deque>
#include <algorithm>
#include <stdint.h>
#include <assert.h>
namespace milliways {
template <typename Key, typename T>
bool ordered_map<Key, T>::get(T & dst, const Key& key)
{
typename key_value_map_t::const_iterator it = m_map.find(key);
if (it != m_map.end())
{
dst = it->second;
return true;
}
return false;
}
template <typename Key, typename T>
void ordered_map<Key, T>::set(const Key& key, const T & value)
{
typename key_value_map_t::const_iterator it = m_map.find(key);
if (it == m_map.end())
m_keys.push_back(key);
m_map[key] = value;
}
template <typename Key, typename T>
T & ordered_map<Key, T>::operator[](const Key& key)
{
typename key_value_map_t::const_iterator it = m_map.find(key);
if (it == m_map.end())
m_keys.push_back(key);
return m_map[key];
}
template <typename Key, typename T>
std::pair<Key, T> ordered_map<Key, T>::pop()
{
Key key = m_keys.back();
m_keys.pop_back();
typename key_value_map_t::iterator it = m_map.find(key);
T value = it->second;
m_map.erase(it);
return std::pair<Key, T>(key, value);
}
template <typename Key, typename T>
std::pair<Key, T> ordered_map<Key, T>::pop_front()
{
Key key = m_keys.front();
m_keys.pop_front();
typename key_value_map_t::iterator it = m_map.find(key);
T value = it->second;
m_map.erase(it);
return std::pair<Key, T>(key, value);
}
template <typename Key, typename T>
std::pair<Key, T> ordered_map<Key, T>::pop(const key_type& key)
{
typename key_vector_t::iterator k_it = std::find(m_keys.begin(), m_keys.end(), key);
if (k_it != m_keys.end())
{
m_keys.erase(k_it);
typename key_value_map_t::iterator it = m_map.find(key);
T value = it->second;
m_map.erase(it);
return std::pair<Key, T>(key, value);
}
return std::pair<Key, T>();
}
template <typename Key, typename T>
typename ordered_map<Key, T>::iterator ordered_map<Key, T>::find(const key_type& key)
{
typename key_vector_t::iterator k_it = std::find(m_keys.begin(), m_keys.end(), key);
return iterator(this, k_it);
}
} /* end of namespace milliways */
#endif /* MILLIWAYS_ORDERED_MAP_IMPL_H */