实现std::sort，replace，fill，accumulate，equal等函数
std::sort
/// <summary>
/// std::sort 是从小到大排列的
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <typeparam name="ComparingFunctions"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="f"></param>
/// 创建时间： 2024-10-09 最后一修改时间：2024-10-09（已测试）
template<typename IteratorClass, typename ComparingFunctions>
void sort(IteratorClass itBegin, IteratorClass itEnd, ComparingFunctions f) {
while (itBegin != itEnd) {
Swap(itBegin, Min(itBegin, itEnd,f)); //与std::sort相同，从小到大
itBegin++;
}
}
/// <summary>
/// bool f(t1, t2){ }
/// 如果函数返回true，则认为 t1 < t2
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <typeparam name="ComparingFunctions"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="fun"></param>
/// <returns></returns>
/// 创建时间： 2024-10-09 最后一修改时间：2024-10-09
template<typename IteratorClass, typename ComparingFunctions>
IteratorClass Min(IteratorClass itBegin, IteratorClass itEnd, ComparingFunctions f) {
assert(itBegin != itEnd);
IteratorClass result = itBegin;
itBegin++;
while (itBegin != itEnd) {
if( f(*itBegin, *result) ) //if *itbegin < *result
result = itBegin;
++itBegin;
}
return result;
}
/// <summary>
///
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="it1"></param>
/// <param name="it2"></param>
/// 创建时间： 2024-07-02 最后一修改时间：2024-10-09
template<typename IteratorClass>
void Swap(IteratorClass it1, IteratorClass it2) {
//std::cout << "===================================\n";
//_pin(*it1);
//_pin(*it2);
/*
auto tmp = *it1; //如果*it2是 int& 则，tmp 的类型是int, 并不是int&。
*it1 = *it2;
*it2 = tmp;
*/
_Math::swap(*it1, *it2);
//_pin(*it1);
//_pin(*it2);
//std::cout << "===================================\n";
}
/// <summary>
/// 交换两个T类型的值
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
/// 创建时间： ????-??-?? 最后一次修改时间：2024-09-17
template <typename T>
void _Math::swap(T &a, T &b) {
/*
T t = a;
a = b;
b = t;
*/
constexpr size_t nLen = sizeof(T);
_byte tmp[nLen];
_Memory::Copy((_byte*)(&tmp), (_byte*)(&a), nLen);
_Memory::Copy((_byte*)(&a), (_byte*)(&b), nLen);
_Memory::Copy((_byte*)(&b), tmp, nLen);
}
例子1：
bool isShorter(const string& s1, const string& s2)
{
return s1.size() < s2.size();
}
int main() {
vector<string> v1 = {"the","quick","red","fox","jumsp","over","the","slow","red","turitle" };
vector<string> v2 = {"the","quick","red","fox","jumsp","over","the","slow","red","turitle" };
ga.BeginTiming();
std::sort(v1.begin(), v1.end(), isShorter);
ga.EndTiming();
_pn(ga.GetTimeUsedDesc());
ga.BeginTiming();
alg.sort(v2.begin(), v2.end(), isShorter);
ga.EndTiming();
_pn(ga.GetTimeUsedDesc());
_pn(v1);
_pn(v2);
}执行结果：
（1次）
（2次）
由于程序是刚写的，并没有什么优化和测试，发现性能不错。：）
例子2 标准库std::sort好像不支持链表。
int main() {
list<int> lst1 = { 0,3,2,3,9,9,7,6,5,4,3,1 };
_list<int> lst2 = { 0,3,2,3,9,9,7,6,5,4,3,1 }; //_DList
alg.sort(lst1.begin(), lst1.end(), [](const int& i1, const int& i2)->bool {
return i1 < i2;
});
alg.sort(lst2.begin(), lst2.end(), [](const int& i1, const int& i2)->bool {
return i1 < i2;
});
_pn(lst1);
_pn(lst2);
std::cout << "--------------------------------------------\n";
//下面代码运行不了，std::sort好像不支持lsit
/*
list<int> lst3 = { 0,3,2,3,9,9,7,6,5,4,3,1 };
_list<int> lst4 = { 0,3,2,3,9,9,7,6,5,4,3,1 }; //_DList
std::sort(lst3.begin(), lst3.end(), [](const int& i1, const int& i2)->bool {
return i1 < i2;
});
std::sort(lst4.begin(), lst4.end(), [](const int& i1, const int& i2)->bool {
return i1 < i2;
});
_pn(lst3);
_pn(lst4);
*/
return 0;
}
结果：
下面是几个函数的代码：
/*******************************************************************************************
文件名 ： _Algorithm.h
功能 ： 通用算法,算法库
作者 ： 李锋
手机 ： 13828778863
Email ： ruizhilf@139.com
创建时间 ： 2024年07月02日
最后一次修改时间 : 2024年10月09日
注意 ：所有base里的头文件都不要包含这个文件
注释 ：每个算法函数都应该有一个用法例子
*********************************************************************************************/
#pragma once
#include "_List.h"
_LF_BEGIN_
/// <summary>
/// 用以描述配对
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间： 2024-08-15 最后一修改时间：2024-08-15
template<class Iterator>
class PairOf : _Object
{
public:
inline PairOf() = default;
/// <summary>
/// 指向左边配对数据的指针
/// </summary>
Iterator itLeft;
/// <summary>
/// 左路配对数据的长度
/// </summary>
size_t LeftLength = 0;
/// <summary>
/// 指向右边配对数据的指针
/// </summary>
Iterator itRight;
/// <summary>
/// 右边配对数据的长度
/// </summary>
size_t RigthLength = 0;
/// <summary>
/// 用于保存查找的左边配对的位置指针
/// </summary>
Iterator itLeftPosition;
/// <summary>
/// 用于保存查找的右边配对的位置指针
/// </summary>
Iterator itRigthPosition;
/// <summary>
/// 配对包含的数据的开始指针，此数据包含配对本身
/// </summary>
/// <returns></returns>
const Iterator begin()const { return itLeftPosition; }
/// <summary>
/// 配对包含的数据的结束位置的后一位指针，此数据包含配对本身
/// </summary>
/// <returns></returns>
const Iterator end()const { return itRigthPosition + RigthLength; }
/// <summary>
/// 返回配对包含的数据数据，包含配对本身
/// </summary>
/// <returns></returns>
auto PairData() {
using T = std::remove_reference_t<decltype(*itLeft)>;
int nLength = end() - begin();
lassert(itLeftPosition != null && itRigthPosition != null && nLength >= 0);
_Array<T> aResult(end() - begin() + 1);
Iterator it = itLeftPosition;
for (size_t n = 0; n < nLength; ++n) { *(aResult.Data + n) = *(it + n); }
aResult.ResetLength(nLength);
aResult.ZeroBufferAll();
return aResult;
}
/// <summary>
/// 返回配对包含的数据数据，不包含配对本身
/// </summary>
/// <returns></returns>
inline auto PairOnlyData() {
using T = std::remove_reference_t<decltype(*itLeft)>;
int nLength = end() - begin() - LeftLength - RigthLength;
lassert(itLeftPosition != null && itRigthPosition != null && nLength >= 0);
_Array<T> aResult(end() - begin() + 1);
Iterator it = itLeftPosition + LeftLength;
for (size_t n = 0; n < nLength; ++n) { *(aResult.Data + n) = *(it + n); }
aResult.ResetLength(nLength);
aResult.ZeroBufferAll();
return aResult;
}
};
/// <summary>
/// 不喜欢用 namespace::, 喜欢用 class., 因此用静态类。
/// lf::sort_selection 改用 alg.sort_selection
/// </summary>
/// 创建时间： 2024-07-25 最后一修改时间：2024-07-25
static class _Algorithm : public _Math
{
public:
/*****************************************************************************
排序
****************************************************************************/
//排序
//参考：https://blog.csdn.net/qq_45615577/article/details/115257685
//排序的概念
/*
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY - SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https ://blog.csdn.net/qq_45615577/article/details/115257685
*/
/// <summary>
/// 选择排序---直接选择排序
/// 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，
/// 直到全部待排序的 数据元素排完 。
/// 找出序列中的最小关键字，然后将这个元素与序列首端元素交换位置。例如，序列前i个
/// 元素已经有序，从第i + 1到第n个元素中选择关键字最小的元素，假设第j个元素为最小
/// 元素，则交换第j个元素与第i + 1个元素的位置。依次执行此操作，直到第n - 1个元素
/// 也被确定。
/// </summary>
/// <typeparam name="T">类型</typeparam>
/// <param name="pData">开始位置</param>
/// <param name="nCount">元素个数</param>
/// <param name="so">排序顺序，默认从小到大</param>
/// 创建时间： 2024-07-01 最后一修改时间：2024-07-01
/// 参考网址：https://blog.csdn.net/qq_45615577/article/details/115257685
template<class T>
void Sort_Selection(T* pData, const size_t& nCount, const bool& bMinMax = true)
{
/*
7 4 5 9 8 2 1
1 4 5 9 8 2 7
2 5 9 8 4 7
4 9 8 5 7
5 8 9 7
7 9 8
8 9
在 [0 , n-1] 中找出最小的放在第一位
在 [1 , n-1] 中找出最小的放在第二位
...
*/
if (pData == null || nCount == 0) return;
int nSortedCount = 0; //已排序好的个数
if (bMinMax) {
while (nSortedCount < nCount) {
int minIndex = nSortedCount;
//在[nStart, nCount-1] 中找出最小值
for (int n = nSortedCount + 1; n < nCount; ++n) {
if (*(pData + n) < *(pData + minIndex)) {
minIndex = n;
}
}
if (minIndex != nSortedCount) {
T tmp = *(pData + minIndex);
*(pData + minIndex) = *(pData + nSortedCount);
*(pData + nSortedCount) = tmp;
}
++nSortedCount;
}
}
else {
while (nSortedCount < nCount) {
int maxIndex = nSortedCount;
//在[nStart, nCount-1] 中找出最大值
for (int n = nSortedCount + 1; n < nCount; ++n) {
if (*(pData + n) > *(pData + maxIndex)) {
maxIndex = n;
}
}
if (maxIndex != nSortedCount) {
T tmp = *(pData + maxIndex);
*(pData + maxIndex) = *(pData + nSortedCount);
*(pData + nSortedCount) = tmp;
}
++nSortedCount;
}
}
}
/// <summary>
/// 返回最小值的位置
/// lf::_DList<int> d1 = { 1,3,5,8,2,0 };
/// lf::_DList<int> d2 = { 1 };
/// lf::_DList<int> d3 = { };
/// vector<int> v = { 1,3,5,8,2,0 };
///
/// _pin(*lf::Min(d1.begin(), d1.end())); //输出： 0
/// _pin(*lf::Min(d2.begin(), d2.end())); //输出： 1
/// _pin(*lf::Min(d3.begin(), d3.end())); //报错，最少一个元素
///
/// _pin(*lf::Min(v.begin(), v.end())); //输出： 0
///
/// _string s = _t("sdwsffa");
/// _pin(*lf::Min(s.begin(), s.end())); //输出： a
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <returns></returns>
/// 创建时间： 2024-07-02 最后一修改时间：2024-07-02
template<typename IteratorClass>
IteratorClass Min(IteratorClass itBegin, IteratorClass itEnd) {
assert(itBegin != itEnd);
IteratorClass result = itBegin;
itBegin++;
while (itBegin != itEnd) {
if (*result > *itBegin)
result = itBegin;
++itBegin;
}
return result;
}
/// <summary>
/// bool f(t1, t2){ }
/// 如果函数返回true，则认为 t1 < t2
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <typeparam name="ComparingFunctions"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="fun"></param>
/// <returns></returns>
/// 创建时间： 2024-10-09 最后一修改时间：2024-10-09
template<typename IteratorClass, typename ComparingFunctions>
IteratorClass Min(IteratorClass itBegin, IteratorClass itEnd, ComparingFunctions f) {
assert(itBegin != itEnd);
IteratorClass result = itBegin;
itBegin++;
while (itBegin != itEnd) {
if( f(*itBegin, *result) ) //if *itbegin < *result
result = itBegin;
++itBegin;
}
return result;
}
/// <summary>
/// 创建时间： 2024-07-02 最后一修改时间：2024-07-02
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <typeparam name="ComparingFunctions"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="f"></param>
/// <returns></returns>
template<typename IteratorClass ,typename ComparingFunctions>
IteratorClass Max(IteratorClass itBegin, IteratorClass itEnd, ComparingFunctions f) {
assert(itBegin != itEnd);
IteratorClass result = itBegin;
//itBegin++;
while (itBegin != itEnd) {
if ( !f(*itBegin, *result)) //if *itbegin < *result
result = itBegin;
++itBegin;
}
return result;
}
/// <summary>
///
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <returns></returns>
/// 创建时间： 2024-07-02 最后一修改时间：2024-07-02
template<typename IteratorClass>
IteratorClass Max(IteratorClass itBegin, IteratorClass itEnd) {
assert(itBegin != itEnd);
IteratorClass result = itBegin;
while (itBegin != itEnd) {
if (*result < *itBegin)
result = itBegin;
++itBegin;
}
return result;
}
/// <summary>
///
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="it1"></param>
/// <param name="it2"></param>
/// 创建时间： 2024-07-02 最后一修改时间：2024-10-09
template<typename IteratorClass>
void Swap(IteratorClass it1, IteratorClass it2) {
//std::cout << "===================================\n";
//_pin(*it1);
//_pin(*it2);
/*
auto tmp = *it1; //如果*it2是 int& 则，tmp 的类型是int, 并不是int&。
*it1 = *it2;
*it2 = tmp;
*/
_Math::swap(*it1, *it2);
//_pin(*it1);
//_pin(*it2);
//std::cout << "===================================\n";
}
/// <summary>
/// 输出itBegin到itEnd之间（不含itEnd)的所有元素，如果分隔符sSeparator为空，
/// 则每行输出一个元素，否则每个元素用分隔符分开。
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itBegin">迭代器开始位置</param>
/// <param name="itEnd">迭代器结束位置</param>
/// <param name="sSeparator">分隔符</param>
/// 创建时间： 2024-08-01 最后一修改时间：2024-08-01
template<typename IteratorClass>
void Print(IteratorClass itBegin, IteratorClass itEnd, const std::string& sSeparator = "") {
//输出beg到end之间（不含end)的所有元素
if (itBegin == itEnd) return;
if (sSeparator == "") {
while (itBegin != itEnd)
std::cout << *itBegin++ << std::endl; //输出当前元素并将指针向前移动一个位置
std::cout << std::endl;
}
else {
while (itBegin != itEnd - 1)
std::cout << *itBegin++ << sSeparator; //输出当前元素并将指针向前移动一个位置
std::cout << *itBegin << std::endl;
}
}
/// <summary>
/// 输出集合的所有元素，如果分隔符sSeparator为空，
/// 则每行输出一个元素，否则每个元素用分隔符分开。
/// </summary>
/// <typeparam name="CollectionClass"></typeparam>
/// <param name="col">集合</param>
/// <param name="sSeparator">分隔符</param>
/// 创建时间： 2024-08-01 最后一修改时间：2024-08-01
template<typename CollectionClass>
void Print(const CollectionClass& col, const std::string& sSeparator = "") {
print(col.begin(), col.end(), sSeparator);
}
/// <summary>
/// lf::_DList<int> d4 = {1,2,3,6,5,4};
/// lf::sort_selection(d4.begin(), d4.end(), _SortOrder::s_Minmax);
/// _pcn(d4); //输出：d4={1,2,3,4,5,6}
/// lf::sort_selection(d4.begin(), d4.end(), _SortOrder::s_Maxmin);
/// _pcn(d4); //输出：d4={6,5,4,3,2,1}
///
/// _string s2 = _t("_DListNodeIterator,abcd,efg");
/// _pcn(s2); //s2=_DListNodeIterator,abcd,efg
/// lf::sort_selection(s2.begin(), s2.end(), _SortOrder::s_Minmax);
/// _pcn(s2); //s2=,,DILN_aabcddeeefgioorrsttt
/// lf::sort_selection(s2.begin(), s2.end(), _SortOrder::s_Maxmin);
/// _pcn(s2); //s2=tttsrrooigfeeeddcbaa_NLID,,
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="so"></param>
/// 创建时间： 2024-07-01 最后一修改时间：2024-10-09（已测试）
template<typename IteratorClass>
void Sort_Selection(IteratorClass itBegin, IteratorClass itEnd, const bool& bMinMax = true)
{
/*
7 4 5 9 8 2 1
1 4 5 9 8 2 7
2 5 9 8 4 7
4 9 8 5 7
5 8 9 7
7 9 8
8 9
7 2 2 2 2 2 2
2 7 2 2 2 2 2
2 7 2 2 2 2
2 7 2 2 2
2 7 2 2
2 7 2
2 7
在 [0 , n-1] 中找出最小的放在第一位
在 [1 , n-1] 中找出最小的放在第二位
...
*/
if (bMinMax) {
while (itBegin != itEnd) {
//在[itBegin + 1, itEnd] 中找出最小值,与itBegin交换
Swap(itBegin, Min(itBegin, itEnd));
itBegin++;
}
}
else {
while (itBegin != itEnd) {
//在[itBegin + 1, itEnd] 中找出最小值,与itBegin交换
Swap(itBegin, Max(itBegin, itEnd));
itBegin++;
}
}
}
/// <summary>
/// std::sort 是从小到大排列的
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <typeparam name="ComparingFunctions"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="f"></param>
/// 创建时间： 2024-10-09 最后一修改时间：2024-10-09（已测试）
template<typename IteratorClass, typename ComparingFunctions>
void sort(IteratorClass itBegin, IteratorClass itEnd, ComparingFunctions f) {
while (itBegin != itEnd) {
Swap(itBegin, Min(itBegin, itEnd,f)); //与std::sort相同，从小到大
itBegin++;
}
}
/*****************************************************************************
查找
顺序查找
二分查找
插值查找、
斐波那契查找
分块查找
哈希查找
树表查找
****************************************************************************/
template<typename IteratorType>
struct FindResult
{
/// <summary>
/// 如果没找到 Index == -1
/// </summary>
int Index;
IteratorType Iter;
public:
inline FindResult()
{
Index = -1;
}
inline FindResult(const FindResult& r)
{
Index = r.Index;
Iter = r.Iter;
}
};
/// <summary>
/// 顺序查找
///
/// 注意：
/// 如果是向后查找，则返回的索引是以itFirst开始算来，第一个为 0，即itFirst为0。
/// 如果是向前揸找，则返回的索引是以itLast开始算起，第一个，即itLast为0。
///
/// </summary>
/// <typeparam name="IteratorType"></typeparam>
/// <typeparam name="DataType"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="tValue"></param>
/// <param name="bBackward"></param>
/// <returns></returns>
/// 创建时间： 2024-07-03 最后一修改时间：2024-07-03
template<typename IteratorType, typename DataType>
FindResult<IteratorType> Find_Sequential(IteratorType itFirst, IteratorType itLast,
const DataType& tFindValue, const bool& bBackward = true)
{
FindResult<IteratorType> fr;
fr.Index = -1;
int n = 0;
if (bBackward) { //向后
while (true)
{
if (*itFirst == tFindValue) {
fr.Index = n;
fr.Iter = itFirst;
break;
}
++n;
++itFirst;
if (itFirst == itLast) break;
}
}
else {
while (true)
{
if (*itLast == tFindValue) {
fr.Index = n;
fr.Iter = itLast;
break;
}
++n;
--itLast;
if (itFirst == itLast) break;
}
}
return fr;
}
/// <summary>
/// 集合类必须带有 begin() 和 end() 函数
/// 例子：
/// std::vector<int> v = { 1,2,3,23,435,4646,34 };
/// lf::_DList<int> d = { 1,2,3,23,435,4646,34 };
/// if (lf::IsExists(d, 23))
/// {
/// cout << "存在23.\n";
/// }
/// if (lf::IsExists(v, 55))
/// {
/// cout << "存在55.\n";
/// }
/// </summary>
/// <typeparam name="value_type"></typeparam>
/// <typeparam name="CollectionClass"></typeparam>
/// <param name="col"></param>
/// <param name="value"></param>
/// <returns></returns>
/// 创建时间： 2024-07-03 最后一修改时间：2024-07-03
template<typename CollectionClass, typename value_type = CollectionClass::value_type>
bool IsExists(const CollectionClass& col, const value_type& value)
{
auto itbegin = col.begin();
auto itend = col.end();
while (itbegin != itend)
{
if (*itbegin == value)
return true;
++itbegin;
}
return false;
}
/// <summary>
/// 二分法查找有序表的通用算法（可查链表，数组，字符串...等等）
/// 注意事项：
/// （1）你设计的迭代器模板中必须有using value_type = T，且有加减运算功能，
/// 其本上能与C++标准库std中一样。
/// （2）集合必须是有序的。
/// 例子：
/// vector<int> v;
/// find_binary(b.begin(),v.end(),3); // Inde返回 (-1, *Iterator == ?)
///
/// vector<int> v = {3};
/// find_binary(b.begin(),v.end(),3); // 返回 (Index == 0, *Iterator == 3)
///
/// const char* sz = "abcdefgb";
/// auto f3 = lf::find_binary(sz, sz + 8, 'c'); //返回 (Index == 2, *Iterator == c)
/// </summary>
/// <typeparam name="IteratorType">迭代器类型</typeparam>
/// <typeparam name="value_type">值类型</typeparam>
/// <param name="itBegin">开始位置</param>
/// <param name="itEnd">结束位置</param>
/// <param name="vtFindValue">查找值</param>
/// <returns>返回索引与指向vtFindValue的迭代器</returns>
/// 创建时间： 2024-07-03 最后一修改时间：2024-07-04 (初步测试）
template<typename IteratorType,typename value_type = IteratorType::value_type>
FindResult<IteratorType> Find_Binary(const IteratorType& itBegin,
const IteratorType& itEnd, const value_type& vtFindValue)
{
FindResult<IteratorType> fr;
auto beg = itBegin;
auto end = itEnd;
int nCount = end - beg;
if (nCount == 0) return fr;
if (*(itEnd-1) > *itBegin) {//从小到大排列
auto mid = beg + nCount / 2;
while (mid != itEnd){
if(*mid == vtFindValue){
fr.Iter = mid;
fr.Index = mid - itBegin;
return fr;
}
if (vtFindValue < *mid)
end = mid;
else
beg = mid + 1; //在mid之后查找
mid = beg + (end - beg) / 2; //新的中间点
}
}else{ //从大到小排列
auto mid = beg + nCount / 2;
while (mid != itEnd) {
if (*mid == vtFindValue) {
fr.Iter = mid;
fr.Index = mid - itBegin;
return fr;
}
if (vtFindValue > *mid)
end = mid;
else
beg = mid + 1; //在mid之后查找
mid = beg + (end - beg) / 2; //新的中间点
}
}
return fr;
}
/// <summary>
/// 查找元素是否存在，或者计算元素个数。
/// 例：
/// _DList<int> d1 = { 1,3,4,5,3 };
/// size_t n;
/// 执行： alg.IsExistsElement(d1, 3, &n, true)) 则 n = 2, 并且函数返回true
/// alg.IsExistsElement(d1, 3), 函数返回true
/// </summary>
/// <typeparam name="CollectionClass">集合类型</typeparam>
/// <typeparam name="Element_Type">集合元素类型</typeparam>
/// <param name="col">集合</param>
/// <param name="Value">元素值</param>
/// <param name="pCount">保存元素个数的变量指针</param>
/// <param name="IsStatisticsCount">是否计算出现个数</param>
/// <returns></returns>
/// 创建时间： 2024-07-30 最后一修改时间：2024-07-30 (初步测试）
template<typename CollectionClass,typename Element_Type = CollectionClass::value_type>
bool IsExistsElement(const CollectionClass& col, const Element_Type &Value,
size_t* pCount = null, const bool &IsStatisticsCount = false)
{
size_t nSize = col.size();
auto itBegin = col.begin();
if (IsStatisticsCount){
assert(pCount != null);
*pCount = 0;
for (size_t n = 0; n < nSize; ++n) {
if (*(itBegin + n) == Value){
*pCount = *pCount + 1;
}
}
return *pCount != 0;
}else{
for (size_t n = 0; n < nSize; ++n){
if (*(itBegin + n) == Value)
return true;
}
return false;
}
}
/// <summary>
/// 检查母集合中是否存在子集.
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itParentBegin">母集开始位置</param>
/// <param name="itParentEnd">>母集结束位置</param>
/// <param name="itSubBegin">子集开始位置</param>
/// <param name="itSubEnd">子集结束位置</param>
/// <returns></returns>
/// 创建时间： 2024-07-24 最后一修改时间：2024-07-24 (初步测试）
template<typename IteratorClass>
bool IsContain(const IteratorClass& itParentBegin, const IteratorClass& itParentEnd,
const IteratorClass& itSubBegin,const IteratorClass& itSubEnd) {
//母串集合元集
size_t nParentSize = itParentEnd - itParentBegin;
//字串集合元素
size_t nSubSize = itSubEnd - itSubBegin;
if (nSubSize == 0 || nParentSize == 0 || nSubSize > nParentSize) return false;
for (size_t i = 0; i < nParentSize - nSubSize + 1; ++i) {
bool isSub = true;
for (size_t j = 0; j < nSubSize; ++j){
if ( *(itParentBegin + i + j) != *(itSubBegin + j) ) {
isSub = false;
break;
}
}
if (isSub) return true;
}
return false;
}
/*
/// <summary>
/// 检查母集合中是否存在子集.
/// </summary>
/// <param name="vecParent">母集</param>
/// <param name="vecSub">子集</param>
/// <returns></returns>
/// 创建时间： 2024-07-24 最后一修改时间：2024-07-24 (初步测试）
inline bool IsContain(const std::vector<int>& vecParent, const std::vector<int>& vecSub)
{
if (vecParent.size() == 0 || vecSub.size() == 0 || vecSub.size() > vecParent.size())
return false;
for (size_t i = 0; i < vecParent.size() - vecSub.size() + 1; ++i) {
bool bFind = true;
for (size_t j = 0; j < vecSub.size(); ++j) {
if (vecParent[i + j] != vecSub[j]) {
bFind = false;
break;
}
}
if (bFind) return true;
}
return false;
}
*/
/// <summary>
/// 检查母集合colParent中是否存在子集colSub。
/// </summary>
/// <typeparam name="CollectionClass"></typeparam>
/// <param name="colParent"></param>
/// <param name="colSub"></param>
/// <returns></returns>
/// 创建时间： 2024-07-25 最后一修改时间：2024-07-25 (初步测试）
template<typename CollectionClass>
bool IsContain(const CollectionClass& colParent, const CollectionClass& colSub) {
//母串集合元集
size_t nParentSize = colParent.size();
auto itParentBegin = colParent.begin();
auto itSubBegin = colSub.begin();
//字串集合元素
size_t nSubSize = colSub.size();
if (nSubSize == 0 || nParentSize == 0 || nSubSize > nParentSize) return false;
for (size_t i = 0; i < nParentSize - nSubSize + 1; ++i) {
bool isSub = true;
for (size_t j = 0; j < nSubSize; ++j) {
if (*(itParentBegin + i + j) != *(itSubBegin + j)) {
isSub = false;
break;
}
}
if (isSub) return true;
}
return false;
}
/***************************************************************
FindFirstOf使用例子代码：
_string s1 = "(int)";
_string s2 = "int";
auto s = FindFirstOf(s1.begin(), s1.end(), s2.begin(), s2.end());
if (s != null)
_cout << s;
输出：
int)
***************************************************************/
/// <summary>
/// 查找一段数据第一次出现的位置。
/// </summary>
/// <typeparam name="T">数据类型</typeparam>
/// <param name="itParentBegin">母数据指针开始位置</param>
/// <param name="itParentEnd">母数据开始结束位置，对于字符串，即：psz + strLength </param>
/// <param name="itSubBegin">子数据指针开始位置</param>
/// <param name="itSubEnd">子数据开始结束位置，对于字符串，即：psz + strLength </param>
/// <returns>如找到，返回这段数据第一次出现的指针位置，否则返回nuLL。</returns>
/// 创建时间： 2024-08-15 最后一修改时间：2024-08-15 (已测试）
template<typename Iterator>
inline Iterator FindFirstOf(const Iterator& itParentBegin, const Iterator& itParentEnd,
const Iterator& itSubBegin, const Iterator& itSubEnd) {
const int nParentLength = itParentEnd - itParentBegin;
const int nSubLength = itSubEnd - itSubBegin;
if (nSubLength <= 0 || nSubLength > nParentLength) return Iterator();
Iterator Result = itParentBegin;
//别忘了加上1
const Iterator end = itParentBegin + nParentLength - nSubLength + 1;
while (Result != end) {
bool bFind = true;
//判断这一段数据是否相等
for (int n = 0; n < nSubLength; ++n) {
if (*(Result + n) != *(itSubBegin + n)) {
bFind = false;
break;
}
}
if (bFind) return Result;
++Result;
}
return Iterator();
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="beginPtr"></param>
/// <param name="endPtr"></param>
/// <param name="p"></param>
/// <returns></returns>
/// 创建时间： 2024-08-15 最后一修改时间：2024-08-15 (已测试）
template<class Iterator>
inline bool FindPairOfFirst(const Iterator& itBegin, const Iterator& itEnd,
PairOf<Iterator>& p)
{
//查找左边第一次出现的位置
p.itLeftPosition = FindFirstOf(itBegin, itEnd, p.itLeft, p.itLeft + p.LeftLength);
//查找右边第一次出现我
if (p.itLeftPosition != null)
{
p.itRigthPosition = FindFirstOf(p.itLeftPosition + p.LeftLength, itEnd, p.itRight,
p.itRight + p.RigthLength);
}
return p.itLeftPosition != null && p.itRigthPosition != null;
}
/// <summary>
/// 获取配对中间的数据，例 (a): for(int i) = 0 ,如果是括号为配对，
/// 那么获取的数据是 "a" 和 "int i" 。
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="beginPtr"></param>
/// <param name="endPtr"></param>
/// <param name="p"></param>
/// <returns></returns>
/// 创建时间： 2024-08-15 最后一修改时间：2024-08-15 (已测试）
template<class Iterator>
auto ExtractionPairData(const Iterator& itBegin, const Iterator& itEnd, PairOf<Iterator>& p)
{
using T = std::remove_reference_t<decltype(*itBegin)>;
_DList<_Array<T>> result;
auto f = FindPairOfFirst(itBegin, itEnd, p);
while (f)
{
result.Add(p.PairOnlyData());
f = FindPairOfFirst(p.itRigthPosition + p.RigthLength, itEnd, p);
}
return result;
}
template<class CollectionClass, class ValueType = CollectionClass::iterator>
_DList<CollectionClass> ExtractionPairData(const CollectionClass& col,
const CollectionClass left, const CollectionClass& right) {
_DList<CollectionClass> result;
/*
auto f = FindPairOfFirst(itBegin, itEnd, p);
while (f)
{
result.Add(p.PairOnlyData());
f = FindPairOfFirst(p.itRigthPosition + p.RigthLength, itEnd, p);
}
*/
return result;
}
/// <summary>
/// 计数colParent包含有多少个colSub，跟IsContain算法一样，但是
/// IsContain找到立即返回。
/// </summary>
/// <typeparam name="CollectionClass">具有迭代性质的类</typeparam>
/// <param name="colParent">母集合</param>
/// <param name="colSub">子集合</param>
/// <returns></returns>
/// 创建时间： 2024-07-29 最后一修改时间：2024-07-29
template<typename CollectionClass>
int count(const CollectionClass &colParent, const CollectionClass &colSub) {
int nResult = 0;
//母串集合元集
size_t nParentSize = colParent.size();
auto itParentBegin = colParent.begin();
auto itSubBegin = colSub.begin();
//字串集合元素
size_t nSubSize = colSub.size();
if (nSubSize == 0 || nParentSize == 0 || nSubSize > nParentSize) return false;
for (size_t i = 0; i < nParentSize - nSubSize + 1; ++i) {
bool isSub = true;
for (size_t j = 0; j < nSubSize; ++j) {
if (*(itParentBegin + i + j) != *(itSubBegin + j)) {
isSub = false;
break;
}
}
if (isSub)
++nResult;
}
return nResult;
}
///
/// <summary>
/// 如果是数组：
/// int ia[] = { 1,2,3,4,5 };
/// accumulate(ia + 0, ia + 5, 0);
///
/// accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型
/// </summary>
/// <typeparam name="value_type"></typeparam>
/// <typeparam name="IterClass"></typeparam>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <param name="InitialValue"></param>
/// <returns></returns>
/// 创建时间： 2024-10-07 最后一修改时间：2024-10-07
template<class IterClass, class value_type>
static value_type accumulate(
const IterClass& begin,
const IterClass& end,
const value_type& InitialValue) {
value_type sum = InitialValue;
size_t n = 0;
while (begin + n < end)
{
sum += *(begin + n);
++n;
}
return sum;
}
/// <summary>
///
/// </summary>
/// <typeparam name="IterClass"></typeparam>
/// <param name="begin1"></param>
/// <param name="end1"></param>
/// <param name="begin2"></param>
/// <returns></returns>
/// 创建时间： 2024-10-07 最后一修改时间：2024-10-07
template<class IterClass>
static bool equal(
const IterClass& begin1,
const IterClass& end1,
const IterClass& begin2) {
size_t n = 0;
while (begin1 + n < end1)
{
if (*(begin1 + n) != *(begin2 + n))
return false;
++n;
}
return true;
}
/// <summary>
///
/// </summary>
/// <typeparam name="IterClass"></typeparam>
/// <typeparam name="value_type"></typeparam>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <param name="tFill"></param>
/// 创建时间： 2024-10-07 最后一修改时间：2024-10-07
template<class IterClass, class value_type>
static void fill(
const IterClass& begin,
const IterClass& end,
const value_type& tFill = value_type()) {
size_t n = 0;
while (begin + n < end)
{
*(begin + n) = tFill;
++n;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="IterClass"></typeparam>
/// <typeparam name="value_type"></typeparam>
/// <param name="begin"></param>
/// <param name="nCount"></param>
/// <param name="tFill"></param>
/// 创建时间： 2024-10-07 最后一修改时间：2024-10-07
template<class IterClass, class value_type>
static void fill_n(
const IterClass& begin,
const size_t& nCount,
const value_type& tFill = value_type()) {
size_t n = 0;
/*
for(size_t n = 0; n < nCount; ++n)
{
*(begin + n) = tFill;
}
*/
IterClass it = begin;
for (size_t n = 0; n < nCount; ++n)
{
*(it) = tFill;
it++;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <param name="dest"></param>
/// <returns></returns>
/// 创建时间： 2024-10-07 最后一修改时间：2024-10-07
template<class T>
const T* copy(const T* begin, const T* end, T* dest) {
T* it1 = (T*)begin;
T* it2 = dest;
while (it1 < end) {
*it2++ = *it1++;
}
return it2;
}
/// <summary>
/// 例子：
///
/// string s = "abcda-";
///
/// _list<int> ilst1 = { 3,5,0,130,0 };
/// list<int> ilst2 = { 3,5,0,130,0 };
///
/// //将所有值为0的元素改为42
/// alg.replace(ilst1.begin(), ilst1.end(), 0, 42);
/// alg.replace(ilst2.begin(), ilst2.end(), 0, 42);
///
/// char sz[] = "abcda";
///
/// alg.replace(s.begin(), s.end(), 'a', 'w');
/// alg.replace(&sz[0], sz + 5, 'a', 'w');
///
/// _pn(ilst1);
/// _pn(ilst2);
/// _pn(s);
/// _pn(sz);
///
/// 输出：
///
/// ilst1={3,5,42,130,42}
/// ilst2={3,5,42,130,42}
/// s="wbcdw-"
/// sz="wbcdw"
///
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="value_type"></typeparam>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <param name="old_value"></param>
/// <param name="new_value"></param>
/// 创建时间： 2024-10-08 最后一修改时间：2024-10-08
template<class itClass,class value_type>
void replace(const itClass& begin, const itClass& end, const value_type& old_value,
const value_type& new_value) {
//itClass it = begin;
itClass it = begin;
//这里要 != ,不能 while (it < end) 因为在链表中，可能不会重载小于运算符
while (it != end) {
if (*it == old_value) {
*it = new_value;
}
it++;
}
}
/// <summary>
/// 注意：std::replace_copy第三个参数为 back_inserter
/// 例子：
/// list<int> ilst = { 0, 1,2,3 };
/// vector<int> ivec{ 3,3 };
///
/// std:
///
/// //使用back_inserter按需要增长目标序列
/// //replace_copy(ilst.cbegin(), ilst.cend(),
/// // back_inserter(ivec), 0, 42);
///
///
/// alg.replace_copy(ilst.cbegin(), ilst.cend(), ivec, 0, 42);
/// _pn(ilst);
/// _pn(ivec);
/// 输出：
/// ilst={0,1,2,3}
/// ivec = { 3,3,42,1,2,3 }
/// </summary>
/// <typeparam name="itClass"></typeparam>
/// <typeparam name="container_class"></typeparam>
/// <typeparam name="value_type"></typeparam>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <param name="cc"></param>
/// <param name="old_value"></param>
/// <param name="new_value"></param>
/// <returns></returns>
/// 创建时间： 2024-10-08 最后一修改时间：2024-10-08
template<class itClass, class container_class, class value_type>
container_class& replace_copy(const itClass& begin, const itClass& end,
container_class& cc,
const value_type& old_value,
const value_type& new_value) {
//itClass it = begin;
itClass it = begin;
//这里要 != ,不能 while (it < end) 因为在链表中，可能不会重载小于运算符
while (it != end) {
if (*it == old_value) {
cc.push_back(new_value);
}else{
cc.push_back(*it);
}
it++;
}
return cc;
}
/// <summary>
/// 返回一个unique的拷贝，注意，如果已排序的集合速度会很快。
/// </summary>
/// <typeparam name="container_class"></typeparam>
/// <param name="cCopy"></param>
/// <param name="is_sorted"></param>
/// <returns></returns>
/// 创建时间： 2024-10-08 最后一修改时间：2024-10-08
template<class container_class>
container_class unique_copy(const container_class& cCopy, bool is_sorted = false) {
container_class cResult;
if (cCopy.size() == 0) return cResult;
auto it = cCopy.begin(), itend = cCopy.end();
if (is_sorted) {
cResult.push_back(*it);
it++;
while (it != itend) {
if (*it != *(cResult.end() - 1)) {
cResult.push_back(*it);
}
it++;
}
}else {
while (it != itend) {
if (!IsExists(cResult, *it)) {cResult.push_back(*it);}
it++;
}
}
return cResult;
}
///
}alg; //类实例
///
_LF_END_ //--------------------------- namespace lf
///