Map
可以通过Map迭代器改变map的元素内容吗?
如果想修改元素的键值,那是不行的，因为map元素的键值关系到map元素的排列规则。 任意改变map元素键值将会严重破坏map组织。 但是如果想修改元素的实值，是可以的。 因为map元素的实值并不影响map元素的排列规则。 因此：map interators既不是一种constant interators ，也并不是mutable interators.
map 底层是使用使用了RB-tree算法
map 的调用里面，都是通过调用RB-tree的接口
里面方法的简单使用
DenseMap
llvm-DenseMapInfo.h
DenseMapInfo 这个周密map的信息
实现的类型有：
T* 、DisguisedPtr<T>、const char*、char、unsigned、unsigned long、unsigned long long、int、long、long long、std::pair<T, U>、
template<typename T>
struct DenseMapInfo<T*> { // T是指针类型
static inline T* getEmptyKey() { //空的key都是 *t = -1
uintptr_t Val = static_cast<uintptr_t>(-1);
return reinterpret_cast<T*>(Val);
}
static inline T* getTombstoneKey() { // 这个设置为-2
uintptr_t Val = static_cast<uintptr_t>(-2);
return reinterpret_cast<T*>(Val);
}
static unsigned getHashValue(const T *PtrVal) {
return ptr_hash((uintptr_t)PtrVal); // 求地址的hash值
}
static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } // 判断是否相等（地址）
};
... 里面还定义了其他类型的信息
1、getEmptyKey() 这个直接返回-1
2、getTombstoneKey() 这个直接返回-2
3、getHashValue() 获取hash值 （不同的类型可能会 有不同的算法）
4、isEqual() 判断是否相等，按照需要来进行判断
// 定义了一个value info 表示value有值传入就不会为空的
template<typename T>
struct DenseMapValueInfo {
static inline bool isPurgeable(const T &value) {
return false;
}
};
llvm-DenseMap.h
// 重写pair大概是为了DisguisedPtr<T> 这些新的bucket方式
namespace detail { // detail 的域
// We extend a pair to allow users to override the bucket type with their own implementation without requiring two members.
// 封装让用户可以重写bucketType， 不需要要求两个数据
template <typename KeyT, typename ValueT>
struct DenseMapPair : public std::pair<KeyT, ValueT> {
DenseMapPair(const KeyT &Key, const ValueT &Value)
: std::pair<KeyT, ValueT>(Key, Value) {}
DenseMapPair(KeyT &&Key, ValueT &&Value)
: std::pair<KeyT, ValueT>(std::move(Key), std::move(Value)) {}
// 继承构造的方法 ， key/value 和pair的方式
template <typename AltKeyT, typename AltValueT>
DenseMapPair(AltKeyT &&AltKey, AltValueT &&AltValue,
typename std::enable_if<
std::is_convertible<AltKeyT, KeyT>::value &&
std::is_convertible<AltValueT, ValueT>::value>::type * = 0)
: std::pair<KeyT, ValueT>(std::forward<AltKeyT>(AltKey),
std::forward<AltValueT>(AltValue)) {}
template <typename AltPairT>
DenseMapPair(AltPairT &&AltPair,
typename std::enable_if<std::is_convertible<
AltPairT, std::pair<KeyT, ValueT>>::value>::type * = 0)
: std::pair<KeyT, ValueT>(std::forward<AltPairT>(AltPair)) {}
// 引用方式和值方式、 第1个和第2个值
KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }
const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
};
}
DenseMapIterator 迭代器
1、定义了5个常变量设置
2、有一个当前指针和结束指针，实现有关iterator方法 ， 用于判断。
3、实现向前迭代和向后迭代的方法
template <typename KeyT, typename ValueT, typename ValueInfoT,
typename KeyInfoT, typename Bucket, bool IsConst>
class DenseMapIterator {
friend class DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, Bucket, true>;
friend class DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, Bucket, false>;
using ConstIterator = DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, Bucket, true>; // 常量的迭代器
public:
// 常规定义的 迭代器的5个类型
using difference_type = ptrdiff_t; // 两个迭代器之间距离
using value_type =
typename std::conditional<IsConst, const Bucket, Bucket>::type; // (key/value) 的类型 ，是 T/V 还是T*/V
using pointer = value_type *; // 指针累心
using reference = value_type &; // 引用类型
using iterator_category = std::forward_iterator_tag; // 能够读写的迭代器， 迭代器类型
private:
pointer Ptr = nullptr; // 当前指针
pointer End = nullptr; // 结束指针
public:
DenseMapIterator(pointer Pos, pointer E,
bool NoAdvance = false)
: Ptr(Pos), End(E) {
if (NoAdvance) return; // 没有优化
AdvancePastEmptyBuckets(); // 默认是false， 优化，经过空的buckets ， 默认就是向前的，就是forward_iterator_tag 这个方式去增加的
}
// Converting ctor from non-const iterators to const iterators. SFINAE'd out
// for const iterator destinations so it doesn't end up as a user defined copy
// constructor.
template <bool IsConstSrc,
typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
DenseMapIterator(
const DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, Bucket, IsConstSrc> &I)
: Ptr(I.Ptr), End(I.End) {} //
// 迭代器操作以及判断使用的函数
reference operator*() const {
return *Ptr;
}
pointer operator->() const {
return Ptr;
}
bool operator==(const ConstIterator &RHS) const {
return Ptr == RHS.Ptr;
}
bool operator!=(const ConstIterator &RHS) const {
return Ptr != RHS.Ptr;
}
// 迭代器++的方式，前+ ， 后加
inline DenseMapIterator& operator++() { // Preincrement
++Ptr;
AdvancePastEmptyBuckets();
return *this;
}
DenseMapIterator operator++(int) { // Postincrement
DenseMapIterator tmp = *this; ++*this; return tmp;
}
private:
// 向前
void AdvancePastEmptyBuckets() { // 为什么要去掉空的区域？
ASSERT(Ptr <= End);
const KeyT Empty = KeyInfoT::getEmptyKey();
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
++Ptr;
}
// 向后
void RetreatPastEmptyBuckets() {
ASSERT(Ptr >= End);
const KeyT Empty = KeyInfoT::getEmptyKey();
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
--Ptr;
}
};
DenseMapBase 基础类
template <typename DerivedT, typename KeyT, typename ValueT,
typename ValueInfoT, typename KeyInfoT, typename BucketT>
class DenseMapBase {
template <typename T>
using const_arg_type_t = typename const_pointer_or_const_ref<T>::type; // 定义了T* 指针类型
public:
using size_type = unsigned;
using key_type = KeyT;
using mapped_type = ValueT;
using value_type = BucketT; // 这个是pair类型， bucket应该是空间
using iterator = DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>; // 变量迭代器
using const_iterator =
DenseMapIterator<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT, true>; // 常量迭代器
inline iterator begin()
inline iterator end()
/// Grow the densemap so that it can contain at least \p NumEntries items
/// before resizing again.
void reserve(size_type NumEntries) {
auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
if (NumBuckets > getNumBuckets()) // 最小的空间 > 当前的空间
grow(NumBuckets); // 增加到当前最小的空间
}
// Clear if empty.
// Shrink if at least 15/16 empty and larger than MIN_COMPACT.
// 变化空间
void compact() {
if (getNumEntries() == 0) {
shrink_and_clear();
}
else if (getNumBuckets() / 16 > getNumEntries() &&
getNumBuckets() > MIN_COMPACT)
{
grow(getNumEntries() * 2);
}
}
// 擦除通过值、迭代器
bool erase(const KeyT &Val) {
BucketT *TheBucket;
if (!LookupBucketFor(Val, TheBucket))
return false; // not in map.
TheBucket->getSecond().~ValueT();
TheBucket->getFirst() = getTombstoneKey();
decrementNumEntries();
incrementNumTombstones(); // 没有命中的
compact();
return true;
}
protected:
void initEmpty() {
setNumEntries(0);
setNumTombstones(0);
ASSERT((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
"# initial buckets must be a power of two!");
const KeyT EmptyKey = getEmptyKey();
for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
::new (&B->getFirst()) KeyT(EmptyKey); // key设置为 -1空
}
/// 获取一个最小的散列表
unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
// Ensure that "NumEntries * 4 < NumBuckets * 3"
if (NumEntries == 0)
return 0;
// +1 is required because of the strict equality.
// For example if NumEntries is 48, we need to return 401.
return NextPowerOf2(NumEntries * 4 / 3 + 1); // 需要最少的空间
}
template <typename LookupKeyT>
BucketT *InsertIntoBucketImpl(const KeyT &Key, const LookupKeyT &Lookup,
BucketT *TheBucket) {
// If the load of the hash table is more than 3/4, or if fewer than 1/8 of
// the buckets are empty (meaning that many are filled with tombstones),
// grow the table.
//
// The later case is tricky. For example, if we had one empty bucket with
// tons of tombstones, failing lookups (e.g. for insertion) would have to
// probe almost the entire table until it found the empty bucket. If the
// table completely filled with tombstones, no lookup would ever succeed,
// causing infinite loops in lookup.
unsigned NewNumEntries = getNumEntries() + 1;
unsigned NumBuckets = getNumBuckets();
if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
this->grow(NumBuckets * 2);
LookupBucketFor(Lookup, TheBucket);
NumBuckets = getNumBuckets();
} else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
NumBuckets/8)) {
this->grow(NumBuckets);
LookupBucketFor(Lookup, TheBucket);
}
ASSERT(TheBucket);
// Only update the state after we've grown our bucket space appropriately
// so that when growing buckets we have self-consistent entry count.
// If we are writing over a tombstone or zero value, remember this.
if (KeyInfoT::isEqual(TheBucket->getFirst(), getEmptyKey())) {
// Replacing an empty bucket.
incrementNumEntries();
} else if (KeyInfoT::isEqual(TheBucket->getFirst(), getTombstoneKey())) {
// Replacing a tombstone.
incrementNumEntries();
decrementNumTombstones();
} else {
// we should be purging a zero. No accounting changes.
ASSERT(ValueInfoT::isPurgeable(TheBucket->getSecond()));
TheBucket->getSecond().~ValueT();
}
return TheBucket;
}
/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
/// FoundBucket. If the bucket contains the key and a value, this returns
/// true, otherwise it returns a bucket with an empty marker or tombstone and
/// returns false.
// 查找的过程
template<typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val,
const BucketT *&FoundBucket) const {
const BucketT *BucketsPtr = getBuckets();
const unsigned NumBuckets = getNumBuckets();
if (NumBuckets == 0) {
FoundBucket = nullptr;
return false;
}
// FoundTombstone - Keep track of whether we find a tombstone while probing.
const BucketT *FoundTombstone = nullptr;
const KeyT EmptyKey = getEmptyKey();
const KeyT TombstoneKey = getTombstoneKey();
assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
!KeyInfoT::isEqual(Val, TombstoneKey) &&
"Empty/Tombstone value shouldn't be inserted into map!");
unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //NumBuckets 这个是2的n次方， 所以，这个是求余在这个范围内
unsigned ProbeAmt = 1;
while (true) {
const BucketT *ThisBucket = BucketsPtr + BucketNo; // 索引+ 距离
// Found Val's bucket? If so, return it.
if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
FoundBucket = ThisBucket;
return true; // 找到
}
// If we found an empty bucket, the key doesn't exist in the set.
// Insert it and return the default value. 当前的位置是空的
if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
// If we've already seen a tombstone while probing, fill it in instead
// of the empty bucket we eventually probed to.
FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; // 么有找到
return false;
}
// If this is a tombstone, remember it. If Val ends up not in the map, we
// prefer to return it than something that would require more probing.
// Ditto for zero values. 是个墓碑，怎么处理？
if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
!FoundTombstone)
FoundTombstone = ThisBucket; // Remember the first tombstone found.
if (ValueInfoT::isPurgeable(ThisBucket->getSecond()) && !FoundTombstone)
FoundTombstone = ThisBucket; // valueInfoT 中查找
// Otherwise, it's a hash collision or a tombstone, continue quadratic
// probing.
if (ProbeAmt > NumBuckets) {
FatalCorruptHashTables(BucketsPtr, NumBuckets);
}
// 这个计算是什么意思？ 到时候看看这里是怎么么调用的？
BucketNo += ProbeAmt++;
BucketNo &= (NumBuckets-1);
}
}
};
PS : 关键代码
1、通过hash表来进行查找呵呵插入
2、没有找到的时候要如何进一步处理？
DenseMap
template <typename KeyT, typename ValueT,
typename ValueInfoT = DenseMapValueInfo<ValueT>,
typename KeyInfoT = DenseMapInfo<KeyT>,
typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>,
KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT> {
friend class DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;
using BaseT = DenseMapBase<DenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;
BucketT *Buckets;
unsigned NumEntries;
unsigned NumTombstones;
unsigned NumBuckets;
public:
explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); }
DenseMap(const DenseMap &other) : BaseT() {
init(0);
copyFrom(other);
}
DenseMap(DenseMap &&other) : BaseT() {
init(0);
swap(other);
}
template<typename InputIt>
DenseMap(const InputIt &I, const InputIt &E) {
init(std::distance(I, E));
this->insert(I, E);
}
DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
init(Vals.size());
this->insert(Vals.begin(), Vals.end());
}
void swap(DenseMap& RHS) {
std::swap(Buckets, RHS.Buckets);
std::swap(NumEntries, RHS.NumEntries);
std::swap(NumTombstones, RHS.NumTombstones);
std::swap(NumBuckets, RHS.NumBuckets);
}
DenseMap& operator=(const DenseMap& other) {
if (&other != this)
copyFrom(other);
return *this;
}
DenseMap& operator=(DenseMap &&other) {
this->destroyAll();
operator delete(Buckets);
init(0);
swap(other);
return *this;
}
void copyFrom(const DenseMap& other) {
this->destroyAll();
operator delete(Buckets);
if (allocateBuckets(other.NumBuckets)) {
this->BaseT::copyFrom(other);
} else {
NumEntries = 0;
NumTombstones = 0;
}
}
void init(unsigned InitNumEntries) {
auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
if (allocateBuckets(InitBuckets)) {
this->BaseT::initEmpty();
} else {
NumEntries = 0;
NumTombstones = 0;
}
}
// 扩展空间
void grow(unsigned AtLeast) {
unsigned OldNumBuckets = NumBuckets;
BucketT *OldBuckets = Buckets;
// 这个分配空间
allocateBuckets(std::max<unsigned>(MIN_BUCKETS, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
ASSERT(Buckets);
if (!OldBuckets) {
this->BaseT::initEmpty();
return;
}
this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
// Free the old table.
operator delete(OldBuckets);
}
// 缩小和清空
void shrink_and_clear() {
unsigned OldNumEntries = NumEntries;
this->destroyAll();
// Reduce the number of buckets.
unsigned NewNumBuckets = 0;
if (OldNumEntries)
NewNumBuckets = std::max(MIN_BUCKETS, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
if (NewNumBuckets == NumBuckets) {
this->BaseT::initEmpty();
return;
}
operator delete(Buckets);
init(NewNumBuckets);
}
private:
bool allocateBuckets(unsigned Num) {
NumBuckets = Num;
if (NumBuckets == 0) {
Buckets = nullptr;
return false;
}
Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
return true;
}
};
主要功能
1、扩展空间
2、缩小和清空数据
3、 分配空间
4、拷贝数据
5、交换对象
SmallDenseMap
从4个数据的数组开始增加成为一个结构体。
template <typename KeyT, typename ValueT, unsigned InlineBuckets = 4,
typename ValueInfoT = DenseMapValueInfo<ValueT>,
typename KeyInfoT = DenseMapInfo<KeyT>,
typename BucketT = detail::DenseMapPair<KeyT, ValueT>>
class SmallDenseMap
: public DenseMapBase<
SmallDenseMap<KeyT, ValueT, InlineBuckets, ValueInfoT, KeyInfoT, BucketT>, KeyT,
ValueT, ValueInfoT, KeyInfoT, BucketT> {
friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;
// Lift some types from the dependent base class into this class for
// simplicity of referring to them.
using BaseT = DenseMapBase<SmallDenseMap, KeyT, ValueT, ValueInfoT, KeyInfoT, BucketT>;
static_assert(powerof2(InlineBuckets),
"InlineBuckets must be a power of 2.");
unsigned Small : 1;
unsigned NumEntries : 31; // 31bit
unsigned NumTombstones;
struct LargeRep {
BucketT *Buckets; // 这个是一个数组
unsigned NumBuckets; // 数量
};
/// A "union" of an inline bucket array and the struct representing
/// a large bucket. This union will be discriminated by the 'Small' bit.
AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
// 一个共用体
// 4个是数组， 然后其他的是使用指针的方式
PS : 为什么苹果使用了DenseMap 替换掉unordered_map ， 在oc里面， hash方法足够好，去替换掉红黑树。
有时间再进一步去理解这个过程。
网友评论