подскажите существует ли аналог set с возможностью обращения по индексу? или аналог vector c сохранением уникальности как в set

Здравствуйте, Аноним, Вы писали:

А>подскажите существует ли аналог set с возможностью обращения по индексу?
Конечно. В узлах двоичных деревьев поиска, через которые часто реализован std::set, можно хранить размеры поддеревьев — этой информации достаточно чтобы реализовать доступ к элементу множества по индексу за то же время O(logN).

А>или аналог vector c сохранением уникальности как в set
Это же просто делается. Берётся std::vector и поддерживается в сортированном состоянии. Для операций с таким вектором в STL уже есть std::set_intersection, std::set_difference и другие алгоритмы. Вставка делается через std::lower_bound + провека на несовпадение элемента + vector.insert.

Здравствуйте, Аноним, Вы писали:

А>подскажите существует ли аналог set с возможностью обращения по индексу?

вам нужно уточнить, что вы понимаете под индексом и обращением по индексу.
если это индексы 0, 1, 2 в упорядоченном наборе элементов таких что e0 <= e1 <= e2, то с помощью
std::advance(index, mySet.begin()) вы уже имеете индексный доступ (его сложность неконстанта, к сожалению)
понятие индекс малоприменимо к set, поэтому лучше более точно изъясняться, что вам нужно
об этом можно почитать здесь:
http://stackoverflow.com/questions/1796503/index-or-position-in-stdset
http://stackoverflow.com/questions/6670501/getting-a-c-stdsets-members-by-index

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

http://www.boost.org/doc/libs/1_51_0/libs/multi_index/doc/index.html
http://www.boost.org/doc/libs/1_51_0/libs/bimap/doc/html/index.html
http://stackoverflow.com/questions/4189770/anything-available-implemented-like-lokis-assocvector-but-with-the-functionalit

А>или аналог vector c сохранением уникальности как в set

по идее, такие контейнеры должны быть, ключевые слова sorted array, sorted vector
поднимал однажды аналогичный вопрос, но готового решения так и не нашел:
http://www.rsdn.ru/forum/cpp.applied/4445477

Автор: uzhas
Дата: 05.10.11

ссылочки из гугла:
http://www.codeproject.com/Articles/3217/An-STL-compliant-sorted-vector
http://loki-lib.sourceforge.net/html/a00645.html
http://stackoverflow.com/questions/2710221/is-there-a-sorted-vector-class-which-supports-insert-etc

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

Здравствуйте, Аноним, Вы писали:

А>подскажите существует ли аналог set с возможностью обращения по индексу? или аналог vector c сохранением уникальности как в set

http://liveworkspace.org/code/fbab4229b19279ee0a1c0a42f9b5b55b

#include <boost/container/flat_set.hpp>
#include <iostream>
#include <ostream>
#include <typeinfo>
using namespace std;

int main()
{
    boost::container::flat_set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    cout << (s.find(1)!=s.end()) << endl;
    cout << (s.find(4)!=s.end()) << endl;
    cout << s.begin()[0] << endl;
    cout << s.begin()[1] << endl;
    cout << s.begin()[2] << endl;
}

Вывод:

1
0
1
2
3

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>...

EP>    boost::container::flat_set<int> s;

В чём вообще практический смысл примера и контейнера flat_set в целом ?

Здравствуйте, Alexander G, Вы писали:

AG>В чём вообще практический смысл примера и контейнера flat_set в целом ?

В том, что он реализуется в виде сортированного вектора, с соответствующими ништяками (быстрый поиск, нулевой оверхед по памяти, быстрая итерация — все за счет того, что все данные лежат рядом) и недостатками (вставка/удаление приводят к инвалидации всего и вся и копированию почти всего содержимого).

Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality are very different. Using g++ (...) it takes X seconds to perform a million lookups in a sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover, the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).

Т.е. если у тебя в основном поиск, а вставки/удаления редки или их вообще нет, то это то, что доктор прописал.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Alexander G, Вы писали:

EP>>...
AG>

EP>>    boost::container::flat_set<int> s;
AG>

AG>В чём вообще практический смысл примера

В примере показывается использование operator[] на значении возвращённом begin(), что является ответом на часть вопроса ТС.

А>>>подскажите существует ли аналог set с возможностью обращения по индексу? или аналог vector c сохранением уникальности как в set

Здравствуйте, Evgeny.Panasyuk, Вы писали:

а если так?

#include <boost/container/flat_set.hpp>
#include <iostream>
#include <ostream>
#include <typeinfo>
using namespace std;

int main()
{
    boost::container::flat_set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);

    cout << s.begin()[0] << endl;
    cout << s.begin()[1] << endl;
    cout << s.begin()[2] << endl;

    s.begin()[1] = 3;
    cout << s.begin()[0] << endl;
    cout << s.begin()[1] << endl;
    cout << s.begin()[2] << endl;
}

то вывод:

1
2
3
1
3
3

что как то не очень получается.

P.S. возможно ли ограничить допускаемых значений? допустим flat_set<int> в диапазоне от 3 до 19?

Здравствуйте, iking, Вы писали:

I>что как то не очень получается.

а там и set такой же.
gcc'шный set так не компилится, в то время как msvc'шный — компилится.
В SGI написано:

In Simple Associative Containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same.

Быстро поискав в C++03 — чего-то похожего не нашёл.

I>P.S. возможно ли ограничить допускаемых значений? допустим flat_set<int> в диапазоне от 3 до 19?

конечно: flat_set< bounded_int<3,19> >

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, iking, Вы писали:

I>>что как то не очень получается.

EP>а там и set такой же.
EP>gcc'шный set так не компилится, в то время как msvc'шный — компилится.
EP>В SGI написано:
EP>

EP>In Simple Associative Containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same.

EP>Быстро поискав в C++03 — чего-то похожего не нашёл.

я надеялся что

s.begin()[1] = 3;

не позволит так сделать, так как элемент с таким ключом уже есть, получается что как set работает только на insert


I>>P.S. возможно ли ограничить допускаемых значений? допустим flat_set<int> в диапазоне от 3 до 19?

EP>конечно: flat_set< bounded_int<3,19> >
А сложнее?

string begin("10:00:00");
string end("23:00:00");

boost::container::flat_set<std::string> s;
s.insert("10:00:00");
s.insert("09:00:00");
s.insert("20:00:00");

возможно ли тут как ограничить ввод? хотя тут надо как то с реальным временем сопоставить

Здравствуйте, iking, Вы писали:

I>я надеялся что
I>

I>s.begin()[1] = 3;
I>

I>не позволит так сделать, так как элемент с таким ключом уже есть, получается что как set работает только на insert

Также как и boost::container::set, и MSVC std::set.
Наверное это удобно для тех случаев, в которых упорядочивание зависит нет от всего элемента множества + map был бы не удобен.

I>>>P.S. возможно ли ограничить допускаемых значений? допустим flat_set<int> в диапазоне от 3 до 19?
EP>>конечно: flat_set< bounded_int<3,19> >
I>А сложнее?
I>

I>boost::container::flat_set<std::string> s;
I>s.insert("10:00:00");
I>

I>возможно ли тут как ограничить ввод? хотя тут надо как то с реальным временем сопоставить

хм, точно также:
boost::container::flat_set<some::time> s;

А>>подскажите существует ли аналог set с возможностью обращения по индексу?
WM>Конечно. В узлах двоичных деревьев поиска, через которые часто реализован std::set, можно хранить размеры поддеревьев — этой информации достаточно чтобы реализовать доступ к элементу множества по индексу за то же время O(logN).

Обращение по индексу в массиве (std::vector) — это O(1), а не O(log(N))