strsvsample09.cpp File Reference

Example: str_sparse_vector<> sorting example. More...

`#include <iostream>`
`#include <string>`
`#include <vector>`
`#include <random>`
`#include <algorithm>`
`#include "bm.h"`
`#include "bmstrsparsevec.h"`
`#include "bmsparsevec_algo.h"`
`#include "bmdbg.h"`
`#include "bmtimer.h"`
`#include "bmundef.h"`
Include dependency graph for strsvsample09.cpp:

Go to the source code of this file.

## Typedefs

typedef bm::str_sparse_vector< char, bvector_type, 16 > | str_sv_type

## Functions

static void | generate_string_set (vector< string > &str_vec, const unsigned max_coll=850000, unsigned repeat=220)
| generate collection of strings from integers with common prefixes ... and shuffle it
void | quicksort (str_sv_type &strsv, int first, int last)
| quick-sort
void | quicksort2 (str_sv_type &strsv, int first, int last)
| Faster variant of quicksort, uses different variant of pivot compare, with decompressed argument.
static void | insertion_sort (str_sv_type &str_sv, const vector< string > &str_vec)
| insertion sort for performance comnparison
int | main (void)

## Variables

bm::chrono_taker ::duration_map_type | timing_map

## Detailed Description

Example: str_sparse_vector<> sorting example.

Definition in file strsvsample09.cpp.

## Typedef Documentation

## str_sv_type

typedef bm::str_sparse_vector<char, bvector_type, 16> str_sv_type

Definition at line 54 of file strsvsample09.cpp.

## Function Documentation

## generate_string_set()

void generate_string_set | ( | vector< string > & | str_vec,
|  | const unsigned | max_coll = 850000,
|  | unsigned | repeat = 220 )

static

generate collection of strings from integers with common prefixes ... and shuffle it

Definition at line 60 of file strsvsample09.cpp.

Referenced by main().

## insertion_sort()

void insertion_sort | ( | str_sv_type & | str_sv,
|  | const vector< string > & | str_vec )

static

insertion sort for performance comnparison

Definition at line 155 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::insert(), and bm::sparse_vector_scanner< SV, S_FACTOR >::lower_bound_str().

Referenced by main().

## main()

int main | ( | void |  | ) |

Definition at line 177 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::begin(), BM_DECLARE_TEMP_BLOCK, bm::str_sparse_vector< CharType, BV, STR_SIZE >::calc_stat(), bm::chrono_taker< TOut >::ct_time, bm::str_sparse_vector< CharType, BV, STR_SIZE >::end(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::equal(), generate_string_set(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::get_back_inserter(), insertion_sort(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::optimize(), bm::chrono_taker< TOut >::print_duration_map(), quicksort(), quicksort2(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::remap(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::size(), and timing_map.

## quicksort()

void quicksort | ( | str_sv_type & | strsv,
|  | int | first,
|  | int | last )

quick-sort

Examples
  strsvsample09.cpp.

Definition at line 89 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::compare(), quicksort(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::swap().

Referenced by main(), and quicksort().

## quicksort2()

void quicksort2 | ( | str_sv_type & | strsv,
|  | int | first,
|  | int | last )

Faster variant of quicksort, uses different variant of pivot compare, with decompressed argument.

optimizations:

1. use of bm::str_sparse_vector<>::compare() function friendly for re-use of pivot element
2. tail call recursion eleimination

Examples
  strsvsample09.cpp.

Definition at line 120 of file strsvsample09.cpp.

References bm::str_sparse_vector< CharType, BV, STR_SIZE >::compare(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::get(), quicksort2(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::swap().

Referenced by main(), and quicksort2().

## Variable Documentation

## timing_map

bm::chrono_taker ::duration_map_type timing_map

Definition at line 175 of file strsvsample09.cpp.