InsertSortedVector.h File Reference

---

Detailed Description

This file contains a template function tf_InsertSortedVector for inserting a sorted vector of pairs into a map, in an effecient manner.

Definition in file InsertSortedVector.h.

#include <vector>
#include <map>

Go to the source code of this file.

Functions
template<typename FIRST, typename SECOND>
void	tf_InsertSortedVector (std::vector< std::pair< FIRST, SECOND > > &vect_pair_data, std::map< FIRST, SECOND > &mp)
	This function takes vector of pairs which are sorted by the first element, and inserts them into a map, so that the map is balanced on the first pass, and does not require automatic rebalancing. This is most useful, for implementations of map which do not have rebalancing, or have inefficient rebalancing. In a naively programmed map this causes worst case performance for the tree. For a binary tree, which does not rebalance, inserting a sorted list, causes the binary tree to have a depth of N, where N is the number of items in the sorted vector. The tf at the beginning of the function name denotes, "template function".

---

Function Documentation

template<typename FIRST, typename SECOND>

void tf_InsertSortedVector	(	std::vector< std::pair< FIRST, SECOND > > &	vect_pair_data,
		std::map< FIRST, SECOND > &	mp
	)

This function takes vector of pairs which are sorted by the first element, and inserts them into a map, so that the map is balanced on the first pass, and does not require automatic rebalancing. This is most useful, for implementations of map which do not have rebalancing, or have inefficient rebalancing.
In a naively programmed map this causes worst case performance for the tree. For a binary tree, which does not rebalance, inserting a sorted list, causes the binary tree to have a depth of N, where N is the number of items in the sorted vector.
The tf at the beginning of the function name denotes, "template function".

tf_InsertSortedVector

Assumes: for i < j, vect_pair_data[i].first < fct[j].first
Changes: contents of mp
Returns: nothing Description: This function takes vector of pairs which are sorted by the first element, and inserts them into a map, so that the map is balanced on the first pass, and does not require automatic rebalancing. This is most useful, for implementations of map which do not have rebalancing, or have inefficient rebalancing. The tf at the beginning of the function name denotes, "template function".

Definition at line 40 of file InsertSortedVector.h.

{
  std::vector<bool> is_used( vect_pair_data.size(), false);
  std::vector<bool>::iterator p_is_used;
  size_t i, j;

  if (!mp.empty()) mp.clear();

  for (i= vect_pair_data.size()/2; i!=0; i/=2) {
    for (j=0; j<vect_pair_data.size(); j+=i) {
      if (!is_used[j]) {
        is_used[j] = true;
        //mp[vect_pair_data[j].first] = vect_pair_data[j].second();
        mp.insert( mp.begin(), vect_pair_data[j]);
      }
    }
  }
}

---