c++ - 将整数分配给 std::vector 中已排序的唯一元素

Question

例子:鉴于 std::vector<string> v = {"C", "A", "B", "A"} ,

我们寻求

vector<size_t> s := {2,0,1,0} .

这些整数是根据 v 中唯一值的排序顺序分配的: 0-"A", 1-"B", 2-"C"

可能的方法是:

vector<string> unique(v.begin(), v.end());
unique.sort();
unique.erase(std::unique(unique.begin(), unique.end()), unique.end());
vector<size_t> s(v.size());
for(size_t i(0); i < v.size(); i++)
{
   s[i] = std::lower_bound(unique.begin(), unique.end(), v[i]) - unique.begin();
}

是否有更优雅、紧凑且最重要的是高效的方法来执行相同的例程？我知道如何用 std::map 做到这一点或 unordered_map但不是按排序顺序。

更新:显然渐近复杂度无法提高 - 下界是 O(n*logn) (如上)。然而，不同的O(n*logn)算法可能会击败常量或者只是更好 :)

Answer 1

脱袖密码:

set<string> unique( v.begin(), v.end() );
vector<int> s( v.size() );
for( int i = 0; i < (int) v.size(); ++i )
{
   s[i] = unique.find( v[i] ) - unique.begin();
}

我认为这更优雅，我怀疑它可能更高效。

免责声明:编译器未触及代码，执行未检查逻辑......

---

更新:检查代码，嘿set 迭代器不支持减法。所以可能效率不是很好。但我认为它看起来更好(更优雅)! :-)

测试代码:

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

auto main()
    -> int
{
    vector<string> const v = {"C", "A", "B", "A"};
    set<string> const unique( v.begin(), v.end() );

    vector<int> s( v.size() );
    for( int i = 0; i < (int) v.size(); ++i )
    {
       s[i] = distance( unique.begin(), unique.find( v[i] ) );
    }

    copy( s.begin(), s.end(), ostream_iterator<int>( cout, " " ) );
    cout << endl;
}