Здравствуйте Jura Kovalev

std::vector устроен внутри также как и простой массив и дает такой же код в ассемблере что и при индексировании массива, память перестраивается при вставке.Хотя может существуют разные реализации STL.Я имею ввиду P.J. Plauger'а

Мельком смотрел std::map -- черно-красное сбалансированное дерево.Думаю, что тоже дает эффективный код и надо будет постараться самому, чтобы написать лучше, и так же универсально.

std::map пользую сам, также как и Вы.Использую для построения индексов.Единственная проблема для map — это то, что надо что-то думать для загрузки/выгрузки.Поэтому, если речь идет о базе данных и о длительном хранении я использую BerkeleyDB от SleepyCat Software.Это внедряемая база данных(библиотека), которая может по ключу найти данные.Не типизированная (ключ-байты и данные-байты), но зато ACID'ная. Говорят на ней MySQL написан.Мне очень нравиться.

Порядок сортировки в map задается с помощью класса предиката сравнения class Pred
(

template<class Key, class T, class Pred = less<Key>, class A = allocator<T> >
    class map {
public:
...

)

по умолчанию стоит less<Key>
можете поменять на свой, в зависимости от того как строки надо сравнивать.
Я этим не пользовался, поэтому готового кода под рукой нет.Посмотрите в 3-м издании Страуструпа.Там хорошие примеры.
Может быть так (псевдокод):

struct myless:public binary_function<MyObj,MyObj,bool> 
{
    bool operator () (const MyObj& str1, const MyObj& str1) const
    {
        return (строка str1 меньше с конца чем str2);
    }
}

или

tempate <class MyObj>
struct myless:public binary_function<MyObj,MyObj,bool> 
{
    bool operator () (const MyObj& str1, const MyObj& str1) const
    {
        return (строка str1 меньше с конца чем str2);
    }
}

Думаю, наврал не сильно

у меня есть список объектов. для быстрого доступа кним (поиска)
я использую std::map<std::string name,KClass* object>
т.е. по строке ищется указатель...
1. хотелось бы знать ваше мнение об этом "способе"
2. как улучшить?

использую MapObject.find(path) и операции вставки и доступа через скобки []/
3. оказалось что строки — "в большей степени различны к концу" — т.е. начало у них одинаковое

а при проверке TrueTime-ом выяснилось что функция "opertor<" вызываеьтся приличное число раз...
(как я понял это для строк...)
вот хотелось бы сравнение производить с конца строки...

что посоветуете?

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

[]

JK>что посоветуете?

использовать hash_map

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

JK>что посоветуете?
hash_map? Только STL нужна более другая (STLPort, например).

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

JK>что посоветуете?

Сделать свой класс потомок от std::basic_string<> и переопределить для него оператор < так как хочется.

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

N>Здравствуйте Jura Kovalev, Вы писали:

JK>>что посоветуете?

N>Сделать свой класс потомок от std::basic_string<> и переопределить для него оператор < так как хочется.

дык нет там такого оператора.

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

[]

Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

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

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

А>[]

А>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

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

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

N>Здравствуйте Алекс, Вы писали:

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

А>>[]

А>>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

N>Ну значит определить, а не переопределить, суть дела не меняется, даже используя hash_map, это добавит производительности ( если только можно создать такой алгоритм который будет сравнивать строки с конца и при этом правильно определять какая из них меньше )

Че-то я не понимаю каким образом это добавит производительности? hash_map не сравнивает ключи вообще! Он сравнивает хеш от них!

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

JK>у меня есть список объектов. для быстрого доступа кним (поиска)
JK>я использую std::map<std::string name,KClass* object>
JK>т.е. по строке ищется указатель...
JK>1. хотелось бы знать ваше мнение об этом "способе"
JK>2. как улучшить?

JK>использую MapObject.find(path) и операции вставки и доступа через скобки []/
JK>3. оказалось что строки — "в большей степени различны к концу" — т.е. начало у них одинаковое

JK>а при проверке TrueTime-ом выяснилось что функция "opertor<" вызываеьтся приличное число раз...
JK>(как я понял это для строк...)
JK>вот хотелось бы сравнение производить с конца строки...

JK>что посоветуете?

Map действительно очень удобен, но все-таки ресурсоемок. Поэтому приходится выбирать. Могу как альтернативу посоветовать vector.

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

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

N>>Здравствуйте Алекс, Вы писали:

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

А>>>[]

А>>>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

N>>Ну значит определить, а не переопределить, суть дела не меняется, даже используя hash_map, это добавит производительности ( если только можно создать такой алгоритм который будет сравнивать строки с конца и при этом правильно определять какая из них меньше )

А>Че-то я не понимаю каким образом это добавит производительности? hash_map не сравнивает ключи вообще! Он сравнивает хеш от них!

А ключи с одинаковыми значениями хеша он не сортирует? тогда при достаточно больших объемах данных и/или плохой хеш функции может map и лучше будет.

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

JK>>что посоветуете?

N>Сделать свой класс потомок от std::basic_string<> и переопределить для него оператор < так как хочется.

Нет, даже не надо другого класса, третим параметром шаблона идет предикат, подставить туда свой и все.

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

JK>>>что посоветуете?

N>>Сделать свой класс потомок от std::basic_string<> и переопределить для него оператор < так как хочется.

N>Нет, даже не надо другого класса, третим параметром шаблона идет предикат, подставить туда свой и все.

template<class _Ty>
struct less_string : std::binary_function<_Ty, _Ty, bool> {
    bool operator()(const _Ty& _X, const _Ty& _Y) const
    {return (0 < _X.compare(_Y)); } // здесь ваша реализация функции сравнения
};

std::map<std::string, std::string, less_string<std::string> > m

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

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

N>>>Здравствуйте Алекс, Вы писали:

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

А>>>>[]

А>>>>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

N>>>Ну значит определить, а не переопределить, суть дела не меняется, даже используя hash_map, это добавит производительности ( если только можно создать такой алгоритм который будет сравнивать строки с конца и при этом правильно определять какая из них меньше )

А>>Че-то я не понимаю каким образом это добавит производительности? hash_map не сравнивает ключи вообще! Он сравнивает хеш от них!

N>А ключи с одинаковыми значениями хеша он не сортирует? тогда при достаточно больших объемах данных и/или плохой хеш функции может map и лучше будет.

Было бы здорово если бы ключи с одинаковым хэшем hash_map хранил в map.

Благодарю всех отозвавшихся — я даже не думал что так быстро получу ответы!

по мотивам ответов (покрайнер мере как я их понял) я сейчас сижу и колдую...

ХЭШ.

    struct hash_no_case
    {
        inline    size_t operator()(const string &s)const
        {
            size_t h=0; 
            const char *ptr = s.c_str();
            while (*ptr)
            {
                h=h+h+h+h+size_t(*ptr++);
                //ptr++;
            }
            return h;
        }
    }; //hash_no_case
    
    struct equal_string_no_case
    {
        inline bool operator()(const string& lhs,const string& rhs) const
        {
            //return lhs==rhs;

            LPCTSTR pcszLhs = lhs.c_str();
            LPCTSTR pcszRhs = rhs.c_str();
            int nLhsLen = lhs.length();
            //_tcslen (pcszLhs);
            int nRhsLen = rhs.length();
            //_tcslen (pcszRhs);

            if (nLhsLen != nRhsLen)
                return false;

            pcszLhs += nLhsLen - 1;
            pcszRhs += nRhsLen - 1;

            while (*pcszLhs-- == *pcszRhs-- && nLhsLen)
                --nLhsLen;

            return (nLhsLen == 0);
        }
    }; 

hash_map<string,TSignId,hash_no_case,equal_string_no_case> AL2SID;

проблемы:
хотя расход памяти сократился... в несколько раз
оно всёравно медленнее map-a (а почему? )
если на мэпе работало 240 милисекунд — то раз в 10-15 затормозило
если на мэпе работало 30 секунд — то я даже не дождался конца
... может какие-то проблемы которых я не вижу в hash_no_case
или equal_string_no_case???

задача моя не решена, поэтому
ЭКСПЕРИМЕНТЫ БУДЕТ ПРОДОЛЖЕНЫ...

P.S. А что string хранит в себе длину?
первый вызов (по сравнению со вторым) привёл к общему увеличению скорости в 2-4 раза.
int nRhsLen = rhs.length();
int nRhsLen = _tcslen (pcszRhs);

JK>P.S. А что string хранит в себе длину?
да конечно. я протормозил.

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

JK>оно всёравно медленнее map-a (а почему? )
Можно посмотреть профайлером, но мне кажется, что дело в хэш-функции. Попробуй на своих данных посчитать количество коллизий после этого многое прояснится
Ну или попробуй использовать стандартную хэш-функцию для char* — мож и делать больше ничего не придется...

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

JK>3. оказалось что строки — "в большей степени различны к концу" — т.е. начало у них одинаковое

Если начало у них у всех одинаковое и Вы знаете, какой длины, то легче всего написать предикат, который будет проводить сравнение строк не с первого символа, а с n-го? который будет содержать вызов типа strcmp(str1+n, str2+n);


А еще проще попросту откусывать общее начало у строк — тогда и памяти сеньше отжираться будет :)

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

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

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

А>[]

А>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

Я дико извиняюсь, но разве string — это не

typedef basic_string<char> string;

?
Если это так, то string не может иметь того, чего нет у basic_string<>...
А в свете этого ваше высказывание — хрень полнейшая, я извиняюсь за выражение

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

L>Здравствуйте Алекс, Вы писали:

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

А>>[]

А>>Этот и другие операторы определены в string, но не являются членами класса basic_string<>.

L>Я дико извиняюсь, но разве string — это не

L>

L>typedef basic_string<char> string;
L>

L>?
L>Если это так, то string не может иметь того, чего нет у basic_string<>...
L>А в свете этого ваше высказывание — хрень полнейшая, я извиняюсь за выражение :shuffle:


string — это еще и имя файла :)))

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