假設我們有一個排序的降序向量，例如：
vector<int> array {26, 21, 13, 11, 8, 3, 2}.
我想在已經存在的元素中插入一個新的和不同的元素，以便保留降序的向量。
示例流程：
- 我想插入元素 22，基本上在索引 1 處添加，因此向量將是：26、22、21、13、11、8、3、2
- 我想插入元素 17，基本上在索引 3 處添加，因此向量將是：26、22、21、17、13、11、8、3、2
- 我想插入元素 1，基本上是在新索引處添加的，因此向量將是：26、22、21、17、13、11、8、3、2、1
- 我想插入元素 43，基本上在索引 0 處添加，因此向量將是：43、26、22、21、17、13、11、8、3、2、1
C 中的快速示例實作將是：
#include<iostream>
#include<vector>
using namespace std;
int get_Index_Insert(const vector<int>& array, int lengthArray, int insertValue)
{
int whereInsert = lengthArray;
for (int i = 0; i < lengthArray; i )
{
if (array[i] < insertValue)
{
whereInsert = i;
break;
}
}
return whereInsert;
}
vector<int> insert_Value(const vector<int>& arrayInput, int insertValue)
{
vector<int> arrayOutput;
int lenghtArray = arrayInput.size();
// At what index to add?
int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue);
// Add it now:
for (int i = 0; i < whereInsert; i )
arrayOutput.push_back(arrayInput[i]);
arrayOutput.push_back(insertValue);
for (int i = whereInsert 1; i < lenghtArray 1; i )
arrayOutput.push_back(arrayInput[i - 1]);
return arrayOutput;
}
int main()
{
vector<int> array{26, 21, 13, 11, 8, 3, 2 };
array = insert_Value(array, 22);
array = insert_Value(array, 17);
array = insert_Value(array, 1);
array = insert_Value(array, 43);
for (int i = 0; i < array.size(); i )
cout << array[i] << " ";
cout << endl << endl << endl;
return 0;
}
其他可能有助于確定推薦方法的資訊：
- 除了來自 STL 的類向量，我不能使用其他任何東西；（僅將它用作持有者 它的 push_back 功能，沒有其他作為輔助功能）；
- I will not have more than a 1000 elements ever in the vector.
Is there any way better to do it than above? in less complexity involved? Any source material I may have missed and that might help is very much appreciated also.
uj5u.com熱心網友回復：
vector您可以使用該insert函式將新值放入現有串列中所需索引處，而不是創建新值。請參閱https://en.cppreference.com/w/cpp/container/vector/insert
void insert_Value(const vector<int>& arrayInput, int insertValue)
{
int lenghtArray = arrayInput.size();
// At what index to add?
int whereInsert = get_Index_Insert(arrayInput, lenghtArray, insertValue);
arrayInput.insert(whereInsert, insertValue);
}
uj5u.com熱心網友回復：
#include <algorithm>
#include<iostream>
#include<vector>
using namespace std;
std::vector<int>::const_iterator get_Index_Insert(const vector<int>& array ,int insertValue) {
return std::find_if(array.cbegin(),array.cend(),[insertValue](int aValue) { return aValue < insertValue;});
}
void insert_Value(vector<int>& arrayInput, int insertValue, std::vector<int>::const_iterator aIt)
{
arrayInput.insert(aIt,insertValue);
}
int main()
{
vector<int> array{26, 21, 13, 11, 8, 3, 2 };
auto myIt = get_Index_Insert(array,22);
insert_Value(array,22,myIt);
for (int i = 0; i < array.size(); i )
cout << array[i] << " ";
cout << endl << endl << endl;
return 0;
}
這只是一個想法，然后可以增強
uj5u.com熱心網友回復：
您不需要傳遞向量的大小，std::vector已經有一個成員函式size()。
我認為你把事情復雜化了。您只需遍歷向量并將每個元素與要插入的值進行比較。如果比較結果為false，那么您找到了插入新元素的位置。
您可以通過以下方式實作該功能：
template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
bool inserted(false);
for(typename std::vector<val_t>::iterator it = vec.begin(); !inserted && (it != vec.end()); it)
{
if(!comp(*it, val))
{
vec.insert(it, val);
inserted = true;
}
}
if(!inserted)
vec.push_back(val);
}
它需要向量、要插入的值和您想要的比較函式。
對于您的用例，它可以這樣使用：
int main()
{
std::vector<int> v {26, 21, 13, 11, 8, 3, 2};
insert_ordered(v, 22, std::greater<int>());
insert_ordered(v, 17, std::greater<int>());
insert_ordered(v, 1, std::greater<int>());
insert_ordered(v, 43, std::greater<int>());
for(const int & i : v)
std::cout << i << ' ';
return 0;
}
輸出：
43 26 22 21 17 13 11 8 3 2 1
活生生的例子
如果由于某種原因不能使用std::greater，則可以像這樣定義自己的比較器：
auto desc_comp = [](const int & lhs, const int & rhs)
{
return lhs > rhs;
};
并像這樣使用它：
insert_ordered(v, 22, desc_comp);
編輯：
如果您不介意函式中有多個退出點，可以將其簡化為：
template <typename val_t, typename Compare>
void insert_ordered(std::vector<val_t> & vec, const val_t & val, Compare comp)
{
for(typename std::vector<val_t>::iterator it = vec.begin(); it != vec.end(); it)
{
if(!comp(*it, val))
{
vec.insert(it, val);
return;
}
}
vec.push_back(val);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/456444.html