Как получить точное положение элемента в наборе?

Question

У меня есть std::set<std::string>, и я хочу знать точное положение элемента в наборе после вставки.

Я попытался с std::distance, но без удачи:

#include <iostream> 
#include <string> 
#include <set> 
#include <iterator> 

using namespace std; 

int main (int argc, char const *argv[]) 
{ 

    string array[] = { "zero", "one", "one", "zero", "two", "three", "zero" }; 
    set<string> numbers; 
    for(size_t i = 0; i < 7; ++i) 
    { 
     int dist = distance(numbers.begin(), numbers.insert(array[i]).first); 
     cout << array[i] << "\t" << dist << endl; 
    } 
    return 0; 
} 

выходы:

zero 0 
one  0 
one  0 
zero 1 
two  1 
three 1 
zero 3 

Вместо этого, я ожидал этого:

zero 0 
one  1 
one  1 
zero 0 
two  2 
three 3 
zero 0 

Любые идеи?

Answer 1

Они сортируется лексикографически (в основном в алфавитном порядке). Сравнение по умолчанию для std::set<T> - std::less<T>, которое, в свою очередь, вызывает operator<.

Answer 2

Во-первых, строки отсортированы лексикографически, а не на каких числах они обозначают на английском языке. Во-вторых, для каждого элемента код проверяет текущее место размещения в наборе, прежде чем набор будет полностью обновлен всеми элементами.

Приветствия & НТН.,

Answer 3

Как сказано, набор обычно реализуется с каким-то деревом, которое по очереди хранит отсортированные данные, а не в том порядке, в котором вы их вставили (что позволяет вставлять и т. Д. В O (logN)), , Если вы хотите получить желаемый эффект, вы можете использовать любой последовательный контейнер - вектор, deque или список