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
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#pragma once
#include <vector>
#include <algorithm>
namespace vespalib {
/**
* This is an ordered map that uses a vector of pair as its backing store.
* The advantages over an std::map are that
* - it does not allocate entries individually.
* - it gives very good cache locality.
* - adding element in keyorder is very cheap.
* - so is removing in reverse key order.
*
* Disadvantages
* - it is kept sorted by insertion. So that is an O(N),
* compared to O(log(N)) for std::map or O(1) for std::unordered_map.
* - Same goes for erase.
* - iterators are invalidated by the same rules as an std::vector.
*
**/
template< typename K, typename V, typename LT = std::less<K> >
class vector_map
{
public:
using value_type = std::pair<K, V>;
using key_type = K;
using mapped_type = V;
private:
using OrderedList = std::vector<value_type>;
friend bool operator < (const std::pair<K, V> & a, const std::pair<K, V> & b) {
LT lt;
return lt(a.first, b.first);
}
struct KeyOrder {
bool operator () (const std::pair<K, V> & a, const K & b) {
LT lt;
return lt(a.first, b);
}
};
OrderedList _ht;
public:
using iterator = typename OrderedList::iterator;
using const_iterator = typename OrderedList::const_iterator;
public:
vector_map() : _ht() { }
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
size_t capacity() const { return _ht.capacity(); }
size_t size() const { return _ht.size(); }
bool empty() const { return _ht.empty(); }
V & operator [] (const K & key);
void erase(const K & key) { return _ht.erase(find(key)); }
void erase(iterator it) { return _ht.erase(it); }
void erase(const_iterator it) { return _ht.erase(it); }
iterator find(const K & key) {
iterator f = std::lower_bound(begin(), end(), key, KeyOrder());
LT lt;
return ((f != end()) && !lt(key, f->first)) ? f : end();
}
const_iterator find(const K & key) const {
const_iterator f = std::lower_bound(begin(), end(), key, KeyOrder());
LT lt;
return ((f != end()) && !lt(key, f->first)) ? f : end();
}
void clear() { _ht.clear(); }
void reserve(size_t sz) { _ht.reserve(sz); }
void swap(vector_map & rhs) { _ht.swap(rhs._ht); }
bool operator == (const vector_map & rhs) const;
};
template< typename K, typename V, typename LT >
void swap(vector_map<K, V, LT> & a, vector_map<K, V, LT> & b)
{
a.swap(b);
}
template< typename K, typename V, typename LT >
V &
vector_map<K, V, LT>::operator[](const K &key) {
LT lt;
iterator f = std::lower_bound(begin(), end(), key, KeyOrder());
if (f == end()) {
_ht.template emplace_back(key, V());
return _ht.rbegin()->second;
} else if (lt(key, f->first)) {
f = _ht.template emplace(f, key, V());
}
return f->second;
}
}
|
